Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/21914
Title: Online scheduling on two parallel-batching machines with limited restarts to minimize the makespan
Authors: Fu, R
Cheng, TCE 
Ng, CT 
Yuan, J
Keywords: Analysis of algorithm
Competitive ratio
Limited restart
Online scheduling
Parallel-batching machines
Issue Date: 2010
Source: Information processing letters, 2010, v. 110, no. 11, p. 444-450 How to cite?
Journal: Information Processing Letters 
Abstract: We study online scheduling on two unbounded parallel-batching machines with limited restarts to minimize the makespan. In this system jobs arrive over time and a batch can be restarted if and only if all the jobs in it have never been restarted. To tackle this difficult problem, we make the second-restart assumption whereby we can only interrupt a running batch B at time t if both machines are busy at time t and batch B has a later starting time than the other running batch. For this case, we provide a best online algorithm with a competitive ratio ?3+12 ≈ 1.366. For the general problem, we show that no online algorithms can have a competitive ratio less than 1.298, leaving a gap from 1.298 to 1.366.
URI: http://hdl.handle.net/10397/21914
ISSN: 0020-0190
DOI: 10.1016/j.ipl.2010.04.008
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 Nov 7, 2018

WEB OF SCIENCETM
Citations

5
Last Week
0
Last month
0
Citations as of Nov 15, 2018

Page view(s)

85
Last Week
0
Last month
Citations as of Nov 12, 2018

Google ScholarTM

Check

Altmetric


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