TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen2002

COGA 5-Wheel


zur Navigation

Preprints 2002

List scheduling in order of α-points on a single machine
Zitatschlüssel Report-734-2002
Autor Martin Skutella
Jahr 2002
Nummer 734
Notiz To appear in a book on Approximation and On-line Algorithms edited by members of the EU-project APPOL.
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung Many approximation results for single machine scheduling problems rely on the conversion of preemptive schedules into (preemptive or non-preemptive) solutions. The initial preemptive schedule is usually an optimal solution to a combinatorial relaxation or a linear programming relaxation of the scheduling problem under consideration. It therefore provides a lower bound on the optimal objective function value. However, it also contains structural information which is useful for the construction of provably good feasible schedules. In this context, list scheduling in order of so-called α-points has evolved as an important and successful tool. We give a survey and a uniform presentation of several approximation results for single machine scheduling with total weighted completion time objective from the last years which rely on the concept of α-points.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe