带两个服务等级的三台机最优在线算法  

Optimal online algorithms for hierarchical scheduling on three parallel machines

作　　者：周昊[1] 蒋义伟[2] 王玉艳[3] ZHOU Hao JIANG Yi-wei Wang Yu-yan(Department of Basic Science, Zhejiang Shuren University, Hangzhou 310015, China School of Management and E-Business, Zhejiang Gongshang University, Hangzhou 310018, CHina College of Sciences, Zhejiang Sci-Tech University, Hangzhou 310018, China)

机构地区：[1]浙江树人大学基础部,浙江杭州310015 [2]浙江工商大学管理工程与电子商务学院,浙江杭州310018 [3]浙江理工大学理学院,浙江杭州310018

出　　处：《高校应用数学学报（A辑）》2017年第2期207-216,共10页Applied Mathematics A Journal of Chinese Universities(Ser.A)

基　　金：国家自然科学基金(11571013)

摘　　要：研究了带服务等级约束的三台平行机在线排序问题.每台机器和每个工件的服务等级为1或者2,工件只能在等级不高于它的机器上加工,即等级为1的工件只能在等级为1的机器上加工,等级为2的工件可在所有机器上加工.每个工件的加工时间为一个单位,目标是极小化所有工件的总完工时间.考虑两种情形:当一台机器等级为1,两台机器等级为2时,给出了竞争比为17/14的最优在线算法;当两台机器等级为1,一台机器等级为2时,给出了竞争比为43/36的最优在线算法.This paper investigates an online hierarchical scheduling problem on three parallel identical machines. Each job has a unit processing time and a hierarchy 1 or 2. Each machine has also a hierarchy 1 or 2. The job with a hierarchy 1 can only be processed on the machine with hierarchy 1 and the job with a hierarchy 2 can be processed on any one of three machines. The goal is to minimize the total completion time of all jobs. For the case where one machine with hierarchy I and two machines with hierarchy 2, an optimal online algorithm with competitive ratio of 17/14 is presented. For the case where two machines with hierarchy 1 and one machine with hierarchy 2, an optimal online algorithm with competitive ratio of 43/36 is presented.

关 键 词：在线排序 服务等级 总完工时间 竞争比 

分 类 号：O175.14[理学—数学]