-
题名两台等级平行机上部分处理时间已知的半在线调度
- 1
-
-
作者
杜豫菲
-
机构
云南大学数学与统计学院
-
出处
《计算机与数字工程》
2021年第7期1350-1356,共7页
-
文摘
工作环境为两台处理速度相同的平行机M_(1),M_(2),工件具有两种不同的等级g_(j)=1或2,等级g_(j)=1的工件只能在第1台机器上处理,等级g_(j)=2的工件两台机都能处理。已知等级g_(j)=1的工件的处理时间之和,目标是最小化最大完工时间。主要思路为第一台机器预留出等级g_(j)=1的工件的总处理时间,分析过程中只对等级g_(j)=2的工件进行讨论。文章的三种半在线等级调度问题分别为已知最优处理时间,即已知C^(opt)的情况,可得竞争比大于等于4/3,并有竞争比为4/3的半在线算法;已知工件的最大处理时间,可得竞争比大于等于4/3,同样有算法得出竞争比为4/3;对已知最优处理时间和工件最大处理时间的半在线问题,得到竞争比大于等于6/5,并且找到了相应的算法竞争比小于等于6/5。
-
关键词
竞争比
半在线问题
平行机
等级调度
-
Keywords
competitive ratio
semi-online problems
parallel machines
hierarchical scheduling
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
