论文部分内容阅读
研究了工件带有拒绝费用的3台平行机在线算法，假定有3台平行机M1，M2，M3，n个工件J1，J2，…，Jn，每个工件可以被接收加工，消耗一定的加工时间tj；也可以被拒绝，但要付出相应的拒绝费用Pj，目标为被接收工件的最大完工时间（makespan）与被拒绝工件的总罚值之和最小。进一步，假定每个工件有两套拒绝策略，最后输出目标值较好的一种。文中设计出在线算法H，并证明算法的竞争比为15/8。