Approximation in Stochastic Scheduling

Add to your list(s) Download to your calendar using vCal

• Nicole Megow (TU Berlin)
• Tuesday 03 February 2015, 14:00-15:00
• MR5, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.

If you have a question about this talk, please contact Felix Fischer.

Stochastic scheduling is concerned with scheduling problems in which job processing times are modeled as random variables with known probability distributions. The actual processing times are revealed only upon completion of the jobs. Such problems have been addressed since the 70s, but only more recently approximation results were derived. We give an overview of results and methods for obtaining provably good scheduling policies. This involves linear programming, lower bounding techniques borrowed from online scheduling, and index-based dynamic allocation rules known from multi-armed bandit problems. We discuss open problems, further research directions, and possible connections to other areas.

This talk is part of the Optimization and Incentives Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Cambridge talks
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Economics and Computer Science Talks
• Hanchen DaDaDash
• Interested Talks
• MR5, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
• Optimization and Incentives Seminar
• School of Physical Sciences
• Statistical Laboratory info aggregator
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.