论文部分内容阅读
研究了带服务等级约束的三台平行机在线排序问题．每台机器和每个工件的服务等级为1或者2，工件只能在等级不高于它的机器上加工，即等级为1的工件只能在等级为1的机器上加工，等级为2的工件可在所有机器上加工．每个工件的加工时间为一个单位，目标是极小化所有工件的总完工时间．考虑两种情形：当一台机器等级为1，两台机器等级为2时，给出了竞争比为17／14的最优在线算法；当两台机器等级为1，一台机器等级为2时，给出了竞争比为43／36的最优在线算法．