Improvements in the Non-Preemptive Speed Scaling Setting
Ladda ner
Typ
Examensarbete för masterexamen
Master Thesis
Master Thesis
Program
Computer science – algorithms, languages and logic (MPALG), MSc
Publicerad
2015
Författare
Matias, Pedro
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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.
Beskrivning
Ämne/nyckelord
Data- och informationsvetenskap , Computer and Information Science