Dual Techniques for Scheduling on a Machine with Varying Speed

We study scheduling problems on a machine of varying speed. Assuming a known speed function (given through an oracle) we ask for a cost-efficient scheduling solution. Our main result is a PTAS for minimizing the total weighted completion time on a machine of varying speed. This implies also a PTAS for the closely related problem of scheduling to minimize generalized global cost functions. The key to our results is a re-interpretation 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

.

We also consider a dynamic problem variant in which deciding upon the speed is part of the scheduling problem and we are interested in the tradeoff between scheduling cost and speed-scaling cost, which is typically the energy consumption. We obtain two insightful results: (1) the optimal scheduling order is independent of the energy consumption and (2) the problem can be reduced to the setting where the speed of the machine is fixed, and thus admits a PTAS.