Description
Stochastic scheduling models are intriguing nonstandard combinatorial optimization problems, with partly surprising or counterintuitive properties.In this set of two lectures we review the stochastic version of a few classical machine scheduling models, study the structure of solutions, some phenomena, and the difficulties in solving such problems. The main part of the lectures focusses on the design of approximation algorithms for the solution of such problems, mainly using linear programming techniques.
The design of approximation algorithms means to compute solutions, here scheduling policies, along with worst-case performance guarantees. The main difficulty lies in the fact that the benchmark to compare with, that is, optimal scheduling policies are highly complex and largely unknown. Hence the necessity to work with linear programming relaxations of stochastic scheduling problems. While proving worst-case performance guarantees is interesting in itself, it has the additional feature of providing also a lot of insight into the the problems and their solution. A set of exercises tailored along the topics of the lectures help to familiarise with the problems and techniques, and will (partly) be discussed in a tutorial session.
| Period | 22 Sept 2015 |
|---|---|
| Event title | Summerschool Decisions Under Uncertainty 2015 |
| Event type | Course |
| Location | Aachen, GermanyShow on map |
| Degree of Recognition | International |