Precedence-constrained scheduling of malleable jobs with preemption

Konstantin Makarychev, Debmalya Panigrahi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations


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 γ.

Original languageEnglish (US)
Title of host publicationAutomata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings
PublisherSpringer Verlag
Number of pages12
EditionPART 1
ISBN (Print)9783662439470
StatePublished - 2014
Event41st International Colloquium on Automata, Languages, and Programming, ICALP 2014 - Copenhagen, Denmark
Duration: Jul 8 2014Jul 11 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume8572 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other41st International Colloquium on Automata, Languages, and Programming, ICALP 2014

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Precedence-constrained scheduling of malleable jobs with preemption'. Together they form a unique fingerprint.

Cite this