Seminario: Stochastic models for operating room planning and scheduling
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.