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 to give an arbitrarily-good approximation for scheduling equal-work jobs on a multiprocessor.
We consider the bi-criteria problem of minimizing the average flow time (average response time) of a collection of dynamically released equi-work processes subject to the constraint that a fixed amount of energy is available. We assume that the processor has the ability to dynamically scale the speed at which it runs, as do current microprocessors from AMD, Intel, and Transmeta. We first reveal the combinatorial structure of the optimal schedule. We then use these insights to devise a relatively simple polynomial time algorithm to simultaneously compute, for each possible energy, the schedule with optimal average flow time subject to this energy constraint.