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 first consider online speed scaling algorithms to minimize the energy used subject to the constraint that every job finishes by its deadline. We assume that the power required to run at speed s is P(s) = s sup spl alpha . We provide a tight spl alpha sup spl alpha bound on the competitive ratio of the previously proposed optimal available algorithm. This improves the best known competitive ratio by a factor of 2 sup spl alpha . We then introduce an online algorithm, and show that this algorithm's competitive ratio is at most 2( spl alpha ( spl alpha - 1)) sup spl alpha e sup spl alpha . This competitive ratio is significantly better and is approximately 2e sup spl alpha +1 for large spl alpha . Our result is essentially tight for large spl alpha . In particular, as spl alpha approaches infinity, we show that any algorithm must have competitive ratio e sup spl alpha (up to lower order terms). We then turn to the problem of dynamic speed scaling to minimize the maximum temperature that the device ever reaches, again subject to the constraint that all jobs finish by their deadlines. We assume that the device cools according to Fourier's law. We show how to solve this problem in polynomial time, within any error bound, using the ellipsoid algorithm. We consider speed scaling algorithms to minimize device temperature subject to the constraint that every task finishes by its deadline. We assume that the device cools according to Fourier's law. We show that the optimal offline algorithm proposed in [18] for minimizing total energy (that we call YDS) is an O(1)-approximation with respect to temperature. Tangentially, we observe that the energy optimality of YDS is an elegant consequence of the well known KKT optimality conditions. Two online algorithms, AVR and Optimal Available, were proposed in [18] in the context of energy management. It was shown that these algorithms were O(1)-competitive with respect to energy in [18] and [2]. Here we show these algorithms are not O(1)-competitive with respect to temperature. This demonstratively illustrates the observation from practice that power management techniques that are effective for managing energy may not be effective for managing temperature. We show that the most intuitive temperature management algorithm, running at such a speed so that the temperature is constant, is surprisingly not O(1)-competitive with respect to temperature. In contrast, we show that the online algorithm BKP, proposed in [2], is O(1)-competitive with respect to temperature. This is the first O(1)-competitiveness analysis with respect to temperature for an online algorithm.