三台可拒绝平行机在线排序问题的近似算法

研究了工件带有拒绝费用的3台平行机在线算法,假定有3台平行机M_1,M_2,M_3,n个工件J_1,J_2,…,J_n,每个工件可以被接收加工,消耗一定的加工时间tj;也可以被拒绝,但要付出相应的拒绝费用pj,目标为被接收工件的最大完工时间(makespan)与被拒绝工件的总罚值之和最小。进一步,假定每个工件有两套拒绝策略,最后输出目标值较好的一种。文中设计出在线算法H,并证明算法的竞争比为15/8。