带等级约束的多重工件在线(半在线)排序问题  

Multiple Jobs Online and Semi-online Scheduling Problems Under GoS Levels

作　　者：代兵飞 夏玉霞 DAI Bingfei;XIA Yuxia(School of Mathematics and Statistics,Yunnan University,Kunming 650000)

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

出　　处：《计算机与数字工程》2020年第3期586-589,677,共5页Computer & Digital Engineering

摘　　要：论文提出了带等级约束的多重工件排序问题,每个客户提交多个加工时间和等级相同的工件。目标是寻找一个调度方案,使得机器的最大完工时间最小。当客户的信息未知时,论文设计了一个竞争比为5/3的在线算法。当所有工件的加工时间总和已知时,论文设计了一个竞争比为3/2的半在线算法。这些结论对经典带等级约束的两台平行机排序问题进行了推广。This paper submits the scheduling problem for multiple jobs under a grade of service(GoS)provision,in which each customer submits multiple jobs with the same processing time and the GoS level. The goal is to minimize the makespan. When the customer information is unknown,this paper presents an online algorithm with competitive ratio of 5/3. When the sum of jobs’ processing times is known in advance,this paper presents an semi-online algorithm with competitive ratio of 3/2. These results generalize the previous results about the scheduling problem on two parallel machines under a grade-of-service provision.

关 键 词：多重工件 等级约束 在线算法 半在线算法 

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