Journal
SIAM JOURNAL ON COMPUTING
Volume 35, Issue 3, Pages 658-671Publisher
SIAM PUBLICATIONS
DOI: 10.1137/050629434
Keywords
scheduling; energy efficiency; variable voltage processor; discrete optimization
Ask authors/readers for more resources
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
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available