TU Berlin

Sebastian StillerPublikationen

COGA 5-Wheel

Page Content

to Navigation

There is no English translation for this web page.


Increasing speed scheduling and Flow scheduling
Citation key StillerWiese2010
Author Stiller, Sebastian and Wiese, Andreas
Title of Book Algorithms and Computation (ISAAC 2010)
Pages 279–290
Year 2010
Publisher Springer
Series Lecture Notes in Computer Science
Institution Technische Universität Berlin
Abstract 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 entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe