Title: An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules
Speaker: Li Minming
Tsinghua University

Date: Friday, April 29, 2005
Time 11-12
Venue: Room 3464, HKUST


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(d nlog n) time. Previous approaches solve this problem by
first computing the optimal continuous solution in O(n3) 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(nlog n) time is
required, hence the algorithm is optimal for fixed d.