一个可中断两台可拒绝同型机半在线排序问题  

Preemptive semi-on-line scheduling on two identical machines with rejection

作　　者：闵啸[1] 张玉才[2] 

机构地区：[1]嘉兴学院数学与信息科学学院,浙江嘉兴314001 [2]嘉兴学院人文社科训练中心,浙江嘉兴314001

出　　处：《浙江大学学报（理学版）》2007年第5期509-514,共6页Journal of Zhejiang University（Science Edition）

摘　　要：讨论一个两台可拒绝同型机半在线排序问题的近似算法.设有两台同型机,工件逐个到达,可以被接收加工,消耗一定的加工时间tj,也可以被拒绝,但要付出一定的罚值pj,目标是使被加工工件集的最大完工时间(makespan)和被拒绝工件集的罚值之和最小.此外,进一步假定每个工件的罚值和加工长度事先形成固定的比例α∈[0,+∞),即pj=αtj,针对工件加工可中断情形,设计出近似算法PRH,证明其竞争比.同时又给出该问题的下界,它们均为α的分段函数,且算法PRH在α∈[0,2^(1/2)/2〕∪[5/6,+∞〕达到最优.A semi on-line scheduling problem on two identical machines with rejection is investigated. 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. And it is further assumed that the processing time of each job and its penalty forms the regular proportion denoted by α ∈ [0,＋∞） in advance. Preemption is allowed. For this versions, an approximation algorithm PRH is presented and the competitive ratio from a worst-case analysis is given. At last, a lower bound of this problem is proposed and in the interval of α ∈ [0,＋√2/2）∪[5/6,＋∞） our algorithm is already optimal.

关 键 词：半在线 排序 可拒绝 可中断 同型机 近似算法 竞争比 

分 类 号：O223[理学—运筹学与控制论]