Scheduling Algorithms for new Emerging Applications

May, 29th - June, 2nd 2006, CIRM, Marseille, France

Speed Scaling for Weighted Flow

SpeakerKirk Pruhs

Co-authorsNikhil Bansal and Clifford Stein

Intel's SpeedStep and AMD's PowerNOW technologies allow the 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 to run that job at. These policies must be online since the operating system does not in general have any knowledge about any jobs that may arrive in the future. We give an O(1)-competitive algorithm for weighted flow time. This result is a big step forward in terms of understanding speeding scaling in problems with flow objectives.