Martin Skutela (Technische Universität Berlin)
07/03/14 12:30 Talks
Stochastic Scheduling on Unrelated Machines
Speaker:
Martin Skutela (Technische Universität Berlin)
Abstract:
Two important characteristics encountered in many real-world scheduling problems are heterogeneous machines/processors and a certain degree of uncertainty about the actual sizes of jobs. The first characteristic entails machine dependent processing times of jobs and is captured by the classical unrelated machine scheduling model. The second characteristic is adequately addressed by stochastic processing times of jobs as they are studied in classical stochastic scheduling models. We give a general overview of LP relaxations for a certain class of machine scheduling problems and then present a new and LP-based approximation algorithms for stochastic unrelated parallel machine scheduling. This is joint work with Maxim Sviridenko and Marc Uetz.
Date:
Friday, March 7, 2014
Time:
12:30 pm - 1:30 pm
Location:
TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby
Martin Skutela (Technische Universität Berlin)
Abstract:
Two important characteristics encountered in many real-world scheduling problems are heterogeneous machines/processors and a certain degree of uncertainty about the actual sizes of jobs. The first characteristic entails machine dependent processing times of jobs and is captured by the classical unrelated machine scheduling model. The second characteristic is adequately addressed by stochastic processing times of jobs as they are studied in classical stochastic scheduling models. We give a general overview of LP relaxations for a certain class of machine scheduling problems and then present a new and LP-based approximation algorithms for stochastic unrelated parallel machine scheduling. This is joint work with Maxim Sviridenko and Marc Uetz.
Date:
Friday, March 7, 2014
Time:
12:30 pm - 1:30 pm
Location:
TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby