An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules

We consider the problem of job scheduling on a variable voltage processor with $d$ discrete voltage/speed levels. We give an algorithm which constructs a minimum energy schedule for $n$ jobs in $O(d n\log n)$ time. Previous approaches solve this problem by first computing the optimal continuous solution in $O(n^3)$ time and then adjusting the speed to discrete levels. In our approach, the optimal discrete solution is characterized and computed directly from the inputs. We also show that $O(n\log n)$ time is required; hence the algorithm is optimal for fixed $d$.