TY - JOUR
T1 - Online C-benevolent job scheduling on multiple machines
AU - Yu, Ge
AU - Jacobson, Sheldon H.
N1 - Funding Information:
Acknowledgements This research has been supported in part by the Air Force Office of Scientific Research under Grant No. FA9550-15-1-0100. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the United States Government, or the Air Force Office of Scientific Research.
Publisher Copyright:
© 2017, Springer-Verlag GmbH Germany.
Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.
PY - 2018/3/1
Y1 - 2018/3/1
N2 - We consider scheduling a sequence of C-benevolent jobs on multiple homogeneous machines. For two machines, we propose a 2-competitive Cooperative Greedy algorithm and provide a lower bound of 2 for the competitive ratio of any deterministic online scheduling algorithms on two machines. For multiple machines, we propose a Pairing-m Greedy algorithm, which is deterministic 2-competitive for even number of machines and randomized (2 + 2 / m) -competitive for odd number of machines. We provide a lower bound of 1.436 for the competitive ratio of any deterministic online scheduling algorithms on three machines, which is the best known lower bound for competitive ratios of deterministic scheduling algorithms on three machines.
AB - We consider scheduling a sequence of C-benevolent jobs on multiple homogeneous machines. For two machines, we propose a 2-competitive Cooperative Greedy algorithm and provide a lower bound of 2 for the competitive ratio of any deterministic online scheduling algorithms on two machines. For multiple machines, we propose a Pairing-m Greedy algorithm, which is deterministic 2-competitive for even number of machines and randomized (2 + 2 / m) -competitive for odd number of machines. We provide a lower bound of 1.436 for the competitive ratio of any deterministic online scheduling algorithms on three machines, which is the best known lower bound for competitive ratios of deterministic scheduling algorithms on three machines.
KW - Approximation algorithm
KW - C-benevolent jobs
KW - Online scheduling
UR - http://www.scopus.com/inward/record.url?scp=85028962418&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85028962418&partnerID=8YFLogxK
U2 - 10.1007/s11590-017-1191-0
DO - 10.1007/s11590-017-1191-0
M3 - Article
AN - SCOPUS:85028962418
VL - 12
SP - 251
EP - 263
JO - Optimization Letters
JF - Optimization Letters
SN - 1862-4472
IS - 2
ER -