This paper investigates the performance of online dynamic speed scaling algorithms for the objective of minimizing a linear combination of energy and response time. We prove that (SRPT, P−1(n)), which uses Shortest Remaining Processing Time (SRPT) scheduling and processes at speed such that the power used is equal to the queue length, is 2-competitive for a very wide class of power-speed tradeoff functions. Further, we prove that there exist tradeoff functions such that no online algorithm can attain a competitive ratio less than 2.
SIGMETRICS Performance Evaluation Review: special issue on the 11th workshop on Mathematical Modeling and Analysis (MAMA 2009), Seattle, United States, 15 June 2009, Vol. 37, no. 2 (Sep 2009), pp. 39-41