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(dn log n) time. Previous approaches solve this problem by first computing the optimal continuous solution in O(n³) 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.