AA3 – Networks

Project

AA3-6

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

Description

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.

Highlights

• 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:

https://wsgi.math.tu-berlin.de/esp_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