On-line scheduling on a batch machine to minimize makespan with limited restarts

被引：17
作者：
Fu, Ruyan [1 ]
Tian, Ji [1 ]
Yuan, Jinjiang [1 ]
He, Cheng [1 ,2 ]
机构：
[1] Zhengzhou Univ, Dept Math, Zhengzhou 450052, Peoples R China
[2] Informat Engn Univ PLA, Inst Sci, Henan 450051, Peoples R China
来源：
OPERATIONS RESEARCH LETTERS | 2008年 / 36卷 / 02期
基金：
中国国家自然科学基金;
关键词：
on-line scheduling; batch machine; restart; competitive ratio;
D O I：
10.1016/j.orl.2007.07.001
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We study the on-line scheduling on an unbounded batch machine to minimize makespan. In this model, jobs arrive over time and batches are allowed limited restarts. Any batch that contains a job which has already been restarted once cannot be restarted any more. We provide a best possible on-line algorithm for the problem with a competitive ratio 3/2. (C) 2007 Published by Elsevier B.V.
引用
收藏
页码：255 / 258
页数：4
相关论文
共 8 条
[1]  
AKKER MVD, 2003, J SCHEDULING, V3, P333
[2]   Approximation algorithms in batch processing [J].
Deng, XT ;
Poon, CK ;
Zhang, YZ .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2003, 7 (03) :247-257
[3]   Online scheduling in a parallel batch processing system to minimize makespan using restarts [J].
Fu, Ruyan ;
Tian, Ji ;
Yuan, Jinjiang ;
Lin, Yixun .
THEORETICAL COMPUTER SCIENCE, 2007, 374 (1-3) :196-202
[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]   On-line scheduling algorithms for a batch machine with finite capacity [J].
Poon, CK ;
Yu, WC .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2005, 9 (02) :167-186
[6]   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
[7]  
YUAN J, 2007, UNPUB BEST ONLINE AL
[8]  
Zhang GC, 2001, NAV RES LOG, V48, P241, DOI 10.1002/nav.5
1