Abstract
Scheduling problems with stochastic processing times are intriguing optimization problems with sometimes counterintuitive phenomena. For example, optimal solutions might even require to deliberately leave capacity unused. The talk gives a brief introduction into the model. It turns out that much of the work that has been done for non-stochastic problems can -with some extra work- be carried over to the more general stochastic setting. That leads to approximation algorithms which have performance guarantees that depend quadratically on the coefficient of variation of the underlying random variables. The talk will give one such example, namely an LP-based approximation algorithm for unrelated machine scheduling. However to design constant-factor approximation algorithms -or prove this is impossible- remains a major open problem. Some recent progress in this direction will be highlighted, too. (The talk is largely based on joint work with Skutella and Sviridenko.)