A Simulated Annealing approach to solve Integrated Healthcare Timetabling Problems

Faced with increasing demand and limited resources, healthcare systems require efficient resource management. Within this context, healthcare timetabling problems have emerged as a critical research area, focusing on the optimal allocation of staff, patients, and other resources to improve operational efficiency and service quality while preserving staff and patient satisfaction. In this thesis, we apply a Multi-Neighborhood Simulated Annealing (MNSA) approach to address this class of problems. This approach ensures a thorough exploration of the search space by combining multiple neighborhood operators tailored for the problems at hand to improve search space connectivity, with the Simulated Annealing metaheuristic, which balances intensification and diversification aspects of the search process. Our methodology is evaluated on four distinct NP-hard problems: two standalone healthcare timetabling problems, namely the Medical Students Scheduling Problem and the Nurse Rostering Problem, and two integrated problems involving the joint assignment of multiple resource types. These integrated problems are the Integrated Patient-to-Room and Nurse-to-Patient Assignment Problem and our novel contribution, the Integrated Healthcare Timetabling Problem. The latter formulation served as the basis for the Integrated Healthcare Timetabling Competition, which we organized to foster research in this area. Our approach was tested on benchmark instances for the problems considered. The experimental results demonstrate that the proposed MNSA approach consistently returns high-quality solutions, achieving competitive, and often superior, performance when compared to current state-of-the-art methods within reasonable computational times. Moreover, this approach proves to be scalable and adaptable across diverse problem settings, highlighting its general applicability to healthcare timetabling problems of varying nature and complexity. These computational results are matched by a contribution to domain standardization: supported by strong participation in its companion competition, the Integrated Healthcare Timetabling Problem formulation has since established itself as a reference standard within the community, providing publicly available, validated benchmarks against which future approaches can be compared.