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 
Keywords: Competitive ratio
Online algorithm
Parallel-batch scheduling
Restart
Issue Date: 2011
Publisher: Springer
Source: Journal of scheduling, 2011, v. 14, no. 4, p. 361-369 How to cite?
Journal: Journal of scheduling 
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.
URI: http://hdl.handle.net/10397/23601
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

6
Last Week
0
Last month
0
Citations as of Aug 21, 2017

WEB OF SCIENCETM
Citations

6
Last Week
1
Last month
Citations as of Aug 20, 2017

Page view(s)

64
Last Week
1
Last month
Checked on Aug 20, 2017

Google ScholarTM

Check

Altmetric



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