Improvements in the Non-Preemptive Speed Scaling Setting
| dc.contributor.author | Matias, Pedro | |
| dc.contributor.department | Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers) | sv |
| dc.contributor.department | Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers) | en |
| dc.date.accessioned | 2019-07-03T13:49:32Z | |
| dc.date.available | 2019-07-03T13:49:32Z | |
| dc.date.issued | 2015 | |
| dc.description.abstract | 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. | |
| dc.identifier.uri | https://hdl.handle.net/20.500.12380/224768 | |
| dc.language.iso | eng | |
| dc.setspec.uppsok | Technology | |
| dc.subject | Data- och informationsvetenskap | |
| dc.subject | Computer and Information Science | |
| dc.title | Improvements in the Non-Preemptive Speed Scaling Setting | |
| dc.type.degree | Examensarbete för masterexamen | sv |
| dc.type.degree | Master Thesis | en |
| dc.type.uppsok | H | |
| local.programme | Computer science – algorithms, languages and logic (MPALG), MSc |
Ladda ner
Original bundle
1 - 1 av 1
Hämtar...
- Namn:
- 224768.pdf
- Storlek:
- 1.11 MB
- Format:
- Adobe Portable Document Format
- Beskrivning:
- Fulltext