Flight over Bristol

Bristol Algorithms Days 2010
Feasibility Workshop

15 - 16 February 2010

  •    •    •  

Speed Scaling to Manage Flow Time and Energy

Lap-Kei Lee

Energy usage has been an important concern in recent research on online job scheduling. To save energy, processors nowadays support dynamic speed scaling, which would allow operating systems to manage the power by scaling the processor speed dynamically. Providing good quality of service such as flow time and conserving energy are conflicting objectives. An interesting problem for scheduling is how to optimize an economic tradeoff of flow time and energy. To this end, the past few years have witnessed significant progress on minimizing total flow time plus energy. The earlier work in this area mainly focuses on the clairvoyant model, which assumes that the size of a job is known when the job is released. Different competitive algorithms have been designed for processor with unbounded maximum speed and with bounded maximum speed, respectively. Recently, the focus has been shifted to studying the non-clairvoyant model, which assumes the size of a job is not known when the job is released and its size is only known when the job is completed. This is a more natural assumption in the viewpoint of operating systems. Competitive algorithms have also been designed for the unbounded speed and bounded speed settings in this model. In this talk, we present the framework of potential analysis used in most work for minimizing flow time plus energy, and also discuss some interesting techniques that are commonly used in the analyses.


  The University of Bristol   EPSRC