Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/21186
Title: Best semi-online algorithms for unbounded parallel batch scheduling
Authors: Yuan, J
Ng, CT 
Cheng, TCE 
Keywords: Competitive ratio
Information in advance
Online algorithm
Parallel batch scheduling
Issue Date: 2011
Source: Discrete applied mathematics, 2011, v. 159, no. 8, p. 838-847 How to cite?
Journal: Discrete Applied Mathematics 
Abstract: We consider semi-online scheduling of an unbounded parallel batch machine to minimize the makespan where, at the present time instant t, information on the first longest job arriving after t is known. In this paper online means that jobs arrive over time, J*(t) denotes the first longest job arriving after t, and p*(t) and r*(t) denote the processing time and arrival time of J*(t), respectively. Given information p*(t), we present an online algorithm with a competitive ratio (5-5)2≈1.382, and show that the algorithm is the best possible; furthermore, this algorithm generates at most two batches. This algorithm is also the best possible given information J*(t). Given information r*(t), we present an online algorithm with a competitive ratio 32, and show that any online algorithm cannot have a competitive ratio less than 33≈1.442; furthermore, this algorithm generates at most three batches. Given information r*(t) with the restriction that an online algorithm generates at most two batches, we present an online algorithm with a competitive ratio (5+1)2≈1.618, and show that the algorithm is the best possible.
URI: http://hdl.handle.net/10397/21186
ISSN: 0166-218X
DOI: 10.1016/j.dam.2011.01.003
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

6
Last Week
1
Last month
0
Citations as of Dec 7, 2017

WEB OF SCIENCETM
Citations

4
Last Week
0
Last month
0
Citations as of Dec 9, 2017

Page view(s)

76
Last Week
1
Last month
Checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric



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