TY - JOUR
T1 - Min-energy voltage allocation for tree-structured tasks
AU - Li, Minming
AU - Liu, Becky Jie
AU - Yao, Frances F.
PY - 2006/5
Y1 - 2006/5
N2 - We study job scheduling on processors capable of running at variable voltage/speed to minimize energy consumption. Each job in a problem instance is specified by its arrival time and deadline, together with required number of CPU cycles. It is known that the minimum energy schedule for n jobs can be computed in O(n3) time, assuming a convex energy function. We investigate more efficient algorithms for computing the optimal schedule when the job sets have certain special structures. When the time intervals are structured as trees, the minimum energy schedule is shown to have a succinct characterization and is computable in time O(P) where P is the tree's total path length. We also study an on-line average-rate heuristics AYR and prove that its energy consumption achieves a small constant competitive ratio for nested job sets and for job sets with limited overlap. Some simulation results are also given.
AB - We study job scheduling on processors capable of running at variable voltage/speed to minimize energy consumption. Each job in a problem instance is specified by its arrival time and deadline, together with required number of CPU cycles. It is known that the minimum energy schedule for n jobs can be computed in O(n3) time, assuming a convex energy function. We investigate more efficient algorithms for computing the optimal schedule when the job sets have certain special structures. When the time intervals are structured as trees, the minimum energy schedule is shown to have a succinct characterization and is computable in time O(P) where P is the tree's total path length. We also study an on-line average-rate heuristics AYR and prove that its energy consumption achieves a small constant competitive ratio for nested job sets and for job sets with limited overlap. Some simulation results are also given.
KW - Energy efficiency
KW - Scheduling
KW - Variable voltage processor
UR - http://www.scopus.com/inward/record.url?scp=33646562161&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-33646562161&origin=recordpage
U2 - 10.1007/s10878-006-7910-6
DO - 10.1007/s10878-006-7910-6
M3 - 21_Publication in refereed journal
VL - 11
SP - 305
EP - 319
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
SN - 1382-6905
IS - 3
ER -