Appointment Scheduling Under Time-Dependent Patient No-Show Behavior

This paper studies how to schedule medical appointments with time-dependent patient no-show behavior and random service times. The problem is motivated by our studies of independent datasets from countries in two continents that unanimously identify a significant time-of-day effect on patient show-up probabilities. We deploy a distributionally robust model, which minimizes the worst-case total expected costs of patient waiting and service provider’s idling and overtime, by optimizing the scheduled arrival times of patients. This model is challenging because evaluating the total cost for a given schedule involves a linear program with uncertainties present in both the objective function and the right-hand side of the constraints. In addition, the ambiguity set considered contains discrete uncertainties and complementary functional relationships among these uncertainties (namely, patient no-shows and service durations). We show that when patient no-shows are exogenous (i.e., time-independent), the problem can be reformulated as a copositive program and then be approximated by semidefinite programs. When patient no-shows are endogenous on time (and hence on the schedule), the problem becomes a bilinear copositive program. We construct a set of dual prices to guide the search for a good schedule and use the technique iteratively to obtain a near-optimal solution. Our computational studies reveal a significant reduction in total expected cost by taking into account the time-of-day variation in patient show-up probabilities as opposed to ignoring it. This paper was accepted by David Simchi-Levi, optimization.