两台可中断同类机可拒绝半在线排序问题的近似算法

研究一个两台同类机可拒绝半在线排序问题,机器速度一个为1,另一个为s∈[1,+∞),加工允许中断.当工件到达时,可以将其接受加工,占用一定的机器负荷,也可以将其拒绝,付出相应的罚值,目标为使被接受工件集产生的makespan和被拒绝工件集的总罚值之和最小.问题进一步假定每个工件在选择是否加工时有两个拒绝尺度,各自独立决策,最后选择较好的结果作为最终输出.笔者设计了算法H,得到其关于s的参数竞争比为s+2s+1,优于只有一个拒绝尺度的经典情形.最后又给出问题的一个下界(s+1)2s2+s+1,上下界的最大差距在s=1时达到0.167.

Semi on-line preemptive scheduling on two uniform machines with rejection

A semi on-line scheduling problem on two uniform machines with rejection is investigated.The speed of the first machine is 1 and the second machine is s∈[1,＋∞）,preemption is permitted.When a job arrives,we can either reject it,when one pays its penalty,or accepts it when it contributes its processing time to the makespan of the constructed schedule.The objective is to minimize the sum of the makespan which is yeilded by the accepted jobs and the penalties of all rejected jobs.In addition,two rejection strategies are allowed and two schedules are performed independently.Then two schemes are obtained and one can select the better solution.We present an approximation algorithm with competitive ratio s＋2s＋1,which is strictly less than the classical version that has only one rejection strategy.Finally a lower bound of（s＋1）2s2＋s＋1 is proposed,the largest gap between the competitive ratio and the lower bound is 0.167 when s is equal to 1.