Robust Allocation of Operating Rooms: a Cutting Plane Approach to handle Lognormal Case Durations and Emergency Arrivals

Please always quote using this URN: urn:nbn:de:0297-zib-58502
  • The problem of allocating operating rooms (OR) to surgical cases is a challenging task, involving both combinatorial aspects and uncertainty handling. In this article, we formulate this problem as a job shop scheduling problem, in which the job durations follow a lognormal distribution. We propose to use a cutting-plane approach to solve a robust version of this optimization problem. To this end, we develop an algorithm based on fixed-point iterations to solve the subproblems that identify worst-case scenarios and generate cut inequalities. The main result of this article uses Hilbert's projective geometry to prove the convergence of this procedure under some mild conditions. We also present two extensions of our model, that allow to deal with add-on jobs (emergency arrivals), and to balance the load over several planning period 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) the present robust optimization approach --that protects against likely scenarios from the lognormal durations-- perform well compared to a previous model that ignored the distribution of case durations; (ii) the proposed model is able to efficiently reserve capacity for emergency arrivals; (iii) compared to an alternative stochastic programming approach based on the sample average approximation (SAA), robust optimization yields solutions that are a bit more robust against uncertainty, at a small price in terms of average cost; (iv) However the SAA approach is superior to the robust optimization approach for instances in which the total duration of all cases is very likely to exceed to total available time in all ORs.

Download full text files

Export metadata

Author:Guillaume Sagnol, Christoph Barner, Ralf Borndörfer, Mickaël Grima, Matthes Seeling, Claudia Spies, Klaus Wernecke
Document Type:ZIB-Report
Tag:Hilbert's projective metric; lognormal duration; robust optimization
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx]
Date of first Publication:2016/03/24
Series (Serial Number):ZIB-Report (16-18)