Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.3/84693

Download PDF (Accepted manuscript) (Adobe Acrobat PDF, -1 bytes)

Title

Optimal speed scaling under arbitrary power functions

Author(s)

Andrew, Lachlan L. H.;  Wierman, Adam;  Tang, Ao

Abstract

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.

Publication type

Journal article

Research centre

Swinburne University of Technology. Faculty of Information and Communication Technologies. Centre for Advanced Internet Architectures

Source

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

Publication year

2009

FOR Code(s)

010206 Operations Research

Keyword(s)

Power functions;  Shortest Remaining Processing Time;  Speed scaling;  SRPT

Publisher

ACM

ISSN

0163-5999

Publisher URL

http://dx.doi.org/10.1145/1639562.1639576

Copyright

Copyright © 2009 ACM. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in SIGMETRICS Performance Evaluation Review, Vol. 37, no. 2 (Sep 2009), pp. 39-41. http://doi.acm.org/10.1145/1639562.1639576.

Full text

Peer reviewed