AG 1, AG 4, RG1, MMCI, AG 3, AG 5, SWS   Info

AG Audience

English

45 Minutes

Saarbrücken

Scheduling problems play a central role in combinatorial optimization. Due to their relevance in practice, models for optimization under uncertainty are of particular interest. Typically this means that parts of the input data are given by stochastic parameters or are not known a priori. In this talk, I will first give a brief overview on different models and performance measures for scheduling under uncertainty. Then, I will show how to deal with uncertainty in the example of the universal sequencing problem. In this problem we assume that processors are unreliable machines that may experience unexpected changes in processing speed or even full breakdowns. Nevertheless, we aim for a universal scheduling solution that performs well without adaptation for any possible machine behavior. I will give algorithms with tight performance guarantees and identify the difficulties of more complex problem variants.

Nicole Megow

--email hidden

passcode not visible

logged in users only