Dual Techniques for Scheduling on a Machine with Varying Speed

We study scheduling problems on a machine with varying speed. Assuming a known speed function we ask for a cost-efficient scheduling solution. Our main result is a polynomial-time approximation scheme (PTAS) for minimizing the total weighted completion time in this setting. This also implies a PTAS for the closely related problem of scheduling to minimize generalized global cost functions, that is, the problem 1||∑ wⱼf(Cⱼ). The key to our results is a reinterpretation of the problem within the well-known two-dimensional Gantt chart: instead of the standard approach of scheduling in the time dimension, we construct scheduling solutions in the weight dimension. This allows structural simplifications of the instance and optimal solutions, based on which we can defer the concern of speed to the evaluation of cost in a dynamic programming framework. We also consider a dynamic problem variant, where the decision upon the speed is part of the problem and we are interested in the trade-off between scheduling cost and speed-scaling cost, which is typically the energy consumption. We observe that the optimal order is independent of the energy consumption and that the problem can be reduced to the setting where the speed of the machine is fixed, and thus admits a PTAS. Furthermore, we provide a fully polynomial-time approximation scheme for the NP-hard problem variant in which the machine can run only at a fixed number of discrete speeds. Finally, we show how our results can be used to obtain a (2+ε)-approximation for scheduling preemptive jobs with release dates on multiple identical parallel machines.