TLDR: Team Twente developed a hybrid 3-phase solution combining Mixed-Integer Programming, Constraint Programming, and Simulated Annealing to tackle the complex Integrated Healthcare Timetabling Competition 2024. Their approach decomposes the problem into patient admission, room assignment, operating theater assignment, and nurse assignment subproblems, achieving third place in the competition and providing new lower bounds for benchmark instances. The paper details their methodology, design choices, and identifies areas for future research in healthcare scheduling optimization.
Healthcare systems worldwide are facing immense pressure due to an aging population, increasing demand for services, and a shortage of skilled professionals. In this challenging environment, efficient resource scheduling and planning become paramount to ensure quality care and optimize limited resources. Hospitals, as critical components of the healthcare system, play a vital role in coordinating care and supporting population health needs.
Recognizing the growing complexity of integrating various planning decisions—such as patient admissions, bed allocation, nurse scheduling, and surgery scheduling—the Integrated Healthcare Timetabling Competition (IHTC) was launched in 2024. This competition aimed to find innovative and efficient solution approaches for these integrated planning problems.
Team Twente, comprising researchers Daniela Guericke, Rolf van der Hulst, Asal Karimpour, Ieke Schrader, and Matthias Walter from the University of Twente, participated in the IHTC 2024 and secured an impressive third place. Their approach, detailed in their research paper “A hybrid solution approach for the Integrated Healthcare Timetabling Competition 2024”, offers a sophisticated method for tackling these complex scheduling challenges.
A Hybrid, Multi-Phase Approach
The core of Team Twente’s solution is a 3-phase decomposition approach that combines three powerful optimization techniques: Mixed-Integer Linear Programming (MILP), Constraint Programming (CP), and Simulated Annealing (SA). This hybrid strategy was developed because solving the entire integrated planning problem as a single, monolithic program proved too difficult for larger instances within the competition’s strict time limits.
The problem was broken down into four key subproblems:
Patient admission: Deciding the optimal day for each patient’s admission.
Room assignment: Allocating admitted patients to specific rooms for their entire length of stay.
Operating theater assignment: Assigning admitted patients to operating theaters.
Nurse assignment: Scheduling available nurses to patient rooms for each shift.
The three phases work in concert, exchanging information to build a comprehensive solution. Phase 1 focuses on initial patient admission and calculating “care-cost bounds” to identify promising admission days. Phase 2 iteratively refines patient-day admission, room assignment, operating theater assignment, and uses simulated annealing for nurse assignment. Finally, Phase 3 aims to further improve the nurse assignment using an exact MIP approach, building on the best solutions found in Phase 2.
Leveraging Different Optimization Techniques
The team strategically employed different techniques for different parts of the problem. Mixed-Integer Linear Programming (MIP) was used for patient admission and operating theater assignment, leveraging its strength in finding optimal solutions for problems with linear objectives and constraints. Constraint Programming (CP), known for its efficiency in handling complex feasibility problems, was crucial for the patient-room assignment, especially given gender constraints for rooms.
For the computationally intensive nurse assignment, a Simulated Annealing (SA) heuristic was initially used in Phase 2. This metaheuristic is effective for finding good solutions in large search spaces within reasonable timeframes. In Phase 3, the best nurse assignments were then subjected to an exact MIP approach to seek further improvements.
Also Read:
- AgileThinker: AI Agents Mastering Real-Time Decisions in Dynamic Environments
- Automated Planning for Mechanized Combat Operations
Results and Future Directions
Team Twente’s approach demonstrated strong performance in the IHTC 2024, securing third place. Their method also provided valuable lower bounds on optimal solution values for the benchmark instances, a significant contribution to the field. While the hybrid approach proved effective, the authors noted areas for future improvement, particularly in enhancing the feedback mechanisms between subproblems and improving the efficiency of the exact nurse assignment MIP.
This research highlights the power of combining diverse optimization techniques and decomposing complex problems into manageable subproblems. It offers valuable insights for developing robust and efficient scheduling solutions that can help healthcare systems better manage their resources and deliver improved patient care in the face of increasing demands.
