Solving integrated operating room planning and scheduling: Logic-based Benders decomposition versus Branch-Price-and-Cut

Integrated operating room planning and scheduling (IORPS) allocates patients optimally to different days in a planning horizon, assigns the allocated set of patients to ORs, and sequences/schedules these patients within the list of ORs and surgeons to maximize the total scheduled surgical time. The state-of-the-art model in the IORPS literature is a hybrid constraint programming (CP) and integer programming (IP) technique that is efficiently solved by a multi-featured Branch-Price-&Cut (BP&C) algorithm. We extend the IORPS literature in two ways: (i) we develop new mixed-integer programming (MIP) and CP models that improve the existing CP-IP model and (ii) we develop various combinatorial Benders decomposition algorithms that outperform the existing BP&C algorithm. Using the same dataset as used for the existing methods, we show that our MIP model achieves an average optimality gap of 3.84%, outperforming the existing CP-IP model that achieves an average optimality gap of 11.84%. Furthermore, our MIP model is 54-92 times faster than the CP-IP model in some of the optimally solved instances of the problem. We demonstrate that our best Benders decomposition approach achieves an average optimality gap of 0.88%, whereas the existing BP&C algorithm achieves an average optimality gap of 2.81%. (C) 2020 Published by Elsevier B.V.

Automated summary

This study extends the integrated operating room planning and scheduling literature by developing new mixed-integer programming and constraint programming models, as well as various combinatorial Benders decomposition algorithms that outperform the existing technique. Experimental results show that the new models outperform the existing ones in terms of performance and optimization.