Speed scaling to manage energy and temperature

We first consider online speed scaling algorithms to min-imize the energy used subject to the constraint that every job finishes by its deadline. We assume that the power re-quired to run at speed s is P s s. We provide a tight bound on the competitive ratio of the previously pro-posed Optimal Available algorithm. This improves the best known competitive ratio by a factor of . We then intro-duce a new online algorithm, and show that this algorithm’s competitive ratio is at most e. This competi-tive ratio is significantly better and is approximately e for large . Our result is essentially tight for large . In particular, as approaches infinity, we show that any al-gorithm must have competitive ratio e (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 accord-ing to Fourier’s law. We show how to solve this problem in polynomial time, within any error bound, using the Ellip-soid algorithm. 1