Speed scaling for weighted flow time

Abstract

Intel,s SpeedStep and AMD,s PowerNOW technologies allow the Windows XP operating system to dynamically change the speed of the processor to prolong battery life. In this setting, the operating system must not only have a job selection policy to determine which job to run, but also a speed scaling policy to determine the speed at which the job will be run. We give an online speed scaling algorithm that is O(1)-competitive for the objective of weighted .ow time plus energy. This algorithm also allows us to e.ciently construct an O(1)-approximate schedule for minimizing weighted .ow time subject to an energy constraint. © 2009 Society for Industrial and Apllied Mathematics.