Please wait a minute...
高校应用数学学报
Applied Mathematics A Journal of Chinese Universities  2017, Vol. 32 Issue (2): 207-216    DOI:
    
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
Download:
Export: BibTeX | EndNote (RIS)      

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     
Received: 07 December 2016      Published: 01 June 2017
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
ZHOU Hao
JIANG Yi-wei
Wang Yu-yan
Cite this article:

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.

URL:

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


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

研究了带服务等级约束的三台平行机在线排序问题. 每台机器和每个工件的服务等级为1或者2, 工件只能在等级不高于它的机器上加工, 即等级为1的工件只能在等级为1的机器上加工, 等级为2的工件可在所有机器上加工. 每个工件的加工时间为一个单位, 目标是极小化所有工件的总完工时间. 考虑两种情形：当一台机器等级为1, 两台机器等级为2时, 给出了竞争比为17/14的最优在线算法；当两台机器等级为1, 一台机器等级为2时, 给出了竞争比为43/36的最优在线算法.

关键词： 在线排序,  服务等级,  总完工时间,  竞争比 
[1] WEI Han-yu, XIA Tie-cheng. Nonlinear bi-integrable couplings of Broer-Kaup-Kupershmidt hierarchy with self-consistent sources[J]. Applied Mathematics A Journal of Chinese Universities, 2017, 32(2): 165-175.