A Two-Phase Matheuristic for the Integrated Healthcare Timetabling Problem

The Integrated Healthcare Timetabling Problem (IHTP), introduced in the 2024 IHT Competition, addresses the coordinated optimization of Patient Admission Scheduling, Surgical Case Planning, and Nurse-to-Room assignment. The problem's complexity derives from the interdependencies among these components and the need to balance multiple objectives while respecting capacity, compatibility, and regulatory constraints.We first introduce a comprehensive Mixed-Integer Linear Programming formulation for the IHTP. However, this model becomes computationally intractable on the benchmark instances of the computational challenge due to the significant growth in variables and constraints. To address this challenge, we propose HIPPO (Healthcare Integrated Planning via Phased Optimization), a two-phase matheuristic exploiting the problem's hierarchical structure. Phase 1 jointly optimizes patient admissions and surgical scheduling, establishing the hospital schedule framework; Phase 2 optimizes nurse assignments given the fixed patient placement from Phase 1, leveraging the fact that the nurse assignment subproblem simplifies substantially once admission decisions are determined. Computational experiments on the IHTC 2024 benchmark show that HIPPO produces high-quality feasible solutions, with most instances achieving results close to best-known values. The explicit MILP structure of both phases ensures methodological flexibility: constraints and objectives can be easily adapted to hospital-specific requirements, and the framework provides a foundation for further algorithmic enhancements.