Please wait a minute...
高校应用数学学报
高校应用数学学报  2017, Vol. 32 Issue (2): 207-216    
    
带两个服务等级的三台机最优在线算法
周昊1 , 蒋义伟2∗ , 王玉艳3
1. 浙江树人大学 基础部, 浙江杭州 310015
2. 浙江工商大学 管理工程与电子商务学院, 浙江杭州 310018
3. 浙江理工大学 理学院, 浙江杭州 310018
Optimal online algorithms for hierarchical scheduling on three parallel machines
ZHOU Hao1 , JIANG Yi-wei2 , Wang Yu-yan3
1. Department of Basic Science, Zhejiang Shuren University, Hangzhou 310015, China
2. School of Management and E-Business, Zhejiang Gongshang University, Hangzhou 310018, China
3. College of Sciences, Zhejiang Sci-Tech University, Hangzhou 310018, China
 全文: PDF 
摘要： 研究了带服务等级约束的三台平行机在线排序问题. 每台机器和每个工件的服务等级为1或者2, 工件只能在等级不高于它的机器上加工, 即等级为1的工件只能在等级为1的机器上加工, 等级为2的工件可在所有机器上加工. 每个工件的加工时间为一个单位, 目标是极小化所有工件的总完工时间. 考虑两种情形：当一台机器等级为1, 两台机器等级为2时, 给出了竞争比为17/14的最优在线算法；当两台机器等级为1, 一台机器等级为2时, 给出了竞争比为43/36的最优在线算法.
关键词： 在线排序;  服务等级;  总完工时间;  竞争比    
Abstract: 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 1 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.
Key words: online scheduling    hierarchy    total completion time    competitive ratio
收稿日期: 2016-12-07 出版日期: 2017-06-01
基金资助: 国家自然科学基金(11571013)
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
周昊
蒋义伟
王玉艳

引用本文:

周昊, 蒋义伟, 王玉艳. 带两个服务等级的三台机最优在线算法[J]. 高校应用数学学报, 2017, 32(2): 207-216.

ZHOU Hao , JIANG Yi-wei , Wang Yu-yan. Optimal online algorithms for hierarchical scheduling on three parallel machines. Applied Mathematics A Journal of Chinese Universities, 2017, 32(2): 207-216.

链接本文:

http://www.zjujournals.com/amjcua/CN/    或    http://www.zjujournals.com/amjcua/CN/Y2017/V32/I2/207

No related articles found!