Inhalt des Dokuments
Preprint 734-2002
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- List scheduling in order of alpha-points on a single machine
- Author
- Publication
- To appear in a book on Approximation and On-line Algorithms edited by members of the EU-project APPOL.
- Classification
-
not available
- Keywords
-
not available
- Abstract
-
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.
- Source
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe