Approximation algorithms for scheduling malleable tasks under precedence constraints

Renaud Lepère; Denis Trystram; Gerhard Woeginger

doi:10.1007/3-540-44676-1_12

Approximation algorithms for scheduling malleable tasks under precedence constraints

Renaud Lepère, Denis Trystram, Gerhard Woeginger

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

31 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 language	English
Title of host publication	Algorithms — ESA 2001
Subtitle of host publication	9th Annual European Symposium Århus, Denmark, August 28–31, 2001 Proceedings
Editors	Friedhelm Meyer auf der Heide
Publisher	Springer
Pages	146-157
ISBN (Electronic)	978-3-540-44676-7
ISBN (Print)	978-3-540-42493-2
DOIs	https://doi.org/10.1007/3-540-44676-1_12
Publication status	Published - 2001
Event	9th Annual European Symposium on Algorithms, ESA 2001 - Aarhus, Denmark Duration: 28 Aug 2001 → 31 Aug 2001 Conference number: 9

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	2161
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th Annual European Symposium on Algorithms, ESA 2001
Abbreviated title	ESA
Country/Territory	Denmark
City	Aarhus
Period	28/08/01 → 31/08/01

Keywords

Approximation algorithm
Time slot
Allotment problem
Critical path
Precedence constraints

Access to Document

10.1007/3-540-44676-1_12

Cite this

Lepère, R., Trystram, D., & Woeginger, G. (2001). Approximation algorithms for scheduling malleable tasks under precedence constraints. In F. Meyer auf der Heide (Ed.), Algorithms — ESA 2001: 9th Annual European Symposium Århus, Denmark, August 28–31, 2001 Proceedings (pp. 146-157). (Lecture Notes in Computer Science; Vol. 2161). Springer. https://doi.org/10.1007/3-540-44676-1_12

@inproceedings{306a64f7e43e439e9dbdd1857aa71715,

title = "Approximation algorithms for scheduling malleable tasks under precedence constraints",

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.",

keywords = "Approximation algorithm, Time slot, Allotment problem, Critical path, Precedence constraints",

author = "Renaud Lep{\`e}re and Denis Trystram and Gerhard Woeginger",

year = "2001",

doi = "10.1007/3-540-44676-1_12",

language = "English",

isbn = "978-3-540-42493-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "146--157",

editor = "{Meyer auf der Heide}, Friedhelm",

booktitle = "Algorithms — ESA 2001",

address = "Netherlands",

note = "9th Annual European Symposium on Algorithms, ESA 2001, ESA ; Conference date: 28-08-2001 Through 31-08-2001",

}

Lepère, R, Trystram, D & Woeginger, G 2001, Approximation algorithms for scheduling malleable tasks under precedence constraints. in F Meyer auf der Heide (ed.), Algorithms — ESA 2001: 9th Annual European Symposium Århus, Denmark, August 28–31, 2001 Proceedings. Lecture Notes in Computer Science, vol. 2161, Springer, pp. 146-157, 9th Annual European Symposium on Algorithms, ESA 2001, Aarhus, Denmark, 28/08/01. https://doi.org/10.1007/3-540-44676-1_12

Approximation algorithms for scheduling malleable tasks under precedence constraints. / Lepère, Renaud; Trystram, Denis; Woeginger, Gerhard.

Algorithms — ESA 2001: 9th Annual European Symposium Århus, Denmark, August 28–31, 2001 Proceedings. ed. / Friedhelm Meyer auf der Heide. Springer, 2001. p. 146-157 (Lecture Notes in Computer Science; Vol. 2161).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Approximation algorithms for scheduling malleable tasks under precedence constraints

AU - Lepère, Renaud

AU - Trystram, Denis

AU - Woeginger, Gerhard

N1 - Conference code: 9

PY - 2001

Y1 - 2001

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

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

KW - Approximation algorithm

KW - Time slot

KW - Allotment problem

KW - Critical path

KW - Precedence constraints

U2 - 10.1007/3-540-44676-1_12

DO - 10.1007/3-540-44676-1_12

M3 - Conference contribution

SN - 978-3-540-42493-2

T3 - Lecture Notes in Computer Science

SP - 146

EP - 157

BT - Algorithms — ESA 2001

A2 - Meyer auf der Heide, Friedhelm

PB - Springer

T2 - 9th Annual European Symposium on Algorithms, ESA 2001

Y2 - 28 August 2001 through 31 August 2001

ER -

Approximation algorithms for scheduling malleable tasks under precedence constraints

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this