Heuristics for Online Scheduling on Identical Parallel Machines with Two GoS Levels

被引：0

作者：

CAI Shuang ^{[1
,2
,3
]}

LIU Ke ^{[2
,3
]}

机构：

[1] Logistics R&D Department, Beijing Jingdong Zhenshi Information Technology Co., Ltd

[2] Academy of Mathematics and Systems Science, Chinese Academy of Sciences

[3] University of Chinese Academy of Sciences

来源：

JournalofSystemsScience&Complexity | 2019年 / 32卷 / 04期

基金：

中国国家自然科学基金;

关键词：

Grade of Service(GoS) constraints; heuristic algorithm; online scheduling; parallel machine scheduling;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

This paper considers the online scheduling problem on m(m ≥ 3) parallel machines(the first k machines with grade 1 and the remaining m-k machines with grade 2) with two Go S levels and makespan as the objective function. The jobs arrive over time with grade 1 or 2 and an arrival job can be assigned to a machine only when the grade of the job is no less than the grade of the machine. Three cases are considered:(i) For k = 1, the authors present an online algorithm with competitive ratio of9/5.(ii) For 1 < k < m-1, an online algorithm with competitive ratio of 2.280 is proposed.(iii)For k = m-1, an online algorithm is presented with competitive ratio of 2. All the three algorithms are based on greedy algorithm with a similar structure. At last, numerical instances are given and the average competitive ratios of the instances show good performance of the proposed algorithms.

引用

页码：1180 / 1193

页数：14

共 18 条

[1] On-Line Scheduling on Parallel Machines to Minimize the Makespan[J]. LI Songsong,ZHANG Yuzhong.Journal of Systems Science ＆ Complexity. 2016(02)
[2] Optimal semi-online scheduling algorithms on two parallel identical machines under a grade of service provision[J] . Yong Wu,Min Ji,Qifan Yang.International Journal of Production Economics . 2011 (1)
[3] A combined integer/constraint programming approach to a resource-constrained parallel machine scheduling problem with machine eligibility restrictions
Edis, Emrah B.
Ozkarahan, Irem
[J]. ENGINEERING OPTIMIZATION, 2011, 43 (02) : 135 - 157
[4] A note on hierarchical scheduling on two uniform machines
Tan, Zhiyi
Zhang, An
[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2010, 20 (01) : 85 - 95
[5] Fast approximation algorithms for job scheduling with processing set restrictions[J] . Yumei Huo,Joseph Y.-T. Leung.Theoretical Computer Science . 2010 (44)
[6] Online parallel machines scheduling with two hierarchies[J] . An Zhang,Yiwei Jiang,Zhiyi Tan.Theoretical Computer Science . 2009 (38)
[7] Online scheduling on two uniform machines to minimize the makespan[J] . Ming Liu,Yinfeng Xu,Chengbin Chu,Feifeng Zheng.Theoretical Computer Science . 2009 (21)
[8] Parallel machine scheduling with machine availability and eligibility constraints[J] . Lu-Wen Liao,Gwo-Ji Sheen.European Journal of Operational Research . 2006 (2)
[9] Two-phase sub population genetic algorithm for parallel machine-scheduling problem
Chang, PC
Chen, SH
Lin, KL
[J]. EXPERT SYSTEMS WITH APPLICATIONS, 2005, 29 (03) : 705 - 712
[10] Online and semi-online scheduling of two machines under a grade of service provision[J] . Jongho Park,Soo Y. Chang,Kangbok Lee.Operations Research Letters . 2005 (6)

← 1 2 →