Operating room scheduling with Generalized Disjunctive Programming

• New MILP-based algorithm for scheduling elective surgeries.
• Upper level assigns surgeries to operating rooms and working days.
• Lower level sequences surgeries so as to avoid conflicts.
• Real-life case study from a university hospital.
• Up to 700 surgeries scheduled from a waiting list of over 2000.

This paper addresses the short-term scheduling problem involved in the selection of a subset of elective surgeries from a large waiting list. In order to overcome the combinatorial complexity, a decomposition algorithm is proposed that relies on two continuous-time Generalized Disjunctive Programming (GDP) models. More specifically, there is an upper-level planning model to select surgical assignments to operating rooms and a lower-level constrained scheduling model to synchronize surgeons operating in different rooms on a given day. The GDP models are reformulated using standard convex hull and big-M techniques so as to generate the most efficient set of integer or mixed-integer linear programming constraints. Through the solution of a set of real-life instances from the literature, we show that the new algorithm outperforms a full-space discrete-time formulation and a genetic algorithm, improving the total surgical time as well as the number of performed surgeries by 5%.