Branch-and-check methods for multi-level operating room planning and scheduling

We develop the first exact decomposition approaches for a multi-level operating room planning and scheduling problem that integrates case mix planning, master surgical scheduling, and surgery sequencing in the presence of multiple surgical specialties. Our approaches consist of novel uni-level and bi-level branch-and-check algorithms that solve the problem using a hybridization of integer programming and constraint programming. We demonstrate that our approaches outperform an existing time-indexed integer programming model, yielding significant improvements on solution quality. Our methods are competitive with an existing genetic algorithm while providing provable bounds on solution quality. We conduct an investigation into the impact of time discretization on our algorithms, illustrating that our decompositions, unlike the previously proposed integer programming approach, are much less sensitive to time discretization and produce more accurate solutions as a result. Finally, we introduce and investigate benchmark instances with a more diverse case mix. Overall, we conclude that our decompositions are the most appropriate approaches for this multi-level operating room planning and scheduling problem.