两台具有服务等级的可拒绝平行机排序问题

摘要

研究了工件具有服务等级且可拒绝的平行机排序问题.设有两台平行机,加工速度相同;n个工件分别按列表在线到达,每个工件含有三个参数:加工长度,拒绝费用以及服务等级gj=1,2.当且仅当g (M)≤gj时,工件Jj可由机器Mi加工,且加工不允许中断.进一步,当工件到达时,可以选择被加工,花费一定的加工时间;也可以被拒绝,此时要付出相应的罚值.目标为使被接收工件的最大完工时间与被拒绝工件的总罚值之和最小.文中设计出在线算法H,并证明算法的竞争比为1+(√2/2)≈1.707,下界为5/3≈1.667,上下界大约相差0.04.