Seminario: Stochastic models for operating room planning and scheduling

Tue, 13/09/2016 - 16:00

Abstract: In this talk, I will first give an overview of my research in healthcare in France and in China since over 10 years. I will then focus on stochastic models for planning and dynamic scheduling of operating rooms.

I first present stochastic models for Operating Room (OR) planning with two classes of patients: elective surgery and emergency surgery. Elective cases can be planned starting from an earliest date with a patient related cost depending on the surgery date. Emergency cases arrive randomly and have to be performed in the day of arrival. The planning problem consists in assign elective cases to different periods over a planning horizon in order to minimize the sum of elective patient related costs and overtime costs of operating rooms. We first propose a basic stochastic mathematical programming model and a Monte Carlo optimization method combining the Monte Carlo simulation and Mixed Integer Programming. The convergence to real optimal and properties of the convergence rate as the computation budget increase are established. We then extended the basic OR planning model to include important factors such as patient to OR assignment, random operating times and overtime capacity constraints. The Monte Carlo optimization method can be extended to solve the more general case but the computation time quickly goes beyond acceptable limit. We then propose a column generation approach that is able to provide efficient solutions for problems of realistic size with duality gap of less than 1%.

I will then address the daily surgery scheduling in a multi-OR setting with random surgery durations. We first address the dynamic assignment of a given set of surgeries with planned surgeon arrival times also called appointment times. Surgeries are assigned dynamically to ORs. The goal is to minimize the total expected cost incurred by surgeon waiting and OR idling/overtime. We first formulate the problem as a multi-stage stochastic programming model. An efficient algorithm is then proposed by combining a two-stage stochastic programming approximation and some look-ahead strategies. A perfect information-based lower bound of the optimal expected cost is given to evaluate the optimality gap of the dynamic assignment strategy. Numerical results show that the dynamic scheduling and optimization with the proposed approach significantly improve the performance of usual static scheduling and First Come First Serve (FCFS) strategies.

We then address the optimization of surgeon appointment times for a sequence of surgeries. Surgeries are assigned to ORs dynamically on a FCFS basis. It materially differs from past literature in the sense that dynamic assignments are proactively anticipated in the determination of appointment times. A discrete-event framework is proposed to model the execution of the surgery schedule and to evaluate the sample path gradient of a total cost incurred by surgeon waiting, OR idling and OR overtime. The sample path cost function is shown to be unimodal, Lipchitz continuous and differentiable w.p.1 and the expected cost function continuously differentiable. A stochastic approximation algorithm based on unbiased gradient estimators is proposed and extensive numerical experiments suggest that it converges to a global optimum. A series of numerical experiments are performed to show the significant benefits of Multi-OR and properties of the optimal solution with respect to various system parameters such as cost structure and numbers of surgeries and ORs.

The last part of this talk is devoted to the daily overtime management to provide OR-teams with different degrees of guarantee of on-time end of the day. This problem is modelled as two stochastic bin packing problems with chance constraints: a stochastic programming model and a robust formulation with moment information. We present a tailored branch-and-price approach based on a column generation reformulation for which CVaR and probabilistic sets are employed to speed-up the resolution of the pricing problems. For the distributionally robust formulation the worst-case distribution is shown to be a three-point distribution, analytical expression of the worst chance probability derived and simple mixed integer linear program model obtained. We implement a series of real-data-based numerical experiments to show that the benefits of optimal allocation and illustrate the value of robust solution.