In English

Improvements in the Non-Preemptive Speed Scaling Setting

Improvements in the Non-Preemptive Speed Scaling Setting

Pedro Matias
Göteborg : Chalmers tekniska högskola, 2015. 91 s.
[Examensarbete på avancerad nivå]

The speed scaling problem was first introduced by Yao, Demers and Shenker [35]. It consists on finding a schedule of jobs that minimises the amount of energy that is 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, which is in P, the processor is preemptive. This setting has already been analysed to a great extent, including for multiple processors. Unfortunately, the nonpreemptive version of the problem is strongly NP-hard and not so much is known in this variant. Hence, the present work doesn't consider preemption.

The contributions of this thesis can be grouped into two parts. The main results of the first part (chapter 3) include (using a single processor): (i) a substantial improvement in the time complexity when all jobs have the same work volume and (ii) a proof that, when the number of jobs with unrestricted work volume is limited to a constant, the problem is still in P. The second part (chapter 4) presents and proves the correctness of an algorithm that solves a special instance of a different problem: scheduling with job assignment restrictions (first introduced by Muratore, Schwarz and Woeginger [29]). The goal is to find a schedule of jobs that minimises the maximum job completion time, over a set of single-speed processors. Solving this problem might give some insight on how to solve the non-preemptive speed scaling problem.

Nyckelord: Energy-eciency, scheduling, parallel machines, optimization, speed scaling, algorithm correctness

Publikationen registrerades 2015-10-26.

CPL ID: 224768

Detta är en tjänst från Chalmers bibliotek