A stochastic dynamic program for the single-day surgery scheduling problem

Abstract

Scheduling elective surgeries involves sequential decision-making on the part of the operating room (OR) manager, who must continually balance the costs of deferring waiting cases and blocking higher-priority cases. While surgery scheduling has received extensive treatment in the literature, this paper presents the first modeling approach to capture this aspect of the process while incorporating block schedules, block release policies, and surgical waiting lists. The result is a stochastic dynamic programming formulation for the evolution of the schedule for a single day in an OR suite over the days leading up to the day of surgery. A general formulation is presented and theoretical results are obtained for a single-room version. These results demonstrate that optimal waiting list decisions for a single OR follow a threshold policy that preserves a desired amount of OR time for the remaining demand from the room's allocated surgical specialty. An algorithm for determining the optimal thresholds is presented, followed by computational results.