Healthcare Predictive Timetabling: A predictive decomposition for integrated healthcare timetabling

Healthcare timetabling has long been a well-studied problem in operations research. The direct influence on the efficiency of critical resources, along with the inherent complexity and interdependencies of real-world systems, has driven the development of progressively more sophisticated models and algorithms to assist decisionmakers. The importance and challenges of the problem have also fostered the organization of international research competitions, the most recent of which is the Integrated Healthcare Timetabling Competition (IHTC 2024). The problem addressed in the IHTC 2024 unifies three coupled sub-problems. Specifically, the problem jointly considers Surgical Case Planning (SCP), Patient Admission Scheduling (PAS), and the Nurse-to-Room Assignment (NRA). To address the computational complexity of these three problems, as well as the time and hardware limitations imposed by the competition, this work proposes a heuristic based on a two-phase, rollinghorizon mixed-integer linear programming model. The first phase solves a reduced joint formulation of the first two subproblems, SCP and PAS, while approximating the optimal value of the NRA. The solution obtained for SCP and PAS is then fixed, and the NRA is solved in the second phase. In the first phase, the model is decomposed using a rolling-horizon strategy: as the planning window moves further into the future, constraints are progressively relaxed, and the effects of previously fixed variables are represented only approximately. Experiments are conducted on all public and hidden instances of the competition, and additional experiments under different experimental settings are included. The implementation is provided as open source.