论文部分内容阅读
本文讨论一个两台可拒绝同型机半在线排序问题．当工件到达时，可以被拒绝，但要付出一定的罚值，也可以被接收加工，消耗一定的加工时间．其目标是要使所有加工工件生成的makespan和被拒绝工件的总罚值之和最小．加工不允许中断．进一步，机器带有两个并行处理子系统，可以提供两种排序方案，最后选取较好的一种．这是第一个在可拒绝同型机排序模型中使用半在线信息，我们设计出一个近似算法，其竞争比为3／2，另外又给出一个√3＋1/2≈1．366的下界．