Approximation algorithms for scheduling malleable tasks under precedence constraints

Renaud Lepère, Denis Trystram, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

48 Citations (Scopus)

Abstract

This work presents approximation algorithms for scheduling the tasks of a parallel application that are subject to precedence constraints. The considered tasks are malleable which means that they may be executed on a varying number of processors in parallel. The considered objective criterion is the makespan, i.e., the largest task completion time.

We demonstrate a close relationship between this scheduling problem and one of its subproblems, the allotment problem. By exploiting this relationship, we design a polynomial time approximation algorithm with performance guarantee arbitrarily close to (3+√5)/ 2≈2.61803 for the special case of series parallel precedence constraints and for the special case of precedence constraints of bounded width. These special cases cover the important situation of tree structured precedence constraints. For the general case with arbitrary precedence constraints, we give a polynomial time approximation algorithm with performance guarantee 3+√5 ≈5.23606.
Original languageEnglish
Pages (from-to)613-627
JournalInternational journal of foundations of computer science
Volume13
Issue number4
DOIs
Publication statusPublished - 2002

Keywords

  • Parallel computing
  • Scheduling
  • Malleable tasks
  • Precedence constraints
  • Series parallel order
  • Bounded width
  • Approximation algorithm
  • Project management
  • Discrete time-cost tradeoff problem

Fingerprint

Dive into the research topics of 'Approximation algorithms for scheduling malleable tasks under precedence constraints'. Together they form a unique fingerprint.

Cite this