Optimizing Surgical Scheduling in Healthcare Services: Models and Algorithms for Minimizing Makespan in No-Wait Scenarios

This thesis addresses a practical challenge encountered in the management of operating rooms within healthcare institutions. When dealing with the issue of scheduling a list of patients with varying surgery durations, an incorrect decision can result in significant time inefficiencies across the overall schedule, leading to a waste of resources that this work aims at minimizing. The problem of organizing tasks is well studied in the context of scheduling theory and the general idea is to search for a solution that satisfies all the requirements presented and at the same time minimizes a certain quantity indicating the quality of a solution. The first step in solving a scheduling problem is identifying what are the Decision Variables (DVs) that best represent the problem within the context. The following step regards translating the limitations of the problem into mathematically rigorous Constraints that correctly fit the DVs previously chosen. Finally, the Objective Function (OF) is chosen as the key parameter to be optimized. In analogy with scheduling theory we can consider the rooms of the facility as machines that can perform one task at the time, and the patients as jobs composed of several ordered tasks. In the context of the presented problem we consider a facility in which only one Operating Theater (OT) is available, composed by a single Anesthesia/Observation Place (AOP) room and a single Operating Room (OR). The single patient is seen as a sequence of three operations to be performed: Anestesia (A) to be performed only in AOP, Surgery (S) to be performed only in OR and Awakening (AW) to be performed in any of the two rooms. The additional information obtained by the context translates into constraint that impose several complications to the problem, like the No-Wait constraint between tasks of a patient and the No-overlap of different patients inside the same room.\\ The problem is presented in two variants: the AOP Scheduling Problem (AOPSP) and the Integrated AOP and OR Scheduling Problem (IAOPORSP). In the AOPSP variant the order of the patients is predetermined, thus leaving the decision to only the placement of the AW. In the IAOPORSP variant the ordering of patients must also be determined together with the AW placement. Both variants consider as OF the Makespan of the schedule, so the amount of time between the beginning of the first task and the ending of the last task in the OT.\\ Due to the vast number of potential solutions, exhaustively exploring all possibilities is impractical and time-consuming. Therefore, an heuristic algorithmic approach is essential to efficiently solve the problem. This thesis details the methodologies employed to tackle both problems, starting with several modeling techniques for the purpose of using a commercial solver to attempt the resolution, and then progressing to various algorithmic strategies designed to match the solver's outcomes while reducing computational time. Finally the results will be showcased by comparing the discrepancy between the outcomes of the most effective algorithm found and the optimal result obtained by the commercial solver.