direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 07-2010

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Increasing speed scheduling and Flow scheduling
not available
Dynamic Flows, Earliest Arrival Flows, Scheduling with varying Speed, Weighted Sum of Completion Times, Approximation Algorithms
Network 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 (sqrt{3}+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 as [PDF]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe