AA3 – Networks



Stochastic Scheduling with Restricted Adaptivity

Project Heads

Ralf Borndörfer, Guillaume Sagnol

Project Members

Daniel Schmidt genannt Waldschmidt (TU) 

Project Duration

01.01.2019 – 31.12.2022

Located at

TU Berlin


Scheduling jobs of stochastic duration is ideally done by means of fully adaptive policies. In applications such as surgery scheduling, however, highly volatile regimes cannot be implemented. We will study appropriate scheduling policies for such situations, both from a theoretical and a computational perspective.

We are conducting a fine-grained analysis of the adaptivity trade-off for machine scheduling problems, by considering classes of semi-adaptive policies that can be described with a single parameter, and that interpolates fully adaptive non-anticipative policies and fixed assignment policies. The goal is to get the most out of the performance of adaptive policies,while keeping the stability properties of fixed assignments. Such policies could easily be implemented in stochastic envoronments like hospitals.

From a more practical point of view, we are also investigating the use of reinforcement learning to compute such policies.

Project Webpages

Selected Publications

  • Restricted Adaptivity in Stochastic Scheduling, Sagnol, G., and Schmidt genannt Waldschmidt, D. (2021).  29th Annual European Symposium on Algorithms (ESA). Vol. 204. (pp 79:1-79:14).
  • Scheduling with Contact Restrictions – A Problem Arising in Pandemics, Buchem, M., Kleist, L., and Schmidt genannt Waldschmidt, D. (2021). arXiv preprint arXiv:2102.08231.
  • Stochastic Extensible Bin Packing, Sagnol, G. and Schmidt genannt Waldschmidt, D. (2020). arXiv preprint arXiv:2002.00060.
  • An unexpected connection between Bayes A-optimal designs and the group lasso, Sagnol, G. and Pauwels, E. (2019). Statistical Papers vol 60, 565-584.
  • Robust allocation of operating rooms: A cutting plane approach to handle lognormal case durations, Sagnol, G., Barner, C., Borndörfer, R., Grima, M., Seeling, M., Spies, C. and Wernecke K., (2018). Eur J Oper Res 271(2), 420–435.
  • The Price of Fixed Assignments in Stochastic Extensible Bin Packing. Sagnol, G., Schmidt genannt Waldschmidt, D. and Tesch, A. (2018). In WAOA’18 (pp. 327–347).
  • Improving energetic propagations for cumulative scheduling. Tesch, A. (2018).  In CP’18, (pp. 629–645).
  • Optimal duty rostering for toll enforcement inspectors. Borndörfer, R., Sagnol, G., Schlechte, T., und Swarat, E. (2017). Ann Oper Res 252(2), 383-406.
  • Improved Compact Models for the Resource-Constrained Project Scheduling Problem. Tesch, A. (2016). In OR’16 (pp. 25-30).
  • Robust tail assignment. Dovica (2014). PhD thesis, Borndörfer, R. and Grötschel, M., advisors.

Selected Pictures

Machine Assignments with stochastic jobs.
The analysis of fixed assignment policies relies on splitting stochastic jobs between a truncated part (denoted by alpha on the figure) and an exceptional part (beta).
Reassigning jobs in semi-adaptive policy

Reassigning jobs to free machines only at integer multiples of (αT+δ) starting with a delay δ

Please insert any kind of pictures (photos, diagramms, simulations, graphics) related to the project in the above right field (Image with Text), by choosing the green plus image on top of the text editor. (You will be directed to the media library where you can add new files.)
(We need pictures for a lot of purposes in different contexts, like posters, scientific reports, flyers, website,…
Please upload pictures that might be just nice to look at, illustrate, explain or summarize your work.)

As Title in the above form please add a copyright.

And please give a short description of the picture and the context in the above textbox.

Don’t forget to press the “Save changes” button at the bottom of the box.

If you want to add more pictures, please use the “clone”-button at the right top of the above grey box.