An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules

Abstract 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 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.

Authors

• Minming Li
• F. Frances Yao

Keywords

No keywords are indexed for this paper.