### Skapa referens, olika format (klipp och klistra)

**Harvard**

Matias, P. (2015) *Improvements in the Non-Preemptive Speed Scaling Setting*. Göteborg : Chalmers University of Technology

** BibTeX **

@mastersthesis{

Matias2015,

author={Matias, Pedro},

title={Improvements in the Non-Preemptive Speed Scaling Setting},

abstract={The <i>speed scaling</i> 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 <i>variable-speed</i> 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.<br><br>
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: <i>scheduling with job assignment restrictions</i> (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.},

publisher={Institutionen för data- och informationsteknik (Chalmers), Chalmers tekniska högskola},

place={Göteborg},

year={2015},

keywords={Energy-eciency, scheduling, parallel machines, optimization, speed scaling, algorithm correctness},

note={91},

}

** RefWorks **

RT Generic

SR Electronic

ID 224768

A1 Matias, Pedro

T1 Improvements in the Non-Preemptive Speed Scaling Setting

T2 Improvements in the Non-Preemptive Speed Scaling Setting

YR 2015

AB The <i>speed scaling</i> 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 <i>variable-speed</i> 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.<br><br>
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: <i>scheduling with job assignment restrictions</i> (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.

PB Institutionen för data- och informationsteknik (Chalmers), Chalmers tekniska högskola,

LA eng

LK http://publications.lib.chalmers.se/records/fulltext/224768/224768.pdf

OL 30