Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/31678
Title: Online scheduling on unbounded parallel-batch machines to minimize the makespan
Authors: Tian, J
Cheng, TCE 
Ng, CT 
Yuan, J
Keywords: Algorithms
Competitive ratio
Makespan
Online scheduling
Parallel-batch machines
Issue Date: 2009
Source: Information processing letters, 2009, v. 109, no. 21-22, p. 1211-1215 How to cite?
Journal: Information Processing Letters 
Abstract: We consider online scheduling on m parallel-batch machines to minimize the makespan where the batch capacity is unbounded. The processing time of a job becomes known only upon its arrival. We give an improved lower bound 1 + αm on the competitive ratio, where αm is the positive solution of the equation αm 2 + m αm - 1 = 0, and establish a best possible online algorithm matching this lower bound. We also provide a new lower bound 3/2 on the competitive ratio for dense-algorithms, and present a best possible dense-algorithm matching this lower bound.
URI: http://hdl.handle.net/10397/31678
ISSN: 0020-0190
DOI: 10.1016/j.ipl.2009.08.008
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

20
Last Week
0
Last month
1
Citations as of Dec 1, 2017

WEB OF SCIENCETM
Citations

16
Last Week
0
Last month
0
Citations as of Sep 29, 2017

Page view(s)

58
Last Week
2
Last month
Checked on Dec 11, 2017

Google ScholarTM

Check

Altmetric



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