TY - JOUR
T1 - Online scheduling on two uniform machines subject to eligibility constraints
AU - Lee, Kangbok
AU - Leung, Joseph Y.T.
AU - Pinedo, Michael L.
N1 - Funding Information:
Work of the first author was supported by the Korea Research Foundation Grant KRF-2007-357-D00270. Work of the second author was supported in part by the NSF Grant DMI-0556010. Work of the third author was supported in part by the NSF Grant DMI-0555999.
PY - 2009/9/6
Y1 - 2009/9/6
N2 - We consider the online scheduling of a set of jobs on two uniform machines with the makespan as objective. The jobs are presented in a list. We consider two different eligibility constraint set assumptions, namely (i) arbitrary eligibility constraints and (ii) Grade of Service (GoS) eligibility constraints. In the first case, we prove that the High Speed Machine First (HSF) algorithm, which assigns jobs to the eligible machine that has the highest speed, is optimal. With regard to the second case, we point out an error in [M. Liu et al., Online scheduling on two uniform machines to minimize the makespan, Theoretical Computer Science 410 (21-23) (2009) 2099-2109]; we then provide tighter lower bounds and present algorithms with worst-case analysis for various ranges of machine speeds.
AB - We consider the online scheduling of a set of jobs on two uniform machines with the makespan as objective. The jobs are presented in a list. We consider two different eligibility constraint set assumptions, namely (i) arbitrary eligibility constraints and (ii) Grade of Service (GoS) eligibility constraints. In the first case, we prove that the High Speed Machine First (HSF) algorithm, which assigns jobs to the eligible machine that has the highest speed, is optimal. With regard to the second case, we point out an error in [M. Liu et al., Online scheduling on two uniform machines to minimize the makespan, Theoretical Computer Science 410 (21-23) (2009) 2099-2109]; we then provide tighter lower bounds and present algorithms with worst-case analysis for various ranges of machine speeds.
KW - Competitive ratio
KW - Eligibility constraints
KW - Grade of service eligibility
KW - Online scheduling
KW - Uniform machines
UR - http://www.scopus.com/inward/record.url?scp=68249084307&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=68249084307&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2009.06.032
DO - 10.1016/j.tcs.2009.06.032
M3 - Article
AN - SCOPUS:68249084307
SN - 0304-3975
VL - 410
SP - 3975
EP - 3981
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 38-40
ER -