TY - GEN

T1 - Precedence-constrained scheduling of malleable jobs with preemption

AU - Makarychev, Konstantin

AU - Panigrahi, Debmalya

N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.

PY - 2014

Y1 - 2014

N2 - Scheduling jobs with precedence constraints on a set of identical machines to minimize the total processing time (makespan) is a fundamental problem in combinatorial optimization. In practical settings such as cloud computing, jobs are often malleable, i.e., can be processed on multiple machines simultaneously. The instantaneous processing rate of a job is a non-decreasing function of the number of machines assigned to it (we call it the processing function). Previous research has focused on practically relevant concave processing functions, which obey the law of diminishing utility and generalize the classical (non-malleable) problem. Our main result is a (2 + ε)-approximation algorithm for concave processing functions (for any ε > 0), which is the best possible under complexity theoretic assumptions. The approximation ratio improves to (1 + ε) for the interesting and practically relevant special case of power functions, i.e., pj (z) = cj·z γ.

AB - Scheduling jobs with precedence constraints on a set of identical machines to minimize the total processing time (makespan) is a fundamental problem in combinatorial optimization. In practical settings such as cloud computing, jobs are often malleable, i.e., can be processed on multiple machines simultaneously. The instantaneous processing rate of a job is a non-decreasing function of the number of machines assigned to it (we call it the processing function). Previous research has focused on practically relevant concave processing functions, which obey the law of diminishing utility and generalize the classical (non-malleable) problem. Our main result is a (2 + ε)-approximation algorithm for concave processing functions (for any ε > 0), which is the best possible under complexity theoretic assumptions. The approximation ratio improves to (1 + ε) for the interesting and practically relevant special case of power functions, i.e., pj (z) = cj·z γ.

UR - http://www.scopus.com/inward/record.url?scp=84904198136&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84904198136&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-43948-7_68

DO - 10.1007/978-3-662-43948-7_68

M3 - Conference contribution

AN - SCOPUS:84904198136

SN - 9783662439470

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 823

EP - 834

BT - Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings

PB - Springer Verlag

T2 - 41st International Colloquium on Automata, Languages, and Programming, ICALP 2014

Y2 - 8 July 2014 through 11 July 2014

ER -