This Friday (9/9), Nicole Megow from the Max Planck Institute for Informatics is giving a talk on scheduling under uncertainty. As usual, we meet in the Boardroom at 11:00 am.
Title : Models and Algorithms for Scheduling under Uncertainty
Uncertain problem data are prevalent in real-world scheduling problems. Jobs may take more or less time than originally estimated, resources may be unreliable and slow down or become completely unavailable, material may arrive late, new jobs may have to be incorporated or others may be dropped, etc. In this talk we focus on scheduling problems with stochastic input data. We give an overview on different models, algorithms, and performance measures. The methods for obtaining provably good solutions involve linear programming, lower bounding techniques known from online scheduling, and priority indices borrowed from probability theory. We also discuss recent approaches on obtaining robust schedules.