Parallel machine scheduling with service hierarchy and rejection(具有服务等级的可拒绝平行机排序问题)

研究了将服务等级与拒绝费用2种模型复合起来的平行机排序问题.设有2台平行机M1，M2，加工速度相同；n个工件J1,J2，…，Jn分别按列表在线到达，每个工件Jj含有3个参数：加工长度tj、拒绝费用pj以及服务等级gj=1，2.当工件到达时，可以接收加工，占用一定的加工时间；亦可拒绝，付出相应的罚值.目标为被接收工件的最大完工时间与被拒绝工件的总罚值之和最小.进一步，当且仅当g(Mi)≤gj时，工件Jj可以分配给机器Mi加工，即机器M1可以加工所有工件，机器M2只能加工等级为gj=2的工件，允许中断加工.设计了在线算法PH，并证明其竞争比为，下界为1.618，上下界差约为0.089.