Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Non-Preemptive Speed Scaling and Parallel Machine Scheduling with Job Restrictions
Speaker:Pedro Ascensão Ferreira Matias
coming from:International Max Planck Research School for Computer Science - IMPRS
Speakers Bio:
Event Type:PhD Application Talk
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:Public Audience
Date, Time and Location
Date:Monday, 26 October 2015
Duration:120 Minutes
Building:E1 4
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 and not so much is known in this variant. This talk will start by mentioning a few contributions made to special instances of the non-preemptive version of the problem, e.g., when all jobs have the same work volume. Afterwards, it is presented an algorithm for solving a special instance of a different problem: parallel machine scheduling with job restrictions, whose task is to find a schedule of jobs that minimises the maximum job completion time, over a set of processors. Solving this problem might give some insight on how to solve the speed scaling problem.

[1] F. Yao, A. Demers and S. Shenker. A Scheduling Model for Reduced CPU Energy.
FOCS 1995, 374-382

Name(s):Andrea Ruffing
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Andrea Ruffing/MPI-INF, 10/23/2015 02:36 PM
Last modified:
Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Andrea Ruffing, 10/23/2015 02:44 PM -- Created document.