Optimal appointment scheduling in continuous time: The lag order approximation method

Wouter Vink, Alex Kuiper, Benjamin Kemper, Sandjai BhulaiEuropean 2014 · DOI

TL;DR

This paper introduces a novel "lag order approximation method" to efficiently solve complex appointment scheduling problems in continuous time. By strategically limiting the number of past appointments considered, the method achieves near-optimal schedules with significantly reduced computational effort, making it practical for real-world scenarios with many clients.

What Problem Does This Paper Address?

The paper tackles the challenge of optimizing appointment schedules for a service provider with a finite number of clients and a single server. The goal is to determine the optimal appointment times for each client to minimize a combined loss function that penalizes client waiting times, server idle times, and lateness (overtime). Deriving the truly optimal schedule is computationally intractable for a large number of clients due to the high dimensionality of the problem. Existing approaches often rely on restrictive assumptions about service times (e.g., exponential) or are too slow for practical implementation. This paper aims to bridge this gap by developing a method that is flexible with respect to service-time distributions and computationally efficient for large-scale problems.

Methods

The core contribution is the lag order approximation method. Instead of considering the influence of all preceding clients on a given client's appointment time, this method strategically limits the lookback to a fixed number of K predecessors. This "lag order K" approach simplifies the problem by reducing the dependencies considered.

  • Lag Order 0: Assumes client sojourn times are equal to their service times, completely ignoring interdependencies.
  • Lag Order I: Considers the waiting time of the immediately preceding client.
  • Lag Order II: Considers the waiting times influenced by the two preceding clients.
  • Lag Order K: Generalizes this by considering the influence of the K preceding clients.

This approximation allows for the use of convolution formulas to compute expected waiting times, idle times, and lateness, making the optimization problem more tractable. The authors implement this method using MATLAB, leveraging its optimization routines. They also compare their method against a simulated optimal schedule, which serves as a benchmark.

Datasets

The paper evaluates its method using:

  • Simulated data: For exponential, Weibull, and lognormal service time distributions with varying coefficients of variation (CV).
  • Real-life data: From a CT-scan area at Deventer Hospital, which was fitted to a lognormal distribution.

The paper does not introduce new benchmark datasets but rather uses simulated data and real-world data to validate its approach against established simulation-based optimization.

Key Insights and Ideas

  • The power of approximation: The lag order approximation method demonstrates that a significant reduction in computational complexity can be achieved by strategically ignoring some dependencies, without a drastic loss in schedule quality.
  • Lag order trade-off: Increasing the lag order generally leads to schedules closer to the optimal, but at the cost of increased computation time. Lag order II appears to strike a good balance, offering near-optimal results with substantial speedups.
  • "Optimistic" schedules: The paper notes that lower lag orders tend to produce "optimistic" schedules from the service provider's perspective, potentially favoring the server over the client due to the neglect of waiting times.
  • Generalizability: The method is shown to be effective across different service-time distributions (exponential, Weibull, lognormal) and loss functions (linear and quadratic), highlighting its practical applicability.
  • Dome shape: The authors observe that as the lag order increases, the appointment slot sizes tend to converge towards the "dome shape" characteristic of optimal schedules in many appointment scheduling problems.

Key Results

  • Lag Order II: Achieves schedules that are remarkably close to the optimal (within 2-7% of the optimal loss function value) for various settings.
  • Computational Speedup: The lag order approximation method can be significantly faster than simulation-based optimization. For instance, lag order II can be up to 20 times faster than simulation for quadratic loss functions with low CV.
  • Lag Order I: Provides schedules within 25% of the optimal loss value and is substantially faster (over 10 to 100 times) than simulation, especially for linear loss functions.
  • Real-world application: In a CT-scan area example, the lag order II method achieved a loss function value only 7.7% higher than the simulated optimal, while being considerably faster than simulation.

Limitations and Future Work

  • No-shows and walk-ins: The current method assumes punctual clients and does not account for no-shows or walk-in clients. The authors suggest extending the method to handle these phenomena as a key future direction, noting the potential for filling idle slots.
  • Patient groups: The study focused on identical CT-scan patients. Future work could explore settings with multiple patient groups, each potentially having different service-time distributions or loss functions.
  • Other factors: The authors acknowledge that other factors like interappointment time variability, client preferences, and server skill levels can affect optimality and would require new models.
  • Algorithmic improvements: Combining the lag order approximation method with existing heuristics is suggested as a way to further improve performance.

Summary updated

BibTeX
@inproceedings{vink2014optimal,
  author = {Wouter Vink and Alex Kuiper and Benjamin Kemper and Sandjai Bhulai},
  title = {{Optimal appointment scheduling in continuous time: The lag order approximation method}},
  booktitle = {European},
  year = {2014},
  doi = {10.1016/j.ejor.2014.06.024},
}
Figure