A branch and price algorithm for scheduling in surgery pre-admission testing clinics

A Surgery Pre-Admission Testing (PAT) clinic is a hospital unit designed to serve pre-operative patients by gathering critical patient information and performing procedure-specific tests to prepare them for surgery. Patients may require multiple tests, each conducted by a specialized nurse. A patient must be assigned to a room before starting any test and must stay there until all tests are completed, with only one test active at a time. This can lead to inefficiencies, such as patients waiting for nurses or nurses remaining idle while another test is ongoing for a patient. To mitigate this, a scheduling approach is required to synchronize the schedules of patients, rooms, and nurses. In this paper, we introduce a novel path-based formulation for the PAT scheduling problem (PATSP) to determine the schedules of patients, rooms, and nurses while incorporating these synchronization constraints. We propose a Branch and Price algorithm to solve this model and introduce various techniques to enhance its computational efficiency. Our computational experiments show that the proposed approach significantly outperforms an existing method in the literature. Additionally, we explore the impact of integrating synchronization constraints into the scheduling framework.