Min-Energy Voltage Allocation for Tree-Structured Tasks
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 0(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 trees total path length. We also study an on-line averagerate heuristics AVR 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.
Minming Li Becky Jie Liu Prances F. Yao
Department of Computer Science, Tsinghua University Department of Computer Science, City University of Hong Kong
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
283-296
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）