caa a22 4500 445804556 CHVBK 20180317145152.0 cr unu---uuuuu 170323e20110801xx s 000 0 eng 10.1007/s00453-009-9379-z doi (NATIONALLICENCE)springer-10.1007/s00453-009-9379-z Average Rate Speed Scaling [Elektronische Daten] [Nikhil Bansal, David Bunde, Ho-Leung Chan, Kirk Pruhs] 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 (Proc. IEEE Symp. Foundations of Computer Science, pp.374-382, 1995) 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 in Yao etal. (Proc. IEEE Symp. Foundations of Computer Science, pp.374-382, 1995). Springer Science+Business Media, LLC, 2009 Speed scaling nationallicence Voltage scaling nationallicence Scheduling nationallicence Online algorithms nationallicence Power management nationallicence Bansal Nikhil IBM T.J. Watson Research Center, Yorktown Heights, NY, USA aut Bunde David Computer Science Department, Knox College, Galesburg, IL, USA aut Chan Ho-Leung Department of Computer Science, The University of Hong Kong, Hong Kong, China aut Pruhs Kirk Computer Science Department, University of Pittsburgh, Pittsburgh, PA, USA aut Algorithmica Springer-Verlag 60/4(2011-08-01), 877-889 0178-4617 60:4<877 2011 60 453 https://doi.org/10.1007/s00453-009-9379-z text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9379-z text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Bansal Nikhil IBM T.J. Watson Research Center, Yorktown Heights, NY, USA aut NATIONALLICENCE 700 1- Bunde David Computer Science Department, Knox College, Galesburg, IL, USA aut NATIONALLICENCE 700 1- Chan Ho-Leung Department of Computer Science, The University of Hong Kong, Hong Kong, China aut NATIONALLICENCE 700 1- Pruhs Kirk Computer Science Department, University of Pittsburgh, Pittsburgh, PA, USA aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/4(2011-08-01), 877-889 0178-4617 60:4<877 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer