Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/23601
Title: A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan
Authors: Yuan, J
Fu, R
Ng, CT 
Cheng, TCE 
Issue Date: 2011
Source: Journal of scheduling, 2011, v. 14, no. 4, p. 361-369
Abstract: We consider online scheduling with restarts in an unbounded parallel-batch processing system to minimize the makespan. By online we mean that jobs arrive over time and all the information on a job is unknown before its arrival time (release date) and restart means that a running batch may be interrupted, losing all the work done on it, and the jobs in the interrupted batch are released and become independently unscheduled jobs. It is known in the literature that the considered problem has no online algorithm with a competitive ratio less than (5-√5)/2.We give an online algorithm for the considered problem with a competitive ratio (5 -√5)/2 ≈ 1.382.
Keywords: Competitive ratio
Online algorithm
Parallel-batch scheduling
Restart
Publisher: Springer
Journal: Journal of scheduling 
ISSN: 1094-6136
EISSN: 1099-1425
DOI: 10.1007/s10951-010-0172-2
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

14
Last Week
0
Last month
0
Citations as of Sep 8, 2020

WEB OF SCIENCETM
Citations

12
Last Week
0
Last month
Citations as of Sep 18, 2020

Page view(s)

155
Last Week
0
Last month
Citations as of Sep 14, 2020

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.