  Appointment scheduling problems under uncertainty encounter a fundamental
trade-off between cost minimization and customer waiting times. Most existing
studies address this trade-off using a weighted sum approach, which puts little
emphasis on individual waiting times and, thus, customer satisfaction. In
contrast, we study how to minimize total cost while providing waiting time
guarantees to all customers. Given box uncertainty sets for service times and
no-shows, we introduce the Robust Appointment Scheduling Problem with Waiting
Time Guarantees. We show that the problem is NP-hard in general and introduce a
mixed-integer linear program that can be solved in reasonable computation time.
For special cases, we prove that polynomial-time variants of the well-known
Smallest-Variance-First sequencing rule and the Bailey-Welch scheduling rule
are optimal. Furthermore, a case study with data from the radiology department
of a large university hospital demonstrates that the approach not only
guarantees acceptable waiting times but, compared to existing robust
approaches, may simultaneously reduce costs incurred by idle time and overtime.
This work suggests that limiting instead of minimizing customer waiting times
is a win-win solution in the trade-off between customer satisfaction and cost
minimization. Additionally, it provides an easy-to-implement and customizable
appointment scheduling framework with waiting time guarantees.
