Race to Idle: New Algorithms for Speed Scaling with a Sleep State

further energy savings compared to standard dynamic speed scaling. A schedule has to decide on the processor state and speed, so that the jobs are scheduled with a minimum total energy consumption, while still satisfying a certain quality of service. We investigate the offline setting, and consider classical deadline-based scheduling, i.e. each job is specified by a release time, a deadline and a processing volume.

In this talk, we first prove NP-hardness of the optimization problem, and develop lower bounds for general convex power functions. We then develop an algorithmic framework for designing good approximation algorithms. Finally, we turn our attention to a specific and natural class of scheduling algorithms, and show that our framework yields the best approximation guarantees for this class.