论文部分内容阅读
研究一个两台同类机可拒绝半在线排序问题,机器速度一个为1,另一个为s∈[1,＋∞）,加工允许中断.当工件到达时,可以将其接受加工,占用一定的机器负荷,也可以将其拒绝,付出相应的罚值,目标为使被接受工件集产生的makespan和被拒绝工件集的总罚值之和最小.问题进一步假定每个工件在选择是否加工时有两个拒绝尺度,各自独立决策,最后选择较好的结果作为最终输出.笔者设计了算法H,得到其关于s的参数竞争比为s＋2s＋1,优于只有一个拒绝尺度的经典情形.最后又给出问题的一个下界（s＋1）2s2＋s＋1,上下界的最大差