具有等级约束的三台机排序问题的可中断在线算法

摘要

研究具有等级约束的三台机在线排序问题.机器和工件的等级数均为1或2,工件只能在等级数不超过自身等级的机器上加工,且加工允许中断,目标是极小化最大工件完工时间.如果有两台机器等级为1,给出竞争比为3/2的在线算法,并证明算法是最好可能的;如果只有一台等级为1的机器,也给出竞争比为3/2的在线算法.