摘要
研究了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.
作者
肖满
丁璐
张怡
XIAO Man;DING Lu;ZHANG Yi(School of Mathematics and Statistics,Yunnan University,Kunming 650000,China)
出处
《计算机工程与科学》
CSCD
北大核心
2020年第12期2252-2258,共7页
Computer Engineering & Science
基金
国家自然科学基金(61662088)。
关键词
排序
服务等级
3台机器
半在线算法
竞争比
scheduling
grade of service
three machines
semi-online algorithm
competitive ratio
