Power-aware scheduling for makespan and flow |
| |
Authors: | David P Bunde |
| |
Affiliation: | 1. Department of Computer Science, Knox College, Galesburh, USA
|
| |
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 a linear-time algorithm to compute all non-dominated solutions
for the general uniprocessor problem and a fast arbitrarily-good approximation for multiprocessor problems 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 exact real arithmetic, including 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|