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.


  • New classes of semi-adaptive scheduling strategies have been defined. For a simple scheduling objective (makespan minimization), they were shown to have a huge potential (exponentially better than non-adaptive strategies in the worst case).
  • For an application to surgery scheduling, we developed a two-stage stochastic model for the allocation of patients to blocks of operating room (OR)-time. The problem can be solved very quickly by using a surrogate model for the second-stage costs (overtime, waiting time, idle time). This approach can be tested with our online demonstrator:



  • A weighted version of the bin-packing problem, which serves as a simplified model for the above problem, was analyzed. We obtain improved bounds for simple allocation algorithms. In particular, the greedy algorithm that sequentially select the set of patients for the next operation day by solving a knapsack problem is guaranteed to produce a solution with at most 70% additional costs compared to the optimal solution. (This is a worst-case analysis, the algorithm turns out to be near-optimal in practice).
  • Other models of scheduling under uncertainty were also investigated. In the non-clairvoyant model, we obtained tight bounds for a kill-and-restart policy.

Selected Publications

  • Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling, Jäger, S., Sagnol, G., Schmidt gen. Waldschmidt, D. and Warode., P., (2023). In Proc. 24th International Conference on Integer Programming and Combinatorial Optimization (IPCO 2023), Lecture Notes in Computer Science, vol 13904, pp. 246–260, 2023. arXiv preprint arxiv:2211.02044.
  • Improved analysis of two algorithms for min-weighted sum bin packing, Sagnol, G., (2023) In Proc. 34th International Workshop on Combinatorial Algorithms (IWOCA 2023), Lecture Notes in Computer Science, vol 13889, pp 343–345, 2023. arXiv preprint arXiv:2304.02498.
  • Surgery scheduling in flexible operating rooms by using a convex surrogate model of second-stage costs, Almoghrabi, M.M. and Sagnol, G. Submitted.
    arXiv preprint arxiv:2304.13670.
  • Restricted Adaptivity in Stochastic Scheduling, Sagnol, G., and Schmidt genannt Waldschmidt, D., (2021).  29th Annual European Symposium on Algorithms (ESA 2021). Vol. 204. (pp 79:1-79:14).
  • Improved bounds for stochastic extensible bin packing under distributional assumptions, Sagnol , G. and Schmidt gen. Waldschmidt, D., (2022). In 7th International Symposium on Combinatorial Optimization (ISCO 2022), Lecture Notes in Computer Science, vol. 13526, pp. 228–241, 2022. arXiv preprint: 2002.00060v2
  • Scheduling with Machine Conflicts, Buchem, M., Kleist, L., and Schmidt genannt Waldschmidt, D. (2022). In WAOA’22 (pp. 36–60), 2022. arXiv preprint arXiv:2102.08231.
  • Stochastic Extensible Bin Packing, Sagnol, G. and Schmidt genannt Waldschmidt, D. (2020). arXiv preprint arXiv:2002.00060.
  • 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).

Selected Pictures

The analysis of kill-and-restart scheduling strategy

is done by comparing the produced schedule (top) to that of a rescaled instance (middle) and an algorithm processing several jobs at once different rates (bottom).

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.