Asymptotically optimal appointment schedules with customer no-shows

Mor Armony, Rami Atar, Harsha HonnappaarXiv 2017 · DOI · arXiv

Abstract

This paper addresses the challenge of scheduling appointments for a finite customer population in a service facility where no-shows and variable service times are prevalent. The objective is to minimize the combined costs of customer waiting time and server overtime. By analyzing the problem through fluid and diffusion scales, we identify asymptotically optimal schedules. In the fluid scale, we demonstrate that optimal scheduling naturally results in a critically loaded system, meaning heavy-traffic conditions emerge from optimization rather than assumption. In the diffusion scale, we solve the Brownian Optimization Problem (BOP) in the large horizon limit, translating the trade-off between delay and overtime into a trade-off between the state of a reflected Brownian motion and its local time at zero. Finally, we quantify the "stochasticity gap" (SG)—the inherent cost of uncertainty—showing it vanishes in the fluid scale but remains a positive constant in the diffusion scale.

Introduction

In service systems such as outpatient clinics, managers face a difficult "offline" optimization problem: they must set an appointment schedule before knowing which customers will actually arrive or how long each service will take. If appointments are spaced too widely, the server sits idle, wasting capacity; if the system is overbooked to compensate for no-shows, it risks significant customer wait times and expensive staff overtime.

This problem is notoriously difficult to solve exactly, as it is reducible to a stochastic bin-packing problem, which is NP-hard. Most existing research relies on heuristics or specific distributional assumptions. This paper provides a mathematically grounded approach to finding "asymptotically optimal" schedules as the number of customers grows large.

Methodology

The authors employ a three-step asymptotic analysis to solve the scheduling problem:

  1. Fluid Scale Analysis: This first-order approximation washes out stochastic fluctuations to focus on means, transforming the problem into a deterministic variational problem.
  2. Diffusion Scale Analysis: To account for randomness, the authors examine second-order fluctuations (on the scale of the square root of the population size). They formulate a Brownian Optimization Problem (BOP), where the goal is to find a control trajectory that minimizes costs associated with a Reflected Brownian Motion (RBM).
  3. The Stochasticity Gap (SG): A reference model called "Complete Information" (CI) is introduced. In this version, an oracle provides the scheduler with perfect information regarding no-shows and service times before the schedule is set. The difference between the real-world cost and the oracle's cost defines the SG.

Key Insights

Emergent Heavy Traffic

A significant finding in the fluid limit is that the optimal schedule naturally forces the system into a "critically loaded" state. While researchers often assume heavy traffic to simplify calculations, this study shows that heavy traffic is the optimal result of balancing efficiency and capacity. To be truly efficient, a system should be scheduled right at the edge of the server's capacity.

The Cost of Uncertainty

The "Stochasticity Gap" provides a formal measure of the price of ignorance. In the fluid scale, the gap vanishes, suggesting that knowing the future offers little advantage when only considering averages. However, in the diffusion scale, the gap is a strictly positive constant proportional to the diffusion coefficient $\sigma$. This represents the unavoidable "tax" paid for managing a system with inherent randomness.

Stationary RBM Solution

While finite-horizon diffusion problems are often mathematically intractable, the authors found an explicit solution in the large-horizon limit. The optimal schedule in this regime corresponds to a stationary Reflected Brownian Motion with a specific constant negative drift, balancing the cost of server idleness against the cost of customer waiting.

Key Results

  • Optimal Fluid Schedule: The optimal strategy spaces appointments at equal intervals of $p/n\mu$ (where $p$ is the show-up probability and $\mu$ is the service rate) until the end of the horizon, at which point any remaining customers are scheduled.
  • Optimal Diffusion Schedule: The authors identify a refined schedule that adjusts the fluid intervals by a factor of $1/\sqrt{n}$. This adjustment is determined by a constant $c^*_H$ that balances the trade-off between server idleness and customer holding costs.
  • Quantified Gap: The paper provides an explicit formula for the stochasticity gap in the diffusion limit, demonstrating that it is a function of the standard deviation of the underlying noise.

Limitations and Future Work

  • Single Server Focus: The current model is limited to a single server. Multi-queue networks, such as a patient moving from a nurse to a doctor, would involve more complex multidimensional diffusion processes.
  • Punctuality Assumption: The model assumes customers arrive exactly at their appointment time if they show up. In reality, customer tardiness is a major factor that would add another layer of stochasticity.
  • Large Horizon Limit: The explicit solution for the diffusion scale is optimized for a large time horizon. Finding explicit solutions for strictly finite, short-term horizons remains a numerical challenge for future research.

Summary updated

Abstract

We consider the problem of scheduling appointments for a finite customer population to a service facility with customer no-shows, to minimize the sum of customer waiting time and server overtime costs. Since appointments need to be scheduled ahead of time we refer to this problem as an optimization problem rather than a dynamic control one. We study this optimization problem in fluid and diffusion scales and identify asymptotically optimal schedules in both scales. In fluid scale, we show that it is optimal to schedule appointments so that the system is in critical load; thus heavy-traffic conditions are obtained as a result of optimization rather than as an assumption. In diffusion scale, we solve this optimization problem in the large horizon limit. Our explicit stationary solution of the corresponding Brownian Optimization Problem translates the customer-delay versus server-overtime tradeoff to a tradeoff between the state of a reflected Brownian motion in the half-line and its local time at zero. Motivated by work on competitive ratios, we also consider a reference model in which an oracle provides the decision maker with the complete randomness information. The difference between the values of the scheduling problem for the two models, to which we refer as the stochasticity gap (SG), quantifies the degree to which it is harder to design a schedule under uncertainty than when the stochastic primitives (i.e., the no-shows and service times) are known in advance. In the fluid scale, the SG converges to zero, but in the diffusion scale it converges to a positive constant that we compute.
BibTeX
@misc{armony2017asymptotically,
  author = {Mor Armony and Rami Atar and Harsha Honnappa},
  title = {{Asymptotically optimal appointment schedules with customer no-shows}},
  year = {2017},
  eprint = {1708.05920},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1708.05920},
}
Figure