Abstract: The speed scaling problem was first introduced by Yao, Demers and Shenker [1]. It consists on finding a schedule of jobs that minimises the amount of energy necessary to execute them on a single variable-speed processor. Energy consumption is directly given by a convex function of the processor’s speed and each job must be fully executed within its lifetime, which is specified by its work volume, release time and deadline. In the original version of the problem, the processor is preemptive. This setting is in P and it has already been analysed to a great extent, including for multiple processors. Unfortunately, the non-preemptive version of the problem is strongly NP-hard [2] and not so much is known in this variant. In this talk, I will explain the polynomial-time solution for the preemptive version of the problem, briefly mention the state of the art for variants of this problem explain how the non-preemptive version of the problem can be solved in polynomial time, when all the jobs have the same work volume.
Based on Papers:
[1] - F. Yao, A. Demers and S. Shenker. “A Scheduling Model for Reduced CPU Energy”. FOCS 1995
[2] - Chien-Chung Huang and Sebastian Ott. "New results for non-preemptive speed scaling”. MFCS 2014.