Dynamic Appointment Scheduling of a Stochastic Server with Uncertain Demand

We formulate and solve two new stochastic linear programming formulations of appointment scheduling problems that are motivated by the management of health services. We assume that service durations and the number of customers to be served on a particular day are uncertain. In the first model, customers may fail to show up for their appointments ("no-show"). This model is formulated as a two-stage stochastic linear program. In the second model, customers are scheduled dynamically, one at a time, as they request appointments. This model is formulated as a multistage stochastic linear program with stages defined by customer appointment requests. We analyze the structure of the models and adapt decomposition-based algorithms to solve the problems efficiently. We present numerical results that illustrate the impact of uncertainty on dynamic appointment scheduling, and we identify useful insights that can be applied in practice. We also present a case study based on real data for an outpatient procedure center.