Approximation algorithms for scheduling malleable tasks under precedence constraints

Renaud Lepère, Denis Trystram, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

49 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.
  • Approximation algorithms for scheduling malleable tasks under precedence constraints

    Lepère, R., Trystram, D. & Woeginger, G., 2001, Algorithms — ESA 2001: 9th Annual European Symposium Århus, Denmark, August 28–31, 2001 Proceedings. Meyer auf der Heide, F. (ed.). Springer, p. 146-157 (Lecture Notes in Computer Science; vol. 2161).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    31 Citations (Scopus)

Cite this