TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen2008

COGA 5-Wheel


zur Navigation

Preprints 2008

Online Scheduling with Bounded Migration
Zitatschlüssel Report-020-2008
Autor Peter Sanders and Naveen Sivadasan and Martin Skutella
Jahr 2008
Nummer 020
Notiz Submitted. An extended abstract appeared in J. Diaz, J. Karhumäki, A. Lepistö, and D. Sannella (eds.): Automata, Languages and Programming, Lecture Notes in Computer Science 3142, Springer-Verlag: Berlin, 2004, 1111-1122, Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP'04).
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung Consider the classical online scheduling problem where jobs that arrive one by one are assigned to identical parallel machines with the objective of minimizing the makespan. We generalize this problem by allowing the current assignment to be changed whenever a new job arrives, subject to the constraint that the total size of moved jobs is bounded by β times the size of the arriving job. For small values of β, we obtain several simple online algorithms with constant competitive ratio. We also present a linear time `online approximation scheme', that is, a family of online algorithms with competitive ratio $1+\epsilon$ and constant migration factor $\beta(\epsilon)$, for any fixed $\epsilon>0$.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe