A best possible online algorithm for parallel batch scheduling with delivery times and limited restart

被引：4
作者：
Liu, Hailing [1 ,2 ]
Lu, Xiwen [1 ]
Li, Wenjie [3 ]
机构：
[1] East China Univ Sci & Technol, Dept Math, Shanghai 200237, Peoples R China
[2] Henan Univ Engn, Coll Sci, Zhengzhou 451191, Henan, Peoples R China
[3] Luoyang Normal Univ, Sch Math Sci, Luoyang 471934, Henan, Peoples R China
来源：
OPTIMIZATION LETTERS | 2021年 / 15卷 / 04期
关键词：
Online scheduling; Parallel batch; Drop-line; Limited restart; Delivery nine; SINGLE-MACHINE; SEMICONDUCTOR INDUSTRY; MINIMIZE; MODELS;
D O I：
10.1007/s11590-020-01618-8
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We consider the online scheduling on an unbounded (drop-line) parallel batch machine to minimize the time by which all jobs have been delivered. In this paper, all jobs arrive over time and the running batches are allowed limited restart. Here limited restart means that a running batch which contains restarted jobs cannot be restarted again. A drop-line parallel batch machine can process several jobs simultaneously as a batch, and all jobs in a batch start at the same time, and the completion time of a job equals the sum of its starting time and its processing time. Here we consider the restricted model: all jobs have agreeable processing times and delivery times. We provide a best possible online algorithm H with a competitive ratio of I for the problem on an unbounded parallel batch machine and the corresponding problem on an unbounded drop-line parallel batch machine, respectively.
引用
收藏
页码：1155 / 1173
页数：19
相关论文
共 19 条
[11]   An improved on-line algorithm for single parallel-batch machine scheduling with delivery times [J].
Tian, Ji ;
Cheng, T. C. E. ;
Ng, C. T. ;
Yuan, Jinjiang .
DISCRETE APPLIED MATHEMATICS, 2012, 160 (7-8) :1191-1210
[12]   A REVIEW OF PRODUCTION PLANNING AND SCHEDULING MODELS IN THE SEMICONDUCTOR INDUSTRY .2. SHOP-FLOOR CONTROL [J].
UZSOY, R ;
LEE, CY ;
MARTINVEGA, LA .
IIE TRANSACTIONS, 1994, 26 (05) :44-55
[13]   A REVIEW OF PRODUCTION PLANNING AND SCHEDULING MODELS IN THE SEMICONDUCTOR INDUSTRY PART I: SYSTEM CHARACTERISTICS, PERFORMANCE EVALUATION AND PRODUCTION PLANNING [J].
UZSOY, R ;
LEE, CY ;
MARTINVEGA, LA .
IIE TRANSACTIONS, 1992, 24 (04) :47-60
[14]  
van den Akker M., 2000, Journal of Scheduling, V3, P333, DOI 10.1002/1099-1425(200011/12)3:6<333::AID-JOS53>3.0.CO
[15]  
2-8
[16]   Minimizing the total completion time on-line on a single machine, using restarts [J].
van Stee, R ;
La Poutré, H .
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2005, 57 (02) :95-129
[17]  
Wei Z., 2011, THESIS
[18]   A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan [J].
Yuan, Jinjiang ;
Fu, Ruyan ;
Ng, C. T. ;
Cheng, T. C. E. .
JOURNAL OF SCHEDULING, 2011, 14 (04) :361-369
[19]   A best on-line algorithm for the single machine parallel-batch scheduling with restricted delivery times [J].
Yuan, Jinjiang ;
Li, Shisheng ;
Tian, Ji ;
Fu, Ruyan .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2009, 17 (02) :206-213
12