Power-aware scheduling for makespan and flow

Journal of Scheduling 12(5): 489-500, 2009. (Special issue devoted to papers from the Workshop on Models and Algorithms for Planning and Scheduling (MAPSP).)
Proceedings of the 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 190-196, 2006.
arXiv:cs.DS/0605126

Download

Journal version from Springer or a preprint version: pdf or gzipped postscript. The original publication is available at www.springerlink.com.
SPAA version (© 2006 ACM): gzipped postscript or pdf
arXiv version: cs.DS/0605126
(This version does not include reference 2 (by Albers and Fujiwara) from the SPAA version because I became aware of that work only after submitting to arXiv.)

Abstract:

We consider offline scheduling algorithms that incorporate speed scaling to address the bicriteria problem of minimizing energy consumption and a scheduling metric. For makespan, we give linear-time algorithms to compute all non-dominated solutions for the general uniprocessor problem and for the multiprocessor problem when every job requires the same amount of work. We also show that the multiprocessor problem becomes NP-hard when jobs can require different amounts of work.

For total flow, we show that the optimal flow corresponding to a particular energy budget cannot be exactly computed on a machine supporting arithmetic and the extraction of roots. This hardness result holds even when scheduling equal-work jobs on a uniprocessor. We do, however, extend previous work by Pruhs et al. to give an arbitrarily-good approximation for scheduling equal-work jobs on a multiprocessor.