一特殊情形的三台可拒绝同型机在线排序问题

A Special Case of Nonpreemptive On-line Scheduling on Three Identical Machines with Rejection

给定三台同型平行机,工件逐个到达,每个工件带有两个参数(tj,Pj),可以被接受加工,消耗一定的加工时间tj,也可以被拒绝,但要付出一定的罚值Pj,目标是要使被加工工件的最大完工时间makespan和拒绝工件的罚值之和最小．文中进一步假定每个工件的罚值和加工长度成固定的比例α∈[0,＋∞),针对工件加工不可中断情形,设计出近似算法PRL,证明其关于α的参数竞争比,进一步给出该问题的下界,它们均为α的分段函数．该算法在α∈[0,1/2)∪[1,＋∞)已达到最优．

This paper investigates a special case of the on-line scheduling problem on three identical machines with rejection. The job comes one by one, and when a job arrives, it can either be assigned to a certain machine or rejected by paying out the penalty. The objective is to minimize the sum of the makespan produced by the accepted jobs and the total penalty of the jobs which have been rejected. We assume that the processing time of each job and its penalty forms the regular proportion denoted by α∈[0,＋∞）. Preemption is not allowed. For this version, we present an on-line algorithm PRL and prove the competitive ratio. Finally, a lower bound 1 of this problem is proposed which shows that in the interval ofα∈[0,1/2） ∪ [1, ＋∞） our algorithm is optimal