一特殊情形不可中断的两台可拒绝同型平行机在线排序问题

A Special Case of Preemptive On-Line Scheduling On Two Identical Machines with Rejection

讨论一特殊情况的两台可拒绝同型机在线排序问题的近似算法.设有两台同型机,工件逐个到达,可以被接受加工,消耗一定的加工时间tj,也可以被拒绝,但要付出一定的罚值pj,目标是要使被加工工件的最大完工时间(makespan)和拒绝工件的罚值之和最小.假设每个工件的罚值和加工长度成固定的比例α∈[0,+∞),即pj=αtj,针对工件加工不可中断情形,设计出算法NPRL,证明其参数竞争比,同时又给出问题下界,它们均为α的分段函数.算法NPRL在α∈0,2 2∪[1,+∞)已达到最优.

This paper investigates a special case of the on-line scheduling problem on two identical machines with rejection. The job comes one by one, and when a job arrives, one can either assign it to a certain machine or reject it 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 NPRL and prove the competitive ratio. Finally, a lower bound of this problem is proposed which shows that in the interval of α∈[0,√2/2）∪[1,＋∞） our algorithm is optimal.