三台带服务等级的可拒绝同型机在线排序问题

研究三台带服务等级的同型平行机可拒绝在线排序问题．设有三台同型机Mi，i=1，2，3，机器速度一致，并具有两个不同的加工等级g（Mi）=1，2，等级为1的机器数为k，等级为2的机器数为3-k．工件j按列表在线到达，每个工件具有三个参数：长度tj，罚值pj及等级gj=1，2．当工件到达时，可以被接受且分配给某台机器加工，也可以被拒绝，付出相应的罚值．另外，当且仅当g（M）≤譬。时，j可以分配给M。加工，加工不允许中断．目标是使接受加工工件的最大完工时间和被拒绝工件的总罚值最小．针对k=1及k=2两种情况分别给出在线算法HI和H2，其竞争比为2，同时给出该问题的一个下界1．839．

Online Hierarchical Scheduling on Three Identical Machines with Rejection

This paper studies online hierarchical scheduling problem on three identical machines with rejection. Machines are provided with different capabilities. Each machine has a certain GOS level 1 or 2 and every job is also associated with a hierarchy 1 or 2. The job can only be assigned to the machine whose GOS level doesn＇t exceed the job＇s hierarchy, preemption is not allowed. Jobs come one by one over list. When a job arrives, which can be accepted and scheduled on some machine or rejected by paying its penalty. The objective is to minimize the sum of makespan yielded by accepted jobs and total penalties of all rejected jobs. Two online al- gorithms H1 and H2, whose competitive ratio is 2, are presented, while the lower bound is 1. 839.