Distributed appointment assignment and scheduling under uncertainty

Xue Li, Yantong Li, Zheng Wang, Sai‐Ho Chung, Xin WenInternational Journal of Production Research 2023 · DOI

TL;DR

This paper introduces the Stochastic Distributed Appointment Assignment and Scheduling Problem (SDASP), a model for managing appointments across multiple locations under arrival and service time uncertainty. The authors develop a novel Stochastic Logic-Based Benders Decomposition (SLBBD) algorithm that outperforms standard commercial solvers by orders of magnitude, providing a scalable solution for complex systems like medical consortiums and distributed manufacturing.

What Problem Does This Paper Address?

Most appointment scheduling research focuses on a single facility (e.g., one doctor's office). However, modern service systems—like "medical consortiums" where multiple hospitals collaborate or large-scale COVID-19 vaccination campaigns—are distributed.

Decision-makers face a two-fold challenge:

  1. Assignment: Which service unit should a customer be sent to (considering travel costs)?
  2. Scheduling: In what order should appointments be processed at each unit to minimize the "makespan" (the time the last appointment finishes)?

This is complicated by uncertainty. Patients might arrive late due to traffic (release time uncertainty), and check-ups might take longer than expected (service time uncertainty). The authors tackle this "NP-hard" problem by balancing transportation costs with the expected efficiency of the entire system.

Methods

The authors formulate the problem as a two-stage stochastic program:

  • Stage 1: Appointments are assigned to service centers before the specific arrival and service times are known.
  • Stage 2: Once the "scenario" (the actual times) is realized, the sequence of appointments at each center is determined.

To solve this, they use:

  • Sample Average Approximation (SAA): Since uncertainty is continuous and infinite, they sample a finite set of scenarios to make the math tractable.
  • Stochastic Logic-Based Benders Decomposition (SLBBD): This is the paper's primary algorithmic contribution. They decompose the massive problem into a Master Problem (MP) that handles assignments and a Subproblem (SP) that handles scheduling.
  • The "Aha" Moment in the Algorithm: The authors realized that once appointments are assigned to a specific site, the scheduling subproblem becomes a "single-machine scheduling problem with release dates." This specific subproblem can be solved optimally and very quickly using the Earliest Release Date (ERD) rule. They use the results of these fast subproblems to create "Logic-based Benders cuts" that guide the Master Problem toward the global optimum.

Datasets

The paper relies on randomly generated instances rather than a specific static dataset, following established rules in scheduling literature (e.g., Liu et al., 2021):

  • Parameters: Transportation times [1, 3], ready times [1, 5], and mean service times [1, 10] were drawn from discrete uniform distributions.
  • Scenarios: For the SAA method, they used a sample size of 100 scenarios, with a reference set of 1,000 scenarios used for final performance evaluation.
  • Scale: Instances ranged from small (4 appointments, 2 centers) to practical-sized (100 appointments, 10 centers).

Key Insights and Ideas

  • Distributed Flexibility: Moving from a single-site model to a distributed one significantly reduces "hospital strain" and improves system-wide efficiency, but it exponentially increases computational complexity.
  • Parallelism: The SLBBD method is naturally advantageous for modern computing because the subproblems for each service site and each scenario can be solved in parallel.
  • Sensitivity to Service Time: Sensitivity analysis revealed that uncertainty in service duration has a much harsher impact on system performance (higher variance and longer makespans) than uncertainty in arrival times.
  • Logic vs. Linear: Unlike standard Benders decomposition, which requires linear subproblems, the Logic-Based variant allows the subproblem to be any combinatorial problem, which is what allows the use of the ERD rule.

Key Results

  • Speed: On small instances (n=20), the SLBBD method found optimal solutions in an average of 0.82 seconds, while a standard commercial solver (CPLEX) took nearly 1,700 seconds and often failed to reach the true optimum.
  • Scalability: The SLBBD method successfully solved practical-sized instances with up to 100 appointments within a 3,600-second time limit, a feat impossible for non-decomposed models.
  • Objective Quality: The SLBBD method produced objective values (total cost + expected makespan) that were roughly 7.6% better than those found by standard SAA-CPLEX approaches, which often got stuck in local optima.
  • Robustness: The method was successfully extended to a variant minimizing "weighted earliness and tardiness," proving the framework's versatility.

Limitations and Future Work

  • Site Scaling: The authors noted that the SLBBD method "degenerates quickly" as the number of service sites (m) increases. While it handles many appointments well, adding more locations makes the Master Problem significantly harder.
  • Single Period: The current model only looks at a single planning period. Real-world scheduling often spans multiple days or weeks.
  • Heuristic Need: For extremely large-scale industrial applications (thousands of appointments), even this decomposition might be too slow, suggesting a need for future meta-heuristic approaches.
  • Data Availability: The study uses synthetic data; testing on real-world hospital or factory logs would be a logical next step to validate the distribution assumptions.

Summary updated

Abstract

202407 bcch
BibTeX
@article{li2023distributed,
  author = {Xue Li and Yantong Li and Zheng Wang and Sai‐Ho Chung and Xin Wen},
  title = {{Distributed appointment assignment and scheduling under uncertainty}},
  journal = {International Journal of Production Research},
  year = {2023},
  doi = {10.1080/00207543.2023.2252937},
}
Figure