Approximation algorithms for scheduling malleable tasks under precedence constraints

Renaud Lepère, Denis Trystram, Gerhard Woeginger

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

28 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
Title of host publicationAlgorithms — ESA 2001
Subtitle of host publication9th Annual European Symposium Århus, Denmark, August 28–31, 2001 Proceedings
EditorsFriedhelm Meyer auf der Heide
PublisherSpringer
Pages146-157
ISBN (Electronic)978-3-540-44676-7
ISBN (Print)978-3-540-42493-2
DOIs
Publication statusPublished - 2001
Event9th Annual European Symposium on Algorithms, ESA 2001 - Aarhus, Denmark
Duration: 28 Aug 200131 Aug 2001
Conference number: 9

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume2161
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th Annual European Symposium on Algorithms, ESA 2001
Abbreviated titleESA
CountryDenmark
CityAarhus
Period28/08/0131/08/01

Keywords

  • Approximation algorithm
  • Time slot
  • Allotment problem
  • Critical path
  • Precedence constraints

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

Cite this