A two-stage plan-and-allocate algorithm for operation room scheduling problem with uncertainties

Operation room scheduling is a challenging task due to the presence of various sources of uncertainty. The duration of surgeries is stochastic, and there is a possibility of random cancellations or emergent surgeries occurring. These sources of uncertainty can result in staff working overtime and/or excessive idle operation room time. To address these issues, this paper introduces a two-stage iterative algorithm called Column Generation Adaptive Allocation (CGAA). The planning is split into a tactical stage and an operational stage. Uncertainties are represented using time intervals with weighting functions. In the tactical stage, a planning problem based on time intervals is proposed and solved using a column generation algorithm. The goal is to generate an optimized plan that minimises idle time and overtime work. In the operational stage, an adaptive allocation heuristic is employed to dynamically execute the tactical plan based on the current level of idle time. This allows for flexibility in adapting to real-time changes in the operation room schedule. Numerical experiments are conducted using a recently published database of operation room scheduling problems, including real-world and theoretical data. The experiments are divided into two groups based on whether the surgery list exactly matches the planned schedule. The results demonstrate that CGAA generally outperforms the Best-Fit-Decreasing benchmark in both groups. This indicates the algorithm's ability to generate high-quality solutions and handle the two types of uncertainty stably.