Online Scheduling on a Parallel Batch Machine with Delivery Times and Limited Restarts

被引：5
作者：
Liu, Hai-Ling [1 ,2 ]
Lu, Xi-Wen [1 ]
机构：
[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
来源：
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA | 2022年 / 10卷 / 01期
基金：
中国国家自然科学基金;
关键词：
Online scheduling; Parallel batch; Limited restart; Delivery time;
D O I：
10.1007/s40305-021-00356-7
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
The online scheduling on an unbounded parallel batch machine with delivery times and limited restarts is studied in this paper. Here, online means that jobs arrive over time and the characteristics of a job become known until it arrives. Limited restarts mean that once a running batch contains at least one restarted job, it cannot be restarted again. The goal is to minimize the time by which all jobs have been delivered. We consider a restricted model that the delivery time of each job is no more than its processing time. We present a best possible online algorithm with a competitive ratio of 3/2 for the problem.
引用
收藏
页码：113 / 131
页数：19
相关论文
共 11 条
[1]   On-line scheduling on a batch machine to minimize makespan with limited restarts [J].
Fu, Ruyan ;
Tian, Ji ;
Yuan, Jinjiang ;
He, Cheng .
OPERATIONS RESEARCH LETTERS, 2008, 36 (02) :255-258
[2]   Supply chain scheduling: Batching and delivery [J].
Hall, NG ;
Potts, CN .
OPERATIONS RESEARCH, 2003, 51 (04) :566-584
[3]   EFFICIENT ALGORITHMS FOR SCHEDULING SEMICONDUCTOR BURN-IN OPERATIONS [J].
LEE, CY ;
UZSOY, R ;
MARTINVEGA, LA .
OPERATIONS RESEARCH, 1992, 40 (04) :764-775
[4]   Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart [J].
Liu, Hailing ;
Yuan, Jinjiang ;
Li, Wenjie .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 31 (04) :1609-1622
[5]   SCHEDULING PARALLEL MACHINES ONLINE [J].
SHMOYS, DB ;
WEIN, J ;
WILLIAMSON, DP .
SIAM JOURNAL ON COMPUTING, 1995, 24 (06) :1313-1331
[6]   The coordination of transportation and batching scheduling [J].
Tang, Lixin ;
Gong, Hua .
APPLIED MATHEMATICAL MODELLING, 2009, 33 (10) :3854-3862
[7]   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
[8]  
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
[9]  
2-8
[10]   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
12