带两个服务等级的3台机半在线算法  

Semi-online algorithms for hierarchical scheduling on three parallel machines

作　　者：肖满 丁璐 张怡 XIAO Man;DING Lu;ZHANG Yi(School of Mathematics and Statistics,Yunnan University,Kunming 650000,China)

机构地区：[1]云南大学数学与统计学院,云南昆明650000

出　　处：《计算机工程与科学》2020年第12期2252-2258,共7页Computer Engineering & Science

基　　金：国家自然科学基金(61662088)。

摘　　要：研究了3台机上带有2个服务等级的半在线排序问题,其中等级为1的机器只有1台,等级为2的机器有2台,目标为极小化机器最大完工时间。在已知等级为1的工件加工时间之和时,给出一个下界为3/2和一个竞争比为5/3的在线算法;在已知等级为2的工件加工时间之和时,给出一个下界为3/2和一个竞争比为9/5的在线算法;在分别已知2个等级的工件加工时间之和时,给出一个下界为4/3和一个竞争比为3/2的在线算法;在已知工件总的加工时间时,给出一个竞争比为3/2的最优在线算法。This paper studies a semi-online hierarchical scheduling problem on three identical machines.In the problem,there is only one machine with hierarchy 1 and two machines with hierarchy 2,and the goal is to minimize the makespan.When the total size of low-hierarchy is known,an online algorithm with the competitive ratio of 5/3 and the lower bound of 3/2 is given.When the total size of high-hierarchy is known,an online algorithm with the competitive ratio of 9/5 and the lower bound of 3/2 is given.When the total size of each hierarchy is known,an online algorithm with the competitive ratio of 3/2 and the lower bound of 4/3 is given.When the total size of jobs is known,a best possible online algorithm with the competitive ratio of 3/2 is given.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]