Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/30935
Title: Semi-online scheduling with known partial information about job sizes on two identical machines
Authors: Cao, Q
Liu, Z
Cheng, TCE 
Keywords: Identical machines
Maximum job
Scheduling
Semi-online
Issue Date: 2011
Publisher: Elsevier
Source: Theoretical computer science, 2011, v. 412, no. 29, p. 3731-3737 How to cite?
Journal: Theoretical computer science 
Abstract: In this paper we consider the semi-online scheduling problem with known partial information about job sizes on two identical machines, where all the jobs have processing times in the interval [p,tp] (p>0,t<1) and the maximum job size is tp. The objective is to minimize the makespan. For 1≤t<43 and t<2, we obtain lower bounds t+12 and 43 on the optimal solution, respectively, which match the upper bounds given by He and Zhang (1999) in [2]. For 43≤t<2, we prove that a lower bound on the optimal solution is max4t+43t+4,2tt+1 and design an algorithm with a competitive ratio equal to this lower bound.
URI: http://hdl.handle.net/10397/30935
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2011.03.032
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

4
Last Week
0
Last month
1
Citations as of Nov 9, 2017

WEB OF SCIENCETM
Citations

3
Last Week
0
Last month
0
Citations as of Nov 15, 2017

Page view(s)

52
Last Week
1
Last month
Checked on Nov 19, 2017

Google ScholarTM

Check

Altmetric



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