两台等级平行机上部分处理时间已知的半在线调度  

Semi-online Scheduling with Partial Processing Time Under Two Levels of Parallel Machines

作　　者：杜豫菲 DU Yufei(School of Mathematics and Statistics,Yunnan University,Kunming 650000)

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

出　　处：《计算机与数字工程》2021年第7期1350-1356,共7页Computer & Digital Engineering

摘　　要：工作环境为两台处理速度相同的平行机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。The working environment is M_(1) and M_(2) with same speed.The jobs have two hierarchy,g_(j)=1 or 2,the jobs with hierarchy is 1 are processed by the first machine,all machines can process the jobs with hierarchy is 2,and sum of jobs'pro⁃cessing time with hierarchical is 1 are already known.The goal is to minimize the marimum completion time.Main ideas is that the first machine is reserved a place that equal to um of jobs'processing time with hierarchical is 1.This study only focuses on discuss⁃ing jobs with hierarchical is 2.The first version,optimal makespan is already known,the competitive ratio at least is 4/3,and there is an algorithm competitive ratio is 4/3.The second version,the max processing time is known,the competitive ratio at least is 4/3,and there is an algorithm competitive ratio is 4/3,too.The third version,the max processing time and optimal makespan are known,the competitive ratio at least is 6/5,and there is an algorithm competitive ratio is 6/5.

关 键 词：竞争比 半在线问题 平行机 等级调度 

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