direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

There is no English translation for this web page.

Publications

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 [1]
------ Links: ------

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.
Copyright TU Berlin 2008