Power-aware scheduling for makespan and flow
<|reference_start|>Power-aware scheduling for makespan and flow: 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.<|reference_end|>
@article{bunde2006power-aware,
    title={Power-aware scheduling for makespan and flow},
    author={David P. Bunde},
    journal={arXiv preprint arXiv:cs/0605126},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0605126},
    primaryClass={cs.DS}
}