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