In this paper, we present a new stochastic mixed-integer linear programming model for the Stochastic Outpatient Procedure Scheduling Problem (SOPSP). In this problem, we schedule a day’s worth of procedures for a single provider, where each procedure has a known type and associated probability distribution of random duration. Our objective is to minimize the expectation of a weighted sum of patient waiting time, provider idling, and clinic overtime. We present computational results to show the size and characteristics of problem instances that can be solved with our model. We also compare this model to other formulations in the literature and analyze them both empirically and theoretically, demonstrating where significant improvements in performance can be gained with our proposed model. This work is motivated by our research on developing scheduling templates for endoscopic procedures at a major medical center. More broadly, however, the SOPSP is a stochastic single-resource sequencing and scheduling problem and therefore has applications both within and outside of healthcare operations.

Introduction

In this paper, we address the Stochastic Outpatient Procedure Scheduling Problem (SOPSP), which arises in outpatient procedure centers (OPCs). In this problem, we consider the perspective of an OPC manager who must schedule the start times for a day’s worth of procedures for a single provider, where each procedure has a known type and a random (non-negative) duration that follows a known probability distribution associated with the procedure type. Given the uncertainty in procedure durations, the goal is to minimize the expectation of a weighted sum of total patient waiting time (the time from the scheduled start of a procedure to its actual start), total provider idle time (the time from the end of one procedure to the start of the next), and clinic overtime (the time from the scheduled closing time of the clinic to the end of the last procedure of the day). This research is motivated by our work with the University of Michigan Medical Procedures Unit, an OPC that performs a variety of endoscopic procedures such as colonoscopies. The ultimate goal of this project is to optimize daily schedule templates and policies for filling these templates, to best account for variability in patient procedure times. By building higher-quality schedules that incorporate the variability in procedure durations, it is possible to ∗ Corresponding author. E-mail address: ksheha@umich.edu (K.S. Shehadeh). improve patient and provider satisfaction, reduce costs, and even achieve better clinical outcomes. A valuable tool in creating such templates is the ability to solve the simpler (and yet still challenging) SOPSP as an embedded sub-problem.