TU Berlin

Sebastian StillerPublikationen

COGA 5-Wheel

Inhalt des Dokuments

zur Navigation


Increasing speed scheduling and Flow scheduling
Zitatschlüssel StillerWiese2010
Autor Stiller, Sebastian and Wiese, Andreas
Buchtitel Algorithms and Computation (ISAAC 2010)
Seiten 279–290
Jahr 2010
Verlag Springer
Serie Lecture Notes in Computer Science
Institution Technische Universität Berlin
Zusammenfassung Flows and scheduling have been studied intensely, but separately. In many applications a joint optimization model for routing and scheduling is desireable.Therefore, we study flows over time with a demand split into jobs. The objective is to minimize the weighted sum of completion times of these jobs. This is closely related to preemptive scheduling on a single machine with a processing speed increasing over time. For both, flow scheduling and increasing speed scheduling, we provide an EPTAS. Without release dates we can proof a tight approximation factor of $(\sqrt3+1)/2$ for Smith's rule, by fully characterizing the worst case instances.We give exact algorithms for some special cases and a dynamic program for speed functions with a constant number of speeds. We can proof a competitive ratio of 2 for the online version. We also study the class of blind algorithms, i.e., those which schedule without knowledge of the speed function. For both online, and blind algorithm we provide a lower bound.
Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe