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

摘要

两台同型机M1,M2,加工速度一致,但拥有不同的加工能力,用其服务等级表示,M1的服务等级为1,M2的服务等级为2.工件j按列表在线到达,每个工件带有三个参数:长度t,等级gj=1或2,罚值pj.当J到达时,可以被拒绝,但要付出相应的罚值pj,也可以被接受并分配给服务等级不超过该工件等级的机器加工,事实上等级为1的工件只能分给M1加工,等级为2的工件可以分给M1或M2加工,加工不允许中断.目标为极小化加工工件集的最晚完工时间(makespan)和拒绝工件集的总罚值之和.对于该问题给出了一个在线算法,其竞争比为11/6,以及问题一个下界5/3.