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 条
[1]   Lower bounds for on-line single-machine scheduling [J].
Epstein, L ;
van Stee, R .
THEORETICAL COMPUTER SCIENCE, 2003, 299 (1-3) :439-450
[2]   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
[3]   Online scheduling on two parallel-batching machines with limited restarts to minimize the makespan [J].
Fu, Ruyan ;
Cheng, T. C. E. ;
Ng, C. T. ;
Yuan, Jinjiang .
INFORMATION PROCESSING LETTERS, 2010, 110 (11) :444-450
[4]   On-line scheduling on a single machine: maximizing the number of early jobs [J].
Hoogeveen, H ;
Potts, CN ;
Woeginger, GJ .
OPERATIONS RESEARCH LETTERS, 2000, 27 (05) :193-197
[5]   A best possible deterministic on-line algorithm for minimizing maximum delivery time on a single machine [J].
Hoogeveen, JA ;
Vestjens, APA .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2000, 13 (01) :56-63
[6]   EFFICIENT ALGORITHMS FOR SCHEDULING SEMICONDUCTOR BURN-IN OPERATIONS [J].
LEE, CY ;
UZSOY, R ;
MARTINVEGA, LA .
OPERATIONS RESEARCH, 1992, 40 (04) :764-775
[7]   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
[8]   Online unbounded batch scheduling on parallel machines with delivery times [J].
Liu, Peihai ;
Lu, Xiwen .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2015, 29 (01) :228-236
[9]   Online Over Time Scheduling on Parallel-Batch Machines: A Survey [J].
Tian J. ;
Fu R. ;
Yuan J. .
Journal of the Operations Research Society of China, 2014, 2 (4) :445-454
[10]   Online scheduling on the unbounded drop-line batch machines to minimize the maximum delivery completion time [J].
Tian, Ji ;
Wang, Qian ;
Fu, Ruyan ;
Yuan, Jinjiang .
THEORETICAL COMPUTER SCIENCE, 2016, 617 :65-68
12