Campus Event Calendar

Event Entry

What and Who

Algorithms for Classical and Modern Scheduling Problems

Sebastian Ott
Max-Planck-Institut für Informatik - D1
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience

Date, Time and Location

Monday, 4 July 2016
60 Minutes
E1 4


Subject of this thesis is the design and the analysis of algorithms for scheduling problems. In the first part, we focus on energy-efficient scheduling, where one seeks to minimize the energy needed for processing certain jobs via dynamic adjustments of the processing speed (speed scaling). We consider variations and extensions of the standard model introduced by Yao, Demers, and Shenker in 1995 [79], including the addition of a sleep state, the avoidance of preemption, and variable speed limits.

In the second part, we look at classical makespan scheduling, where one aims to minimize the time in which certain jobs can be completed. We consider the restricted assignment model, where each job can only be processed by a specific subset of the given machines. For a special case of this problem, namely when heavy jobs can go to at most two machines, we present a combinatorial algorithm with approximation ratio strictly better than two.


Sebastian Ott
--email hidden
passcode not visible
logged in users only

Sebastian Ott, 06/23/2016 06:42
Sebastian Ott, 06/23/2016 06:42 -- Created document.