A stochastic approach for solving the operating room scheduling problem

We address a stochastic operating room scheduling problem which consists of assigning an intervention date and operating room to surgeries on the waiting list, minimizing the under- and overtime costs of the operating rooms, and the cost of exceeding the capacity constraints of the system. Uncertainties in surgeries duration, in the arrivals of emergency surgeries and in surgeons’ capacity are considered. To solve the problem we propose a Monte Carlo optimization method based on the sample average approximation method, which combines an iterative greedy local search method and Monte Carlo simulation. The performance of the iterative greedy local search method is evaluated against an exact method and two existing heuristic methods for solving the deterministic version of the problem, using testbeds generated based on the literature. Finally, numerical experiments are presented to evaluate the performance of the Monte Carlo optimization method in a stochastic setting. The results show that the objective function value converges with exponential rates when the number of samples increases, obtaining an optimality index value around 1 %. By comparing the results against the solution obtained by the corresponding deterministic expected value problem, we conclude that an important cost reduction can be obtained by solving the stochastic problem rather than the deterministic one.