AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI   Info

Public Audience

English

120 Minutes

Saarbrücken

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

Andrea Ruffing

--email hidden

passcode not visible

logged in users only