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

An online algorithm for hierarchical scheduling on two identical machines with rejection

作　　者：闵啸[1] 朱俊蕾 刘静[1] MIN Xiao;ZHU Junlei;LIU Jing(College of Mathematics,Physics and Information Engineering,Jiaxing University,Jiaxing 314001,Zhejiang,China)

机构地区：[1]嘉兴学院数理与&息工程学院,浙江嘉兴314001

出　　处：《运筹学学报》2018年第3期117-124,共8页Operations Research Transactions

基　　金：浙江省高等学校访问学者专业发展项目(No.FX2014074),嘉兴学院科研重点项目(No.70112023BL)。

摘　　要：两台同型机M_1,M_2,加工速度一致,但拥有不同的加工能力,用其服务等级表示,M_1的服务等级为1,M_2的服务等级为2.工件j按列表在线到达,每个工件带有三个参数:长度t_j,等级g_j=1或2,罚值p_j.当j到达时,可以被拒绝,但要付出相应的罚值p_j,也可以被接受并分配给服务等级不超过该工件等级的机器加工,事实上等级为1的工件只能分给M_1加工,等级为2的工件可以分给M_1或M_2加工,加工不允许中断.目标为极小化加工工件集的最晚完工时间(makespan)和拒绝工件集的总罚值之和.对于该问题给出了一个在线算法,其竞争比为11/6,以及问题一个下界5/3.Two identical machines Mi,M2 with same speed but different processing capabilities labeled by their hierarchies are provided.Mi has the hierarchy 1 and that of M2 is 2.Jobs come one by one over list.Each job has three parameters:size tj,hierarchy gj=1,2,penalty pj.When a job arrives,which can be rejected by paying its penalty or be accepted and scheduled on some machine whose hierarchy does not exceed the job's hierarchy.In fact,the job with hierarchy 1 can only be assigned to Mi,but the job with hierarchy 2 can be assigned to Mi or M2.Preemption is not allowed.The objective is to minimize the sum of makespan yielded by all accepted jobs and the total penalties of all rejected jobs.For this problem,we present an online algorithm with a competitive ratio 11/6 and a relative lower bound 5/3.Keywords online scheduling,identical machines,hierarchy,rejected,competitive ratio.

关 键 词：在线排序 同型机 服务等级 可拒绝 竞争比 

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