@misc{TeschBorndoerfer2025, author = {Tesch, Alexander and Bornd{\"o}rfer, Ralf}, title = {Mathematische Optimierung in der OP-Planung}, volume = {5}, journal = {OP-Management up2date}, number = {1}, publisher = {Thieme}, doi = {10.1055/a-2322-2124}, pages = {21 -- 34}, year = {2025}, abstract = {Deutsche Krankenh{\"a}user sehen sich derzeit mit enormen Schwierigkeiten konfrontiert. Ungef{\"a}hr jede 2. Klinik muss drastische Sparmaßnahmen ergreifen, was auch die Allgemeinversorgung beeintr{\"a}chtigt. Die Gr{\"u}nde daf{\"u}r sind vielschichtig: stark gestiegene Sach- und Personalkosten bei gleicher Finanzierung, teilweiser Patientenr{\"u}ckgang, starke regionale Unterschiede in der Versorgung, Fachkr{\"a}ftemangel und fehlende Investitionen in Kern- und Zukunftsbereiche, insbesondere der Digitalisierung. Das belastet die Haushalte der Kliniken. Insbesondere die Digitalisierung und die Anwendung von Methoden der k{\"u}nstlichen Intelligenz und der mathematischen Optimierung k{\"o}nnten eine Schl{\"u}sselrolle spielen, um die komplexen Krankenhausprozesse mit Kennzahlen qualitativ zu bewerten und zu verbessern. In diesem Artikel stellen wir vier Praxisprobleme aus der OP-Planung vor und benennen welche Entscheidungen, Nebenbedingungen und Zielkriterien mit mathematischen Entscheidungsmodellen dargestellt und optimiert werden k{\"o}nnen. Hierzu erl{\"a}utern wir das erweiterte Potenzial einer umfassenden Anwendung von mathematischer Optimierung im OP-Bereich.}, language = {de} } @misc{SagnolBarnerBorndoerferetal.2016, author = {Sagnol, Guillaume and Barner, Christoph and Bornd{\"o}rfer, Ralf and Grima, Micka{\"e}l and Seeling, Matthes and Spies, Claudia and Wernecke, Klaus}, title = {Robust Allocation of Operating Rooms: a Cutting Plane Approach to handle Lognormal Case Durations}, issn = {1438-0064}, doi = {10.1016/j.ejor.2018.05.022}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-58502}, year = {2016}, abstract = {The problem of allocating operating rooms (OR) to surgical cases is a challenging task, involving both combinatorial aspects and uncertainty handling. We formulate this problem as a parallel machines scheduling problem, in which job durations follow a lognormal distribution, and a fixed assignment of jobs to machines must be computed. We propose a cutting-plane approach to solve the robust counterpart of this optimization problem. To this end, we develop an algorithm based on fixed-point iterations that identifies worst-case scenarios and generates cut inequalities. The main result of this article uses Hilbert's projective geometry to prove the convergence of this procedure under mild conditions. We also propose two exact solution methods for a similar problem, but with a polyhedral uncertainty set, for which only approximation approaches were known. Our model can be extended to balance the load over several planning periods in a rolling horizon. We present extensive numerical experiments for instances based on real data from a major hospital in Berlin. In particular, we find that: (i) our approach performs well compared to a previous model that ignored the distribution of case durations; (ii) compared to an alternative stochastic programming approach, robust optimization yields solutions that are more robust against uncertainty, at a small price in terms of average cost; (iii) the \emph{longest expected processing time first} (LEPT) heuristic performs well and efficiently protects against extreme scenarios, but only if a good prediction model for the durations is available. Finally, we draw a number of managerial implications from these observations.}, language = {en} } @inproceedings{Tesch2017, author = {Tesch, Alexander}, title = {Improved Compact Models for the Resource-Constrained Project Scheduling Problem}, booktitle = {Operations Research Proceedings 2016}, pages = {25 -- 30}, year = {2017}, abstract = {In this article, we study compact Mixed-Integer Programming (MIP) models for the Resource-Constrained Project Scheduling Problem (RCPSP). Compared to the classical time-indexed formulation, the size of compact models is strongly polynomial in the number of jobs. In addition to two compact models from the literature, we propose a new compact model. We can show that all three compact models are equivalent by successive linear transformations. For their LP-relaxations, however, we state a full inclusion hierarchy where our new model dominates the previous models in terms of polyhedral strength. Moreover, we reveal a polyhedral relationship to the common time-indexed model. Furthermore, a general class of valid cutting planes for the compact models is introduced and finally all models are evaluated by computational experiments.}, language = {en} } @article{SagnolSchmidtgenanntWaldschmidt2021, author = {Sagnol, Guillaume and Schmidt genannt Waldschmidt, Daniel}, title = {Restricted Adaptivity in Stochastic Scheduling}, volume = {204}, journal = {29th Annual European Symposium on Algorithms (ESA 2021)}, doi = {10.4230/LIPIcs.ESA.2021.79}, pages = {79:1 -- 79:14}, year = {2021}, abstract = {We consider the stochastic scheduling problem of minimizing the expected makespan on m parallel identical machines. While the (adaptive) list scheduling policy achieves an approximation ratio of 2, any (non-adaptive) fixed assignment policy has performance guarantee Ω(logm/loglogm). Although the performance of the latter class of policies are worse, there are applications in which non-adaptive policies are desired. In this work, we introduce the two classes of δ-delay and τ-shift policies whose degree of adaptivity can be controlled by a parameter. We present a policy - belonging to both classes - which is an O(loglogm)-approximation for reasonably bounded parameters. In other words, an exponential improvement on the performance of any fixed assignment policy can be achieved when allowing a small degree of adaptivity. Moreover, we provide a matching lower bound for any δ-delay and τ-shift policy when both parameters, respectively, are in the order of the expected makespan of an optimal non-anticipatory policy.}, language = {en} } @article{PronzatoSagnol2021, author = {Pronzato, Luc and Sagnol, Guillaume}, title = {Removing inessential points in c- and A-optimal design}, volume = {213}, journal = {Journal of Statistical Planning and Inference}, doi = {10.1016/j.jspi.2020.11.011}, pages = {233 -- 252}, year = {2021}, abstract = {A design point is inessential when it does not contribute to an optimal design, and can therefore be safely discarded from the design space. We derive three inequalities for the detection of such inessential points in c-optimal design: the first two are direct consequences of the equivalence theorem for c-optimality; the third one is derived from a second-order cone programming formulation of c-optimal design. Elimination rules for A-optimal design are obtained as a byproduct. When implemented within an optimization algorithm, each inequality gives a screening test that may provide a substantial acceleration by reducing the size of the problem online. Several examples are presented with a multiplicative algorithm to illustrate the effectiveness of the approach.}, language = {en} }