计算机工程与科学

作者：肖满, 丁璐, 张怡

单位：（云南大学数学与统计学院,云南 昆明 650000）

关键词：排序,服务等级,3台机器,半在线算法,竞争比,

基金：国家自然科学基金 （61662088）

研究了3台机上带有2个服务等级的半在线排序问题，其中等级为1的机器只有1台，等级为2的机器有2台，目标为极小化机器最大完工时间。在已知等级为1的工件加工时间之和时，给出一个下界为3/2和一个竞争比为5/3的在线算法；在已知等级为2 的工件加工时间之和时，给出一个下界为3/2和一个竞争比为9/5的在线算法；在分别已知2个等级的工件加工时间之和时，给出一个下界为4/3和一个竞争比为3/2的在线算法；在已知工件总的加工时间时，给出一个竞争比为3/2的最优在线算法。

来源：2020年第12期

《计算机工程与科学》期刊编辑部

查看计算机工程与科学杂志2020年第12期