Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/11224
Title: Online scheduling on unbounded parallel-batch machines with incompatible job families
Authors: Tian, J
Cheng, TCE 
Ng, CT 
Yuan, J
Keywords: Competitive ratio
Incompatible job families
Online scheduling
Parallel-batch machines
Issue Date: 2011
Publisher: Elsevier
Source: Theoretical computer science, 2011, v. 412, no. 22, p. 2380-2386 How to cite?
Journal: Theoretical computer science 
Abstract: We consider online scheduling on m parallel-batch machines where the batch capacity is unbounded and the jobs belong to m incompatible job families. By incompatible job families, we mean that jobs from different families cannot be processed together in the same batch. The processing time of a job becomes known only upon its arrival. The objective is to minimize the makespan. The problem is difficult to solve so we consider the case where the number of families is equal to the number of machines. We give a lower bound 5+12≈1.618 on the competitive ratio of any online algorithm for this restricted problem. We also provide an online algorithm Hm(θ), where θ∈(0,1) is a parameter, and show that its competitive ratio is no less than 1+105≈1.632. When m=2 or under the condition that jobs belonging to the same family have identical processing times, we show that Hm(α), where α=5-12, is a best possible online algorithm. When m<3, we prove that Hm(β), where β=2-1, has a competitive ratio no greater than 1+1β+1≈1.707.
URI: http://hdl.handle.net/10397/11224
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2011.01.023
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

3
Last Week
0
Last month
0
Citations as of Sep 11, 2017

WEB OF SCIENCETM
Citations

2
Last Week
0
Last month
0
Citations as of Sep 13, 2017

Page view(s)

48
Last Week
2
Last month
Checked on Sep 17, 2017

Google ScholarTM

Check

Altmetric



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