|
带两个服务等级的三台机最优在线算法
收藏
周昊, 蒋义伟, 王玉艳
高校应用数学学报. 2017 (2): 207-216.
研究了带服务等级约束的三台平行机在线排序问题. 每台机器和每个工件的服务等级为1或者2, 工件只能在等级不高于它的机器上加工, 即等级为1的工件只能在等级为1的机器上加工, 等级为2的工件可在所有机器上加工. 每个工件的加工时间为一个单位, 目标是极小化所有工件的总完工时间. 考虑两种情形:当一台机器等级为1, 两台机器等级为2时, 给出了竞争比为17/14的最优在线算法;当两台机器等级为1, 一台机器等级为2时, 给出了竞争比为43/36的最优在线算法.
|
|