Increasing speed scheduling and Flow scheduling

Sebastian Stiller and Andreas Wiese

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]