Average rate speed scaling

Written with Nikhil Bansal, Ho-Leung Chan, and Kirk Pruhs.
Algorithmica, 60(4): 877-889, 2011.
Proceedings of the 8th Latin American Theoretical Infomatics Symposium (LATIN), volume 4957 of LNCS, pp. 240-251, 2008.

Download

official version of journal version from Springer
preprint version of journal paper as gzipped postscript or pdf
official version of conference paper from Springer
preprint version of conference paper as gzipped postscript or pdf

Abstract:

Speed scaling is a power management technique that involves dynamically changing the speed of a processor. This gives rise to dual-objective scheduling problems, where the operating system both wants to conserve energy and optimize some Quality of Service (QoS) measure of the resulting schedule. Yao, Demers, and Shenker considered the problem where the QoS constraint is deadline feasibility and the objective is to minimize the energy used. They proposed an online speed scaling algorithm Average Rate (AVR) that runs each job at a constant speed between its release and its deadline. They showed that the competitive ratio of AVR is at most (2α)^α/2 if a processor running at speed s uses power s^α. We show the competitive ratio of AVR is at least ((2 - δ) α)^α/2, where δ is a function of α that approaches zero as α approaches infinity. This shows that the competitive analysis of AVR by Yao, Demers, and Shenker is essentially tight, at least for large α. We also give an alternative proof that the competitive ratio of AVR is at most (2α)^α/2 using a potential function argument. We believe that this analysis is significantly simpler and more elementary than the original analysis of AVR by Yao, Demers, and Shenker.