TY - JOUR
T1 - An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules
AU - Li, Minming
AU - Yao, Frances F.
PY - 2005
Y1 - 2005
N2 - 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(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(n log n) time is required, hence the algorithm is optimal for fixed d.
AB - 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(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(n log n) time is required, hence the algorithm is optimal for fixed d.
UR - http://www.scopus.com/inward/record.url?scp=26844482427&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-26844482427&origin=recordpage
U2 - 10.1007/11549345_56
DO - 10.1007/11549345_56
M3 - RGC 21 - Publication in refereed journal
SN - 0302-9743
VL - 3618
SP - 652
EP - 663
JO - Lecture Notes in Computer Science
JF - Lecture Notes in Computer Science
T2 - 30th Symposium on Mathematical Foundations of Computer Science<br/> (MFCS 2005)
Y2 - 29 August 2005 through 2 September 2005
ER -