On the approximability of average completion time scheduling under precedence constraints

Gerhard J. Woeginger

doi:10.1007/3-540-48224-5_72

On the approximability of average completion time scheduling under precedence constraints

Gerhard J. Woeginger

Discrete Mathematics and Mathematical Programming

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

10 Citations (Scopus)

2 Downloads (Pure)

Abstract

We consider the scheduling problem of minimizing the average weighted job completion time on a single machine under precedence constraints. We show that this problem with arbitrary job weights, the special case of the problem where all job weights are one, and several other special cases of the problem all have the same approximability threshold with respect to polynomial time approximation algorithms. Moreover, for the special case of interval order precedence constraints and for the special case of convex bipartite precedence constraints, we give a polynomial time approximation algorithm with worst case performance guarantee arbitrarily close to the golden ratio 12 (1+5 – √ )≈1.61803.

Original language	English
Title of host publication	Automata, Languages and Programming
Subtitle of host publication	28th International Colloquium, ICALP 2001 Crete, Greece, July 8–12, 2001 Proceedings
Editors	Fernando Orejas, Paul G. Spivakis, Jan van Leeuwen
Publisher	Springer
Pages	887-897
ISBN (Electronic)	978-3-540-48224-6
ISBN (Print)	978-3-540-42287-7
DOIs	https://doi.org/10.1007/3-540-48224-5_72
Publication status	Published - 2001
Event	28th International Colloquium on Automata, Languages, and Programming, ICALP 2001 - Crete, Greece Duration: 8 Jul 2001 → 12 Jul 2001 Conference number: 28

Publication series

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

Conference

Conference	28th International Colloquium on Automata, Languages, and Programming, ICALP 2001
Abbreviated title	ICALP
Country/Territory	Greece
City	Crete
Period	8/07/01 → 12/07/01

Keywords

METIS-202688

Access to Document

10.1007/3-540-48224-5_72

Cite this

Woeginger, G. J. (2001). On the approximability of average completion time scheduling under precedence constraints. In F. Orejas, P. G. Spivakis, & J. van Leeuwen (Eds.), Automata, Languages and Programming: 28th International Colloquium, ICALP 2001 Crete, Greece, July 8–12, 2001 Proceedings (pp. 887-897). (Lecture Notes in Computer Science; Vol. 2076). Springer. https://doi.org/10.1007/3-540-48224-5_72

@inproceedings{32c77f548fbe44dab9de7db2005df4e3,

title = "On the approximability of average completion time scheduling under precedence constraints",

abstract = "We consider the scheduling problem of minimizing the average weighted job completion time on a single machine under precedence constraints. We show that this problem with arbitrary job weights, the special case of the problem where all job weights are one, and several other special cases of the problem all have the same approximability threshold with respect to polynomial time approximation algorithms. Moreover, for the special case of interval order precedence constraints and for the special case of convex bipartite precedence constraints, we give a polynomial time approximation algorithm with worst case performance guarantee arbitrarily close to the golden ratio 12 (1+5 – √ )≈1.61803.",

keywords = "METIS-202688",

author = "Woeginger, {Gerhard J.}",

year = "2001",

doi = "10.1007/3-540-48224-5_72",

language = "English",

isbn = "978-3-540-42287-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "887--897",

editor = "Fernando Orejas and Spivakis, {Paul G.} and {van Leeuwen}, Jan",

booktitle = "Automata, Languages and Programming",

address = "Germany",

note = "28th International Colloquium on Automata, Languages, and Programming, ICALP 2001, ICALP ; Conference date: 08-07-2001 Through 12-07-2001",

}

Woeginger, GJ 2001, On the approximability of average completion time scheduling under precedence constraints. in F Orejas, PG Spivakis & J van Leeuwen (eds), Automata, Languages and Programming: 28th International Colloquium, ICALP 2001 Crete, Greece, July 8–12, 2001 Proceedings. Lecture Notes in Computer Science, vol. 2076, Springer, pp. 887-897, 28th International Colloquium on Automata, Languages, and Programming, ICALP 2001, Crete, Greece, 8/07/01. https://doi.org/10.1007/3-540-48224-5_72

On the approximability of average completion time scheduling under precedence constraints. / Woeginger, Gerhard J.
Automata, Languages and Programming: 28th International Colloquium, ICALP 2001 Crete, Greece, July 8–12, 2001 Proceedings. ed. / Fernando Orejas; Paul G. Spivakis; Jan van Leeuwen. Springer, 2001. p. 887-897 (Lecture Notes in Computer Science; Vol. 2076).

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

TY - GEN

T1 - On the approximability of average completion time scheduling under precedence constraints

AU - Woeginger, Gerhard J.

N1 - Conference code: 28

PY - 2001

Y1 - 2001

N2 - We consider the scheduling problem of minimizing the average weighted job completion time on a single machine under precedence constraints. We show that this problem with arbitrary job weights, the special case of the problem where all job weights are one, and several other special cases of the problem all have the same approximability threshold with respect to polynomial time approximation algorithms. Moreover, for the special case of interval order precedence constraints and for the special case of convex bipartite precedence constraints, we give a polynomial time approximation algorithm with worst case performance guarantee arbitrarily close to the golden ratio 12 (1+5 – √ )≈1.61803.

AB - We consider the scheduling problem of minimizing the average weighted job completion time on a single machine under precedence constraints. We show that this problem with arbitrary job weights, the special case of the problem where all job weights are one, and several other special cases of the problem all have the same approximability threshold with respect to polynomial time approximation algorithms. Moreover, for the special case of interval order precedence constraints and for the special case of convex bipartite precedence constraints, we give a polynomial time approximation algorithm with worst case performance guarantee arbitrarily close to the golden ratio 12 (1+5 – √ )≈1.61803.

KW - METIS-202688

U2 - 10.1007/3-540-48224-5_72

DO - 10.1007/3-540-48224-5_72

M3 - Conference contribution

SN - 978-3-540-42287-7

T3 - Lecture Notes in Computer Science

SP - 887

EP - 897

BT - Automata, Languages and Programming

A2 - Orejas, Fernando

A2 - Spivakis, Paul G.

A2 - van Leeuwen, Jan

PB - Springer

T2 - 28th International Colloquium on Automata, Languages, and Programming, ICALP 2001

Y2 - 8 July 2001 through 12 July 2001

ER -

Woeginger GJ. On the approximability of average completion time scheduling under precedence constraints. In Orejas F, Spivakis PG, van Leeuwen J, editors, Automata, Languages and Programming: 28th International Colloquium, ICALP 2001 Crete, Greece, July 8–12, 2001 Proceedings. Springer. 2001. p. 887-897. (Lecture Notes in Computer Science). doi: 10.1007/3-540-48224-5_72

On the approximability of average completion time scheduling under precedence constraints

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this