Scheduling with Uncertain Processing Times

Uetz, M. (Invited speaker)

Activity: Talk or presentationInvited talk

Description

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.)
Period23 Sep 2016
Event titleOptimization and Decision-Making Under Uncertainty 2016
Event typeWorkshop
LocationBerkeley, United States
Degree of RecognitionInternational