TY - GEN
T1 - Scheduling Parallel Jobs Online with Convex and Concave Parallelizability
AU - Ebrahimi, Roozbeh
AU - McCauley, Samuel
AU - Moseley, Benjamin
N1 - Full text of this publication does not contain sufficient affiliation information. Research Unit(s) information for this record is based on his previous affiliation.
PY - 2015
Y1 - 2015
N2 - Online scheduling of parallelizable jobs has received a significant amount of attention recently. Scalable algorithms are known-that is, algorithms that are (1+ε)-speed O(1)-competitive for any fixed ε > 0. Previous research has focused on the case where each job's parallelizability can be expressed as a concave speedup curve. However, there are cases where a job's speedup curve can be convex. Considering convex speedup curves has received attention in the offline setting, but, to date, there are no positive results in the online model. In this work, we consider scheduling jobs with convex or concave speedup curves for the first time in the online setting. We give a new algorithm that is (1+ε)-speed O(1)-competitive. There are strong lower bounds on the competitive ratio if the algorithm is not given resource augmentation over the adversary, and thus this is essentially the best positive result one can show for this setting.
AB - Online scheduling of parallelizable jobs has received a significant amount of attention recently. Scalable algorithms are known-that is, algorithms that are (1+ε)-speed O(1)-competitive for any fixed ε > 0. Previous research has focused on the case where each job's parallelizability can be expressed as a concave speedup curve. However, there are cases where a job's speedup curve can be convex. Considering convex speedup curves has received attention in the offline setting, but, to date, there are no positive results in the online model. In this work, we consider scheduling jobs with convex or concave speedup curves for the first time in the online setting. We give a new algorithm that is (1+ε)-speed O(1)-competitive. There are strong lower bounds on the competitive ratio if the algorithm is not given resource augmentation over the adversary, and thus this is essentially the best positive result one can show for this setting.
KW - Online scheduling
KW - Convex and concave parallelizability
KW - Competitive analysis
UR - http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=LinksAMR&SrcApp=PARTNER_APP&DestLinkType=FullRecord&DestApp=WOS&KeyUT=000374051900016
U2 - 10.1007/978-3-319-28684-6_16
DO - 10.1007/978-3-319-28684-6_16
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 978-3-319-28683-9
T3 - Lecture Notes in Computer Science
SP - 183
EP - 195
BT - Approximation and Online Algorithms
A2 - Sanità, Laura
A2 - Skutella, Martin
PB - Springer
CY - Cham
T2 - 13th International Workshop on Approximation and Online Algorithms (WAOA)
Y2 - 17 September 2015 through 18 September 2015
ER -