论文部分内容阅读
讨论两台可拒绝同类机在线排序问题的近似算法。设两台机器的速度之比为ｓ（≥１）。工件逐个到位，可以被加工，也可以被拒绝，但要付出相应的罚值ｐｊ。并且只有在安排完当前工件之后，下一个工件才到达。目标函数要求被加工工件集的最迟工件完工时间与被拒绝工件集的总罚值之和达到最小。文中设计出线性时间的ＲＬＳ（α）算法，并证明了其关于ｓ的参数紧界，这个界于ｓ＝１以及ｓ≥（５＋１）／２均是不可改进的。