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