TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen1997

COGA 5-Wheel


zur Navigation

Preprints 1997

Random-Based Scheduling: New Approximations and LP Lower Bounds
Zitatschlüssel Report-549-1997
Autor Schulz, Andreas S. and Skutella, Martin
Jahr 1997
Nummer 549
Notiz In Jos\é Rolim (ed.): Randomization and Approximation Techniques in Computer Science, Lecture Notes in Computer Science 1269, Springer-Verlag: Berlin, 1997, pp. 119-133, Proceedings of the 1st International Symposium on Randomization and Approximation Techniques in Computer Science (<A HREF=
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung Three characteristics encountered frequently in real-world machine scheduling are jobs released over time, precedence constraints between jobs, and average performance optimization. The general constrained one-machine scheduling problem to minimize the average weighted completion time not only captures these features, but also is an important building block for more complex problems involving multiple machines. In this context, the conversion of preemptive to nonpreemptive schedules has been established as a strong and useful tool for the design of approximation algorithms. The preemptive problem is already NP-hard, but one can generate good preemptive schedules from LP relaxations in time-indexed variables. However, a straightforward combination of these two components does not directly lead to improved approximations. By showing schedules in slow motion, we introduce a new point of view on the generation of preemptive schedules from LP-solutions which also enables us to give a better analysis. Specifically, this leads to a randomized approximation algorithm for the general constrained one-machine scheduling problem with expected performance guarantee $e$. This improves upon the best previously known worst-case bound of $3$. In the process, we also give randomized algorithms for related problems involving precedences that asymptotically match the best previously known performance guarantees. In addition, by exploiting a different technique, we give a simple $3/2$-approxima\-tion algorithm for unrelated parallel machine scheduling to minimize the average weighted completion time. It relies on random machine assignments where these random assignments are again guided by an optimum solution to an LP relaxation. For the special case of identical parallel machines, this algorithm is as simple as the one of Kawaguchi and Kyan, but allows for a remarkably simpler analysis. Interestingly, its derandomized version actually is the algorithm of Kawaguchi and Kyan.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe