Power-aware scheduling for makespan and flow
| dc.creator | Bunde, David P. | |
| dc.date | 2006-05-26 | |
| dc.date.accessioned | 2026-07-07T07:09:35Z | |
| dc.date.available | 2026-07-07T07:09:35Z | |
| dc.description | 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. | |
| dc.description | 13 pages, 3 figures. To appear in 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2006 | |
| dc.identifier | https://arxiv.org/abs/cs/0605126 | |
| dc.identifier | http://arxiv.org/abs/cs/0605126 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/111120 | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Power-aware scheduling for makespan and flow | |
| dc.type | text |