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:
- Fluid Scale Analysis: This first-order approximation washes out stochastic fluctuations to focus on means, transforming the problem into a deterministic variational problem.
- 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).
- 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