Bauerhenne, Kolisch, and Schulz

Robust Appointment Scheduling with Waiting Time Guarantees

Robust Appointment Scheduling with Waiting Time Guarantees

Carolin Bauerhenne School of Management, Technical University of Munich,
Munich, Germany
Funded by Deutsche Forschungsgemeinschaft (DFG), GRK 2201
<EMAIL_ADDRESS>Rainer Kolisch School of Management, Technical
University of Munich, Munich, Germany Andreas S. Schulz Department of
Mathematics and School of Management, Technical University of Munich, Munich,
Germany

Abstract. Problem definition: 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.
Methodology/results: 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 $\mathcal{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. Managerial implications: 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.

appointment scheduling; waiting time guarantees; robust optimization

##  1 Introduction

Excessive waiting times negatively affect customer satisfaction, perceived
service quality, and loyalty in various services, such as call centers, public
transportation, and health care (Huang 1994, Taylor and Baker 1994). A
customer’s tolerance for waiting, which separates acceptable from excessive
waiting times, has been shown to range from 37 minutes for a majority of
patients in an outpatient clinic to 11 seconds for most users to load a
website (Bouch et al. 2000, Moschis et al. 2003, Hill and Joonas 2005). The
tolerance depends amongst others on the perceived and expected waiting time
and can be influenced by many effective interventions, e.g., Kumar et al.
(1997), Davis and Heineke (1998), Bielen and Demoulin (2007). Meanwhile, there
is a lack of appointment scheduling approaches to control actual waiting
times.

Appointment scheduling is a multi-criteria problem that typically involves
uncertainty in service times and other attributes. In particular, appointment
scheduling problems face a fundamental trade-off between waiting times and
capacity utilization: Shorter waiting times come at the cost of longer idle
times, and vice versa. In the literature, this trade-off has been modeled
predominantly by minimizing a weighted sum of waiting times, idle times, and
overtime (Ahmadi-Javid et al. 2017). However, it has long been known that such
weighted sum approaches can lead to unbalanced and excessive waiting times for
some customers (Cayirli and Veral 2003), and in combination with individual
no-show predictions even to racial disparity (Samorani et al. 2021).

This paper proposes a new approach to appointment scheduling that considers
waiting (in)tolerance. In particular, we study the following robust
appointment scheduling and sequencing problem. For a set of preselected
customers, we are given the shortest and longest possible service time of each
customer as well as the total number of no-shows. We limit each customer’s
waiting time, even in a worst-case scenario, to a predetermined tolerance for
waiting (so-called maximum waiting time guarantee). Then we minimize a
weighted sum of idle times and overtime (so-called total cost). The main
contributions of this work can be summarized as follows.

Maximum Waiting Time Guarantees. To the best of our knowledge, this paper is
the first to introduce maximum waiting time guarantees for intraday
appointment scheduling. The guarantees ensure that each customer’s waiting
time stays below a given individual threshold, even in a worst-case scenario.
Hence, they ensure that all customers experience acceptable waiting times and
prevent customer dissatisfaction due to excessive waiting times. In addition,
communicating these guarantees can increase customer satisfaction (Kumar et
al. 1997).

Optimal Scheduling and Sequencing Rules. We show that the robust appointment
scheduling and sequencing problem with customer-specific maximum waiting time
guarantees is $\mathcal{NP}$-hard in general, and introduce a mixed-integer
linear programming formulation. We present optimal scheduling and sequencing
rules for the following polynomial-time solvable problem variants. First, we
consider the case of constant idle time costs, minimizing total idle time plus
overtime cost. For this case, we prove optimality of an extended variant of
the well-known Smallest-Variance-First rule, sorting customers in ascending
order by the degree of uncertainty in their service time and their waiting
time guarantees. For the case of non-increasing idle time costs and any given
but fixed customer sequence, we prove optimality of the so-called ASAP rule,
scheduling customers as early as possible while fulfilling the waiting time
guarantees.

Computational Study Using Patient Data from a Radiology Department. Using real
data from the radiology department of a large hospital, we first show that the
problem can be solved in reasonable computation times for all considered
instances. Second, we conduct a sensitivity analysis of the waiting times,
idle times, and overtime obtained with optimal schedules and sequences. Third,
we compare the schedules with those obtained by a weighted sum approach. The
results show that waiting time guarantees lead to limited and more balanced
waiting times across all customers. Moreover, by definition, our approach
introduces the waiting time guarantees with a minimal increase in worst-case
total cost. In particular, in cases in which the waiting times obtained by the
weighted sum approach are also acceptable for all patients, our approach
generally leads to lower total costs without increasing the waiting time of
the longest waiting patient.

The remainder of the paper is organized as follows. Section 2 reviews related
optimization problems in the appointment scheduling literature. Section 3
formally introduces the Robust Appointment Scheduling Problem with Waiting
Time Guarantees. We show that it is $\mathcal{NP}$-hard in general and derive
a mixed-integer linear program formulation. In Section 4, we present optimal
scheduling and sequencing rules for relevant special cases in polynomial time.
In Section 5, we conduct a computational study with real-world data, showing
that introducing maximum waiting time guarantees can improve both waiting
times and total cost compared to a weighted sum approach.

##  2 Literature Review

For an overview of general appointment scheduling, we refer the interested
reader to Cayirli and Veral (2003), Gupta and Denton (2008), and Ahmadi-Javid
et al. (2017). In the following, we review two streams of the appointment
scheduling literature that are most relevant to our research. In Section 2.1,
we discuss robust optimization approaches using box uncertainty sets for
service times. In Section 2.2, we survey alternative approaches for modeling
waiting time, distinct from the widely used weighted sum approach that
minimizes total idle time, total waiting time, and overtime.

###  2.1 Robust Optimization Framework

Robust approaches to appointment scheduling that require only the shortest and
longest service times but no other distributional information are scarce. To
the best of our knowledge, Mittal et al. (2014) present the first such
approach, minimizing a weighted sum of idle time costs and waiting time costs.
Schulz and Udwani (2019) generalize the problem in Mittal et al. (2014) to
idle time costs that are heterogeneous in the customer sequence and thus
implicitly heterogeneous over time. Both works derive scheduling and
sequencing rules for various special cases that are remarkably easy to
implement. Given a customer sequence and homogeneous idle time costs, Mittal
et al. (2014) present a polynomial-time algorithm to compute optimal
interappointment times, which decrease as the planning horizon progresses.
They also show that a simple variant of Smith’s rule, scheduling customers in
ascending order of the length of their service time intervals divided by their
waiting time costs, is a 1.137 approximation. Schulz and Udwani (2019) prove a
slightly adapted variant of this rule to be 1.0604-approximate, and the
problem of simultaneously scheduling and sequencing customers with
heterogeneous idle time costs and the weighted sum objective function to be
strongly $\mathcal{NP}$-hard. Recently, Issabakhsh et al. (2021) addressed a
robust appointment scheduling problem for infusion centers and solved it with
a scheduling heuristic based on Adaptive Large Neighborhood Search. Advancing
this first stream of literature, whose robust optimization framework we follow
and additionally extend to account for no-shows, we provide waiting time
guarantees to all customers.

###  2.2 Modeling Waiting Time

Building on the classification by Bertsimas et al. (2011), we divide
approaches for modeling waiting times into two substreams, based on the
criterion used to evaluate waiting time. The utilitarian criterion minimizes a
weighted sum of waiting times, while fairness criteria address individual
waiting times more directly.

####  2.2.1 Utilitarian Criterion.

In the first substream, we review appointment scheduling approaches that
deviate from the classic weighted sum objective function but retain the
utilitarian criterion. Sang et al. (2021) use a stochastic optimization
approach to minimize any quantile of the total (idle time, overtime, and
waiting) cost for a given job sequence. They find a semi-dome-shaped pattern
with increasing interappointment times at the beginning of the planning
horizon and constant interappointment times later. Zhou et al. (2022) use a
chance-constraint approach, minimizing, among others, the probability that the
sum of waiting times exceeds a certain threshold. They find optimal
interappointment times to follow the well-known dome-shaped pattern in the
case of zero no-shows and walk-ins. With a positive number of walk-ins, they
find optimal interappointment times in the middle of the planning horizon to
be constant, forming a so-called plateau dome-shaped pattern.

####  2.2.2 Fairness Criteria.

Qi (2017) presents the first optimization study with the primary objective of
fair customer waiting times. She lexicographically minimizes the so-called
delay unpleasantness of the longest-waiting customer, which considers the
frequency and intensity of delays above a certain threshold. Optimal
scheduling rules depend on waiting time thresholds and the weighting of
overtime costs. As the weighting of overtime increases, the interappointment
times between the first appointments are shorter than with weighted sum
approaches. As the waiting time threshold decreases, later start times are
assigned to the later appointments in the planning horizon. Following a
queuing approach, Benjaafar et al. (2023), by contrast, assign the earliest
possible appointment time to each customer request while limiting the expected
waiting time of each customer. They find that the optimal times between
appointments increase in the order of arrival. Finally, for a given customer
sequence, Bendavid et al. (2018) minimize the completion time of the last
appointment while bounding the probability of delay for each appointment.
Under the assumption that the distribution of service times is known, they
develop a simulation-based sequential algorithm and show that optimal
interappointment times follow a dome-shaped pattern.

####  2.2.3 Our Contribution.

In this paper, we contribute to the fairness criteria by providing an a priori
waiting time guarantee for each customer, effectively limiting their worst-
case waiting time. These waiting time guarantees can be customized to match
the tolerance levels for waiting identified in empirical studies. Moreover,
compared to existing approaches, we allow for substantial cost reduction by
accounting for no-shows, (heterogeneous) idle time costs, and the sequencing
decision.

##  3 Robust Appointment Scheduling with Waiting Time Guarantees

This section is organized as follows. In Section 3.1, we formally introduce
the Robust Appointment Scheduling Problem with Waiting Time Guarantees. In
Section 3.2, we show that the problem is $\mathcal{NP}$-hard. In Section 3.3,
we derive two mixed-integer linear programs, the first for the case that all
customers show up and the second for the general case, which considers no-
shows.

###  3.1 Mathematical Model

We consider a set of $n$ preselected customers denoted by
$[n]:=\\{1,\ldots,n\\}$, and a single service provider with a regular working
time of $L$ time units. Our decisions involve determining the customer
sequence and appointment times. To determine the customer sequence, we
introduce binary variables $\pi_{ij}$ for $i,j\in[n]$, where $\pi_{ij}=1$ if
and only if exactly $i-1$ customers are served before customer $j$. In other
words, customer $j$ is assigned to the $i$-th appointment. We define
continuous variables $A_{i}\geq 0$ to represent the start time of each
appointment $i\in[n]$. We consider the following costs. Idle time before the
first appointment incurs a per-time unit cost $c_{1}$, and idle time between
two consecutive appointments $i-1$ and $i$ incurs a per-time unit cost
$c_{i}$, for $2\leq i\leq n$. If there is any idle time before the planning
horizon of $L$ time units ends, it incurs a per-time unit cost $c_{n+1}$.
Additionally, overtime incurs a per-time unit cost $c_{o}$. We aim to
determine a customer sequence and appointment times that minimize the cost
incurred by idle time and overtime, while ensuring that no customer $j\in[n]$
waits longer than their maximum waiting time guarantee $W_{j}$.

The main difficulty is that customers have uncertain service times and no-show
behavior. For each customer $j\in[n]$, we only have information about the
shortest and longest possible service times, denoted as $\ubar{p}_{j}$ and
$\bar{p}_{j}$, respectively. This leads to the scenario set of possible
service time realizations
$\mathcal{P}:=[\ubar{p}_{1},\bar{p}_{1}]\times\ldots\times[\ubar{p}_{n},\bar{p}_{n}]$.
Additionally, we know the total number of customers who will show up within
the planning horizon, denoted as $k$, where $k\leq n$. We have no information
on which $k$ out of $n$ customers show up. This leads to the scenario set of
possible no-show realizations
$\Lambda_{k}:=\\{\lambda\in\\{0,1\\}^{n}:\sum_{j=1}^{n}\lambda_{j}=k\\}$,
where $\lambda_{j}=1$ if and only if customer $j$ shows up. We assume that
customers who show up are on time.

For any given but fixed service time scenario $p\in\mathcal{P}$ and no-show
scenario $\lambda\in\Lambda_{k}$, and given $\pi$ and A, we compute waiting
times, idle times, and overtime as follows. We start by initializing
$C_{0}(\pi,A,p,\lambda):=0$, and define completion times recursively for each
appointment $i\in[n]$ as
${C}_{i}(\pi,A,p,\lambda):=\max\left\\{{A}_{i},{C}_{i-1}(\pi,A,p,\lambda)\right\\}+\sum_{j=1}^{n}\pi_{ij}{\lambda}_{j}{p}_{j}$.
It is useful and easy to see by induction that the completion times can be
reformulated as
$C_{i}(\pi,A,p,\lambda)=\max_{l\in[1,i]}\left\\{{A}_{l}+\sum_{k=l}^{i}\sum\limits_{j=1}^{n}\pi_{kj}{\lambda}_{j}{p}_{j}\right\\}$,
see Lemma 7.1 in the Online Appendix. The waiting time before each appointment
$i\in[n]$ then equals the duration between the completion of the previous
appointment and the start of the current appointment, expressed as

$\textrm{wait}_{i}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(\pi,A,p,\lambda)}:=\left(C_{i-1}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(\pi,A,p,\lambda)}-A_{i}\right)^{+},$

with $(\cdot)^{+}:=\max\\{0,\cdot\\}$. Similarly, the idle time before each
appointment $i\in[n+1]$, with $A_{n+1}:=L$, is given by
$\left(A_{i}-C_{i-1}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(\pi,A,p,\lambda)}\right)^{+}$,
and overtime is computed as
$(C_{n}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(\pi,A,p,\lambda)}-L)^{+}$.
The cost function

$\textrm{cost}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(\pi,A,p,\lambda)}:=\sum\limits_{i=1}^{n}c_{i}\left({A}_{i}-{C}_{i-1}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(\pi,A,p,\lambda)}\right)^{+}+\max\left\\{c_{n+1}(L-C_{n}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(\pi,A,p,\lambda)}),c_{o}(C_{n}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(\pi,A,p,\lambda)}-L)\right\\}$

accounts for the total cost arising from idle time and overtime. We refer to
Table 7 in the Online Appendix for a summary of the notation.

To establish sustainable solutions, appointment schedules should be designed
sufficiently robust to withstand unfortunate service times and no-shows.
_Excessive_ waiting times, idle time, and overtime not only incur high costs
but also lead to employee and customer stress, dissatisfaction, and reduced
loyalty. In healthcare, these factors can even harm patient health (Bae and
Fabry 2014). Hence, we introduce a robust optimization approach that ensures
smooth operations for all stakeholders, even in adverse scenarios. This gives
rise to the following Robust Appointment Scheduling Problem with Waiting Time
Guarantees:

$\displaystyle\\!\min_{\begin{subarray}{c}\pi,A\end{subarray}}\,$
$\displaystyle\,U$ (1) s.t.
$\displaystyle\max\limits_{{p}\in\mathcal{P},{\lambda}\in\Lambda_{k}}\left\\{\textrm{cost}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(p,\lambda,\pi,A)}-U,\max\limits_{i\in[n]}\left\\{\textrm{wait}_{i}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(p,\lambda,\pi,A)}-\sum_{j=1}^{n}\pi_{ij}W_{j}\right\\}\right\\}\leq
0$ (2) $\displaystyle\sum_{i=1}^{n}\pi_{ij}=1,\sum_{j=1}^{n}\pi_{ij}=1$
$\displaystyle\forall i,j\in[n]$ (3) $\displaystyle A_{1}=0$ (4)
$\displaystyle\pi_{ij}\in\\{0,1\\}$ $\displaystyle\forall i,j\in[n]$ (5)

The Objective Function (1) minimizes the upper bound $U$ on total cost
incurred by idle time and overtime. Constraint (2) enforces this upper bound
to remain valid even in worst-case scenarios, preventing excessive idle time
and excessive overtime. Additionally, it ensures that the waiting time
guarantees of all customers are met across all scenarios, ensuring acceptable
waiting times. Thus, by preparing both the provider and the customers for
their respective worst-case scenarios, Constraint (2) ensures smooth operation
even on a challenging day. Constraints (3) enforce that each customer is
assigned to exactly one appointment, and each appointment is assigned to
exactly one customer. Constraint (4) sets the start time of the first
appointment to $0$.

###### Remark 3.1

Due to the adversarial problems in Constraint (2), which maximize the total
cost and the waiting time of the longest-waiting customer, the above problem
formulation is non-linear. In particular, it is not amenable to standard MIP
solvers in this form.

###### Remark 3.2

The problem always has a feasible solution. For an arbitrary but fixed
sequence $\pi$, it is easy to see that the appointment times $A_{1}:=0$ and
$A_{i}:=\left(\max_{l\in[1,i-1]}\left({A}_{l}+\sum_{k=l}^{i-1}\sum_{j=1}^{n}\pi_{kj}\bar{p}_{j}\right)-\sum_{j=1}^{n}\pi_{ij}W_{j}\right)^{+}$
for $i\in[2,n]$ are feasible solutions. In the special case that all waiting
time guarantees are so long that the latter term equals $0$ for all $i\in[n]$,
all customers could be scheduled at time $0$, which corresponds to the single
block rule (Cayirli and Veral 2003).

###### Remark 3.3

It is noteworthy that in special cases a monotonic increase in the appointment
times is not guaranteed. Specifically, given a worst-case scenario $p$ and
$\lambda$, an assignment $\pi$, and appointment times $A_{1},\ldots,A_{i-1}$,
it holds that $A_{i}$ can be chosen to be earlier than $A_{i-1}$ if and only
if
$\max\left\\{0,C_{i-1}(\pi,A,p,\lambda)-A_{i-1}\right\\}+\sum_{j=1}^{n}\pi_{i-1,j}p_{j}<\sum_{j=1}^{n}\pi_{ij}W_{j}$.

###  3.2 Complexity Analysis

In this section, we establish the $\mathcal{NP}$-hardness of the Robust
Appointment Scheduling Problem with Waiting Time Guarantees, which holds even
under the assumption of zero no-shows and identical waiting time guarantees
for all customers. This result expands upon existing $\mathcal{NP}$-hardness
proofs for appointment scheduling and sequencing problems employing weighted
sum approaches (Bosch 1997, Kong et al. 2016, Schulz and Udwani 2019).

######  Theorem 3.4 ($\mathcal{NP}$-Hardness)

Let all customers show up and have identical waiting time guarantees $W$.
Moreover, let the idle time costs fulfill
$c_{1}=\ldots=c_{\sigma}>c_{\sigma+1}=\ldots=c_{n}$ for some $\sigma\in[n-1]$
and the overtime cost $c_{o}=0$. Then the Robust Appointment Scheduling
Problem with Waiting Time Guarantees is $\mathcal{NP}$-hard.

We briefly sketch the proof and refer to the Online Appendix for details. In a
worst-case scenario, worst-case idle times arise in two ways: If no idle time
occurs up to and including appointment $i^{*}-1$, then the idle time before
appointment $i^{*}$ equals
$\sum_{i=1}^{i^{*}-1}\sum_{j=1}^{n}\pi_{ij}(\bar{p}_{j}-\ubar{p}_{j})-W$. The
idle time before all subsequent appointments $i>i^{*}$ equals
$\sum_{j=1}^{n}\pi_{i-1,j}(\bar{p}_{j}-\ubar{p}_{j})$. In the case of
$i^{*}=\sigma$, the unit idle time cost before appointment $i^{*}$ exceeds all
later unit costs of idle time. The challenge lies in partitioning the
customers into two groups such that the idle time sum
$\sum_{i=1}^{i^{*}-1}\sum_{j=1}^{n}\pi_{ij}(\bar{p}_{j}-\ubar{p}_{j})-W$ is
minimized. In the Online Appendix, we show that the well-known Subset Sum
Problem can be reduced to this particular problem, establishing the
$\mathcal{NP}$-hardness of RASWTG.

###### Remark 3.5

If the assumption on idle time costs in Theorem 3.4 is replaced by constant
idle time costs $c_{1}=\ldots=c_{n}$, indicating no time preference for idle
time occurrence, the Robust Appointment Scheduling Problem with Waiting Time
Guarantees becomes solvable in polynomial time. We discuss this case in detail
in Section 4.

###  3.3 Linearization

Due to the recursive nature of completion times in the cost function, applying
the classical dualization scheme by Bertsimas and Sim (2004) for linearization
is impractical. However, we overcome this challenge by exploring structural
problem properties. In Section 3.3.1, we leverage structural properties to
determine worst-case service times analytically. This allows us to formulate a
compact Mixed-Integer Linear Program (MILP) for the case of zero no-shows.
Section 3.3.2 then motivates the consideration of no-shows and outlines
advanced structural properties utilized for linearization in the presence of
no-shows. For a detailed consideration of no-shows as well as for proofs not
included in the main paper, we refer the interested reader to the Online
Appendix 8.

####  3.3.1 Worst-Case Service Time Scenarios.

We investigate service times in adversarial scenarios maximizing cost and
waiting times, respectively. Consequently, we present a compact MILP for the
case of zero no-shows.

##### Adversarial Problem of Maximizing Cost.

The following theorem shows that the total cost is maximized in one of the
$n+1$ sequence-dependent scenarios, in which customers scheduled for the first
$i^{*}\in\\{0,\ldots,n\\}$ appointments require minimum service duration (idle
time maximization), and all subsequent customers require maximum service time
(overtime maximization).

###### Theorem 3.6

Given a customer sequence $\pi$, appointment times $A$, and
$\lambda\in\Lambda_{k}$, let
$\ubar{C}_{i}(\pi,A,\lambda):=\max\left\\{{A}_{i},\ubar{C}_{i-1}(\pi,A,\lambda)\right\\}+\sum_{j=1}^{n}\pi_{ij}{\lambda}_{j}\ubar{p}_{j}$
for $i\in[n]$, with $\ubar{C}_{0}(\pi,A,\lambda):=0$, define the completion
times when all customers require minimum service time. Then
$\max_{p\in\mathcal{P}}\textrm{cost}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(p,\lambda,\pi,A)}$
is equivalent to

$\max_{i^{*}\in\\{0,\ldots,n+1\\}}\sum_{i=1}^{i^{*}}c_{i}(A_{i}-\ubar{C}_{i-1}(\pi,A,\lambda))^{+}+c_{o}\left(A_{i^{*}}+\sum_{k=i^{*}}^{n}\sum_{j=1}^{n}\pi_{kj}\lambda_{j}\bar{p}_{j}-L\right)^{+},$

where $A_{n+1}:=L$.

##### Adversarial Problem of Maximizing Waiting Times.

As for each no-show scenario $\lambda\in\Lambda_{k}$, service time scenario
$p\in\mathcal{P}$, and patient $j\in[n]$, the realized service time
${\lambda}_{j}{p}_{j}$ is non-negative, it is straightforward to see that the
scenario of maximum service times

$\displaystyle\bar{p}:=(\bar{p}_{1},\ldots,\bar{p}_{n})\in\argmax_{\begin{subarray}{c}{p}\in\mathcal{P}\end{subarray}}\left\\{\max_{l\in[1,i-1]}\left({A}_{l}+\sum_{k=l}^{i-1}\sum_{j=1}^{n}\pi_{kj}{\lambda}_{j}{p}_{j}\right)\right\\},\textmd{}$
(6)

uniformly maximizes the waiting time for each appointment $i\in[n]$ in
Constraint (2).

##### MILP.

Now, let $\Delta_{i}$ denote the idle time before appointment $i\in[n+1]$ and
$\sigma_{i^{*}}$ denote the overtime accumulated starting from appointment
$i^{*}\in[n+1]$. Then the worst-case service time scenarios from Theorem 3.6
allow us to obtain the following mixed-integer linear program for the case of
zero no-shows (RASWTG-$0$):

$\displaystyle\min\,$ $\displaystyle U$ (7) s.t. $\displaystyle
U\geq\sum_{i=1}^{i^{*}}c_{i}\Delta_{i}+c_{o}\sigma_{i^{*}}$
$\displaystyle\forall{i^{*}}\in[n+1]$ (8)
$\displaystyle\Delta_{i}\geq{A}_{i}-\ubar{C}_{i-1}$ $\displaystyle\forall
i\in[n+1]$ (9)
$\displaystyle\ubar{C}_{i}=\max\left\\{A_{i},\ubar{C}_{i-1}\right\\}+\sum_{j=1}^{n}\pi_{ij}\ubar{p}_{j}$
$\displaystyle\,\forall i\in[n]$ (10) $\displaystyle\sigma_{i^{*}}\geq
A_{i^{*}}+\sum_{k=i^{*}}^{n}\sum_{j=1}^{n}\pi_{kj}\bar{p}_{j}-L$
$\displaystyle\forall{i^{*}}\in[n]$ (11) $\displaystyle
A_{l}+\sum\limits_{k=l}^{i-1}\sum_{j=1}^{n}\pi_{kj}\bar{p}_{j}-A_{i}\leq\sum_{j=1}^{n}\pi_{ij}W_{j}$
$\displaystyle\forall i,l:i\in[n],l\in[i-1]$ (12)
$\displaystyle\sum_{j=1}^{n}\pi_{ij}=1,\sum_{i=1}^{n}\pi_{ij}=1$
$\displaystyle\forall i,j\in[n]$ (13) $\displaystyle
A_{1}=0,\ubar{C}_{0}=0,A_{n+1}=L$ (14) $\displaystyle A_{i},\ubar{C}_{i}\geq
0$ $\displaystyle\forall{i}\in[n]$ (15)
$\displaystyle\Delta_{i},\sigma_{i}\geq 0$ $\displaystyle\forall{i}\in[n+1]$
(16) $\displaystyle\pi_{ij}\in\\{0,1\\}$ $\displaystyle\forall i,j\in[n]$ (17)

Compared to (1 - 5), RASWTG-0 can be characterized as follows: Based on Lemma
3.6, Constraints (8) - (11) determine the worst-case total cost incurred by
idle time and overtime. Based on (6), Constraint (12) ensures that the waiting
time guarantees are fulfilled even in the worst case.

RASWTG-$0$ is an assignment problem of customers to appointments with
assignment-dependent cost. It has $O(n^{2})$ binary variables, $O(n)$
continuous variables, and $O(n^{2})$ constraints. Using standard linearization
techniques, Constraint (10) can be linearized by introducing another $O(n)$
binary variables, see Remark 7.7 in the Online Appendix. The computational
study in Section 5 shows that RASWTG-$0$ is solvable with a state-of-the-art
MIP solver in short times for all instances with up to twenty patients from a
data set of CT examinations in a large university hospital.

####  3.3.2 Worst-Case No-Show Scenarios.

No-shows introduce uncertainties that, if overlooked, can strongly elevate
costs. The example given in Remark 3.7 illustrates that considering no-shows
can reduce idle time cost by 70%, and this pattern consistently holds across
various examples.

######  Remark 3.7 (Potential for Cost Reduction.)

Consider a scenario with five customers in a fixed order and service time
intervals [5, 6], [5, 7], [5, 8], [5, 9], [5, 10], in which two out of five
customers do not show up. All customers have a maximum waiting time guarantees
of 10 time units. Idle time costs $c_{1}=\ldots=c_{n}$ are constant. For
simplicity, we do not consider idle time after the last appointment or
overtime, i.e., $c_{n+1}=0$, $c_{o}=0$. In Section 4, we demonstrate that this
leads to the following optimal solutions: Disregarding the no-show information
(planning for 0 no-shows) results in appointment times of 0, 0, 3, 11, 20,
incurring a worst-case total idle time of 10 units. However, accounting for
the accurate count of two no-shows yields appointment times of 0, 0, 3, 5, 7,
with a worst-case total idle time of only 3 units.

We now address the task of formulating a MILP for the general Robust
Appointment Scheduling Problem with Waiting Time Guarantees and $k$ no-shows,
$0\leq k\leq n$. To this end, we explore the adversarial problems, seeking no-
show scenarios that maximize waiting times and total cost, respectively.
Identifying worst-case no-show scenarios is notably more complex than
determining worst-case service times. Moreover, maximizing total cost is
particularly intricate because the cost incurred by a no-show is not only
proportional to the customer’s service time but also encompasses sequence-
dependent idle time and overtime costs. For a comprehensive understanding of
the technical aspects, we direct the interested reader to the Online Appendix
8. Here, we summarize our key findings:

##### Adversarial Problem of Maximizing Cost.

In Lemma 8.1 in the Online Appendix, we characterize a worst-case no-show
scenario for an arbitrary but fixed sequence. Specifically, it suffices to
consider, for each $i^{*}\in\\{1,\ldots,n+1\\}$, a no-show scenario in which,
among the customers scheduled for the last $n-i^{*}+1$ appointments, those
with the longest maximum service times show up. If $k>n-i^{*}+1$, all
customers scheduled for these last appointments show up. Additionally, among
the customers scheduled for the first $i^{*}-1$ appointments, the
$k-(n-i^{*}+1)$ ones with the smallest product of idle time cost and minimum
service time show up.

##### Adversarial Problem of Maximizing Waiting Times.

The following lemma establishes the equivalence of (i) computing a single
worst-case scenario that maximizes the waiting time for the longest waiting
customer and (ii) independently computing a worst-case scenario for each
customer that maximizes their waiting time. This inherent decomposability of
the adversary problem for waiting times stems from the scenario-independent
appointment times.

######  Lemma 3.8 (Decomposability)

Given a customer sequence $(\pi_{ij})_{i,j\in[n]}$ and appointment times
$(A_{i})_{i\in[n]}$, it holds that
$\max_{p\in\mathcal{P},\lambda\in\Lambda_{k-1}}\left\\{\max_{i\in[n]}\left\\{C_{i-1}(\pi,A,p,\lambda)-A_{i}-\sum_{j=1}^{n}\pi_{ij}W_{j}\right\\}\right\\}\leq
0$ if and only if
$\max_{i\in[n]}\left\\{\max_{p^{(i)}\in\mathcal{P},\lambda^{(i)}\in\Lambda_{k-1}}\left\\{C_{i-1}(\pi,A,p^{(i)},\lambda^{(i)})-A_{i}-\sum_{j=1}^{n}\pi_{ij}W_{j}\right\\}\right\\}\leq
0$.

By employing the completion time reformulation, leveraging the total
unimodularity of the constraint matrix associated with the adversarial problem
for each appointment, and applying LP duality, the adversarial problem of
maximizing waiting times is then reduced to $\mathcal{O}(n)$ linear
programming problems. Each of these problems entails $\mathcal{O}(n)$
variables and constraints.

##### MILP.

These results lead to a comprehensive MILP for the general case, detailed in
the Online Appendix 8 and denoted as RASWTG. This MILP encompasses $O(n^{3})$
variables and constraints, where the constraint matrix exhibits sparsity. The
computational study in Section 5 demonstrates the efficient solvability of
RASWTG for all instances involving up to ten patients from a dataset of CT
examinations in a large hospital, employing a state-of-the-art MIP solver.

##  4 Optimal Scheduling and Sequencing

In this section, we present optimal scheduling and sequencing rules to solve
RASWTG in polynomial time in special cases, as summarized in Table 1.
Additionally, we investigate optimal interappointment times for the general
case. All results demonstrate how to provide maximum waiting time guarantees
cost-efficiently.

Table 1: Problem Variants and Solution Methods |  | Problem Variant |  |  |  | Solution Method
---|---|---|---|---|---|---
Section 4.1 |  | Constant idle time cost & zero no-shows |  |  |  | Polynomial-time sequencing rule
Section 4.2 |  | Non-increasing idle time cost & fixed sequence |  |  |  | Polynomial-time scheduling rule
Section 4.3 |  | General case |  |  |  | MILP

###  4.1 Polynomial-Time Sequencing for the Case of Constant Idle Time Costs
and Zero No-Shows

Finding an optimal customer sequence can substantially reduce idle time costs
(Cayirli et al. 2008, Deceuninck et al. 2018) but appears extremely difficult
(Mak et al. 2015). Similarly, Theorem 3.4 implies that (unless
$\mathcal{P}=\mathcal{NP}$) we cannot find a universal optimal scheduling and
sequencing rule for the Robust Appointment Scheduling Problem with Waiting
Time Guarantees in polynomial time. However, for a relevant special case, we
now prove optimality of a polynomial-time sequencing rule consistent with the
well-known Smallest-Variance-First (SVF) heuristic.

SVF is the most common heuristic for weighted sum approaches to appointment
sequencing with stochastic service times. It ranks customers in ascending
order of variance, following the intuition to reduce the probability of
deviating from the schedule by placing customers with less variable service
times first. For recent SVF studies in a stochastic optimization framework, we
refer to Kong et al. (2016), Jafarnia-Jahromi and Jain (2020), and de Kemp et
al. (2021). Moreover, Mak et al. (2015) prove, under a mild condition, the
optimality of the SVF rule for a robust mean-variance model with an arbitrary
number of appointments. Recently, Kong et al. (2016) showed that the
optimality of the SVF policy depends on the number of customers as well as the
shape of service time distributions.

######  Lemma 4.1 (Optimal Customer Sequence)

Let the number of no-shows equal zero and idle time costs
$c_{1}=\ldots=c_{n+1}$ be constant, indicating no time preference for the
occurrence of idle time. Then it is optimal to schedule customers $j\in[n]$ in
non-decreasing order w.r.t. $\bar{p}_{j}-\ubar{p}_{j}+(1+c_{o})W_{j}$.

Under the given assumptions, it is optimal to schedule customers $j\in[n]$ in
non-decreasing order with respect to their service time uncertainty
$\bar{p}_{j}-\ubar{p}_{j}$ and their waiting time guarantee $W_{j}$, as a
function of overtime cost $c_{o}$. This result intuitively extends the SVF
rule to account for waiting time guarantees: Uncertainty is kept as low as
possible for as long as possible, particularly for customers with stricter
waiting time guarantees. The relative importance of both criteria depends on
the overtime cost. We call it the Smallest-Variance-First Rule with Waiting
Time Guarantees (SVF-WTG). We will further determine optimal appointment times
under these (and milder) assumptions in Section 4.2.

###  4.2 Polynomial-Time Scheduling Rule under Non-Increasing Idle Time Costs

In the following, we assume that an arbitrary sequence of customers is given.
We first present the so-called As Soon As Possible (ASAP) scheduling rule
defined by Algorithm 1. Second, we show that in the case of non-increasing
idle time costs, it leads to an optimal solution in polynomial time. Third, we
describe how ASAP generalizes the well-known Bailey-Welch rule (Welch and
Bailey 1952).

Algorithm 1 ASAP Scheduling Rule

1:$n\in\mathds{N},c\in\mathds{R}^{n+1}$ with $c_{1}\geq\ldots\geq c_{n+1}$,
$(W_{j})_{j\in[n]}$, $\bar{p}\in\mathds{R}^{n}$, $k\geq 0$,
$\pi\in\\{0,1\\}^{n\times n}$

2:$A_{1}\leftarrow 0$

3:for $i\leftarrow 2$ to $n$ do

4: for $l\leftarrow 1$ to $i-1$ do

5: if $i-l>k-1$ then

6:
$U_{l}\leftarrow\min_{\alpha,z}\left\\{(k-1)\,\alpha+\sum_{\sigma=l}^{i-1}z_{\sigma}\,:\,z_{\sigma}+\alpha\geq\sum_{j=1}^{n}\pi_{\sigma
j}\bar{p}_{j},\,z_{\sigma}\geq 0\,\,\forall{\sigma}\in[l,i-1]\right\\}$

7: else

8: $U_{l}\leftarrow\sum_{\sigma=l}^{i-1}\sum_{j=1}^{n}\pi_{\sigma
j}\bar{p}_{j}$

9:
$A_{i}\leftarrow\left(\max_{l\in[i-1]}A_{l}+U_{l}-\sum\limits_{j=1}^{n}\pi_{ij}W_{j}\right)^{+}$

10:return $(A_{1},\ldots,A_{n})$

The ASAP scheduling rule schedules each customer as early as possible while
respecting the waiting time constraints. It is constructed as follows by
Algorithm 1. The start time of the first appointment is set to $0$ in Line 1.
For each subsequent appointment, the algorithm computes the latest possible
completion time of the previous appointment using Lines 5 and 7. Line 5
calculates the maximum sum of service times from the $l$-th to the $i$th
appointment under $k-1$ show-ups, which corresponds to the term in Line 7 if
all customers show up. Line 8 ensures that even in a worst-case scenario, the
waiting time guarantee is met by setting the $i$-th appointment time to the
latest possible completion time of the previous appointment and subtracting
the waiting time guarantee of the customer scheduled for the $i$-th
appointment. In the special case of zero no-shows, Lines 3 to 7 can be
skipped, and Line 8 can be replaced by
$A_{i}=\left(\,\sum_{k=1}^{i-1}\sum_{j=1}^{n}\pi_{kj}\bar{p}_{j}-\sum_{j=1}^{n}\pi_{ij}W_{j}\right)^{+}$.

Algorithm 1 computes optimal appointment times for a given sequence under non-
increasing idle time costs, as stated in the following theorem. This
condition, while crucial for the optimality proof (see Remark 7.9 in the
Online Appendix), holds practical significance. Constant idle time costs
indicate no time preference for the occurrence of idle time. Decreasing idle
time costs indicate that later idle time is less expensive than earlier idle
time, potentially due to its productive use for documentation work incurred by
earlier appointments.

######  Theorem 4.2 (Optimal Appointment Times)

Given non-increasing idle time costs $c_{1}\geq\ldots\geq c_{n+1}$, and a
customer sequence $\pi$, Algorithm 1 computes optimal appointment times in
polynomial time for the Robust Appointment Scheduling Problem with Waiting
Time Guarantees.

The ASAP rule can be considered a generalization of the well-known Bailey-
Welch rule, which schedules the first two customers simultaneously and all
subsequent customers sequentially. In Line 8, each customer is scheduled to
arrive at time $0$ as long as the latest possible completion times of the
previous customers are not longer than their waiting time guarantee. If this
condition is no longer met, customers are scheduled sequentially. In
particular, the maximum waiting time guarantees control how many customers can
be scheduled at the start time of the planning horizon.

###  4.3 Optimal Interappointment Times for Varying Costs and No-Show Rates

In the literature, empirical studies on optimal interappointment times are
commonly pursued in settings where analytical approaches face significant
challenges. Accordingly, while we have proven optimality of the ASAP
scheduling rule for the case of non-increasing costs, we derive further
insights for the case of increasing costs by analyzing optimal
interappointment times. The optimal schedules are computed using Gurobi and
illustrated by the example of ten identical customers, each with a minimum
service time of 15 minutes, a maximum service time of 25 minutes, and a
waiting time guarantee of 30 minutes.

Figure 1: Optimal Interappointment Times (in Minutes)

(a) Decreasing Idle Time
Costs$A_{2}-A_{1}$$A_{3}-A_{2}$$A_{4}-A_{3}$$A_{5}-A_{4}$$A_{6}-A_{5}$$A_{7}-A_{6}$$A_{8}-A_{7}$$A_{9}-A_{8}$$A_{1}0-A_{9}$$0$$10$$20$$30$

(b) Constant Idle Time
Costs$A_{2}-A_{1}$$A_{3}-A_{2}$$A_{4}-A_{3}$$A_{5}-A_{4}$$A_{6}-A_{5}$$A_{7}-A_{6}$$A_{8}-A_{7}$$A_{9}-A_{8}$$A_{1}0-A_{9}$$0$$10$$20$$30$

(c) Increasing Idle Time
Costs$A_{2}-A_{1}$$A_{3}-A_{2}$$A_{4}-A_{3}$$A_{5}-A_{4}$$A_{6}-A_{5}$$A_{7}-A_{6}$$A_{8}-A_{7}$$A_{9}-A_{8}$$A_{1}0-A_{9}$$0$$10$$20$$30$$40$$50$

0% No-Shows20% No-Shows

In the cases of non-increasing idle time costs, we observe in Figure 1 that
the optimal interappointment times follow variants of the well-known plateau
dome shape (Denton and Gupta 2003, Robinson and Chen 2003, Kong et al. 2020,
Sang et al. 2021). Specifically, interappointment times initially increase,
followed by a plateau of constant interappointment times, and non-increasing
interappointment times towards the end of the planning horizon. We provide a
detailed explanation and generalize these findings for all cases with non-
increasing idle time costs in the Online Appendix, employing the ASAP
scheduling rule. The complexity observed in the case of increasing costs
supports the hypothesis from Remark 7.9 that establishing optimal scheduling
rules in this scenario is more complex.

##  5 Computational Study

In this section, we evaluate the performance of RASWTG schedules on a real-
world data set from the radiology department of a large university hospital.
In particular, we analyze runtimes, conduct a sensitivity analysis, and
present managerial insights from comparing waiting times, idle times, and
overtime obtained with RASWTG to those obtained with a weighted sum approach.
We use the standard time notation mm:ss, where mm denotes the number of
completed minutes and ss the number of completed seconds since the start of
the minute.

###  5.1 Instances

We generate test instances based on 7,745 CT examination records performed on
one of three CT machines in the radiology department of a large university
hospital in Munich, Germany. All exams were performed in 2019 or the first
quarter of 2020. For each CT examination, we have the following information:
Exam type, exam day, start time, and completion time. The start and completion
times were recorded as so-called “Modality Performed Procedure Steps”. That
is, they do not include setup times before and after the irradiation
procedure, such as preparing the patient at the unit or removing the patient
from the unit, but only the scanning time. Service times are calculated as the
difference between completion time and start time.

We first split the data into an interval estimation set and a test set. The
interval estimation set consists of all 6,359 CT examinations recorded in
2019; the test set consists of all 1,386 CT examinations recorded in the first
quarter of 2020. The interval estimation set is used to estimate the service
time intervals for the examinations in the test set. Specifically, for each of
the 64 examination types, we estimate the minimum and maximum service time as
the 5th and 90th percentiles of the empirical distribution of service times
within the interval estimation set. We tested that this choice ensures meeting
the waiting time guarantees for nearly all patients while also resulting in
reasonable total costs. We then compute schedules for the examination requests
recorded in the test set using these service time interval estimates. In case
of multiple optimal solutions, we choose one that minimizes the sum of
appointment times in accordance with the ASAP rule. The schedules are
evaluated using the service times recorded in the test set and a random sample
of $n-k$ no-shows.

To generate test instances, we consider four factors: number of patients,
level of no-shows, waiting time guarantees, and structure of the idle time
costs. In a ceteris paribus design, we systematically vary these factors using
three values each, as outlined in Table 2. Further insights into the rationale
behind selecting these factors are available in the following and the Online
Appendix 10.1. Unless specified otherwise, our analysis centers on the base
case characterized by bold values, encompassing constant idle time costs, ten
patients who all show up, and a maximum waiting time guarantee of 30 minutes.

Table 2: Parameter Sets (Base Case in Bold) Number of patients |  | No-show rate |  | Waiting-time guarantee |  | Idle time cost
---|---|---|---|---|---|---
$\\{5,\,\textbf{10},\,20\\}$ |  | $\left\\{\textbf{0\%},\,10\%,\,20\%\right\\}$ |  | $\\{\textrm{10 min},\,\textrm{20 min},\,\textrm{\bf 30 min}\\}$ |  |  {const., dec., inc.}

For each $n\in\\{5,10,20\\}$, patient selection is performed by first
identifying days within the test set that contain at least $n$ appointments.
Subsequently, we randomly sample $n$ consecutive patient records from these
days. This process generates 252 instances across all classes with five
patients, 107 instances across all classes with ten patients, and 39 instances
across all classes with twenty patients.

We differentiate three types of idle time costs: constant, decreasing, and
increasing. Constant idle time costs $(c_{i})_{i\in[n]}$ remain fixed at
$c_{i}=1$ for all $i\in[n+1]$. Decreasing idle time costs follow three
assumptions: Idle time before the first appointment incurs a per-unit time
cost of $1$, idle time after the last appointment, fully utilized by staff for
tasks like documentation, incurs a per-unit time cost of only $0.5$, and costs
linearly decrease between the first and last idle time. This results in
$c_{i}=1-\frac{i-1}{2n}$ for idle time before appointment $i\in[n+1]$. For
completeness, we also consider linearly increasing idle time costs with
$c_{i}=\frac{n+i-1}{2n}$, $i\in[n+1]$. Overtime cost, complying with current
US federal law requiring a minimum of 1.5 times the regular pay rate, is set
at $c_{o}=1.25$.

Finally, the length $L$ of the planning horizon crucially impacts the trade-
off between idle time cost and overtime cost. A short planning horizon may
cause significant worst-case overtime, while an extended one may lead to no
overtime but substantial idle time. For a comprehensive evaluation of the
model, we set the length of the planning horizon for each instance to a
specific time between the earliest and latest possible completion times of the
last appointment, accommodating both idle time and overtime. Specifically, $L$
is chosen as the sum of maximum service times minus the waiting time guarantee
for the last appointment. For instances with zero no-shows and a waiting time
guarantee of 30 minutes, the resulting average planning horizon is 50:05
minutes for five patients, 132:08 minutes for ten patients, and 312:32 minutes
for twenty patients. The average cumulative uncertainty within this horizon,
obtained as the sum of the service time interval lengths, amounts to 46:53
minutes for five patients, 91:02 minutes for ten patients, and 178:09 minutes
for twenty patients, and accordingly higher in the case of no-shows.

###  5.2 Runtimes

In Table 3, we report the average runtimes to compute an optimal schedule
using the polynomial-time algorithm (PTA) that results from first applying
Lemma 4.1 and then Algorithm 1 in the case of constant idle time costs and
zero no-shows, the mixed-integer program RASWTG-$0$ for the case of zero no-
shows, and the general mixed-integer program RASWTG. All experiments have been
performed on an Intel Core i7-10510U 1.8 GHz machine (in 64-bit mode) with 16
GB memory under Microsoft Windows 10 and Gurobi 9.5.0 in Python 3.9.0.

Table 3: Average Runtimes to Compute an Optimal Schedule (in Seconds) |  |  |  | Method |  | Patients
---|---|---|---|---|---|---
Costs |  | No-shows |  | RASWTG | RASWTG-$0$ | PTA |  | 5 |  | 10 |  | 20
Constant |  | 0% |  |  |  | $\bullet$ |  | 0.00 |  | 0.00 |  | 0.00
Constant |  | 10% |  | $\bullet$ |  |  |  | 0.28 |  | 123.41 |  | -
Constant |  | 20% |  | $\bullet$ |  |  |  | 0.28 |  | 92.80 |  | -
Decreasing |  | 0% |  |  | $\bullet$ |  |  | 0.01 |  | 0.45 |  | 197.35
Decreasing |  | 10% |  | $\bullet$ |  |  |  | 0.45 |  | 799.21 |  | -
Decreasing |  | 20% |  | $\bullet$ |  |  |  | 0.45 |  | 588.82 |  | -
Increasing |  | 0% |  |  | $\bullet$ |  |  | 0.05 |  | 2.80 |  | 199.06
Increasing |  | 10% |  | $\bullet$ |  |  |  | 0.72 |  | 1993.71 |  | -
Increasing |  | 20% |  | $\bullet$ |  |  |  | 0.72 |  | 2541.86 |  | -

In the case of zero no-shows and constant idle time costs, our polynomial-time
algorithm efficiently computes optimal schedules in milliseconds, even for a
substantial number of patients. When there are zero no-shows but non-constant
idle time costs, we employ the mixed-integer linear program RASWTG-$0$. With
this model, Gurobi finds optimal schedules within seconds for up to 10
patients and within 200 seconds for 20 patients.

For the case of a positive number of no-shows, we utilize the mixed-integer
linear program RASWTG to calculate optimal schedules. Computation times
increase noticeably with higher patient numbers and no-show rates. The model
remains computationally tractable for 10 patients. For situations involving 20
patients and a positive number of no-shows, Gurobi solves (almost) no instance
within a one-hour time limit. This underscores the need for future research to
develop scalable algorithms for addressing the robust appointment scheduling
problem with no-shows. Furthermore, our experimental results support the
conjecture from Section 4 that decreasing idle time costs lead to simpler
optimal solution structures than increasing idle time costs.

###  5.3 Results

We first conduct a sensitivity analysis and then compare the results with
those obtained by minimizing a weighted sum of waiting times, idle times, and
overtime.

####  5.3.1 Sensitivity Analysis.

We assess the impact of each of the four factors listed in Table 2 on waiting
times, idle times, and overtime, from which we derive practical managerial
recommendations. To comprehensively understand the dynamics, we recall the
trade-offs between waiting time and idle time until the last appointment, and
the trade-off between overtime and idle time following the last appointment.

##### Base Case.

In the base case, the average waiting time per patient is 10:55 minutes, and
the waiting time guarantees are met for 97% of the patients. The slight
discrepancy from 100% is due to the estimation of minimum and maximum service
times derived from empirical service time data in the separate interval
estimation set, excluding outliers. In cases where realized service times are
outside the estimated range, the waiting time guarantees of a few later
patients are unmet. Furthermore, the average total idle time amounts to 37:40
minutes and overtime to 1:46 minutes, relative to an average cumulative
uncertainty of 91:02 minutes. Figure 2 illustrates the distribution of waiting
and idle times by appointment.

Table 4: Number of Patients |  | 5 patients |  | 10 patients |  | 20 patients
---|---|---|---|---|---|---
Share of patients whose waiting time guarantee is met: |  | 96.11% |  | 96.88% |  | 98.23%
Average idle time before an appointment (mm:ss): |  | 1:54 |  | 3:46 |  | 4:55
Average overtime (mm:ss): |  | 7:55 |  | 1:46 |  | 0:13

##### Number of Patients.

Table 4 summarizes our findings regarding waiting times, idle times, and
overtime across a varying number of patients. Generally, as the number of
patients in the planning horizon increases, the RASWTG approach leads to
shorter waiting times and longer idle times (see Online Appendix, Section
10.2). Moreover, given our choice of the planning horizon $L$, overtime
decreases as the number of patients rises.

Table 5: Total Idle Time (Idle) in Minutes, Average Waiting Time
($\overline{\text{Wait}}$) in Minutes, Percentage of Patients for Whom the
Waiting Time Guarantee is Met (WTG), Overtime (Over)

|  | 10-minute guarantee |  | 20-minute guarantee |  | 30-minute guarantee
---|---|---|---|---|---|---
No-shows |  | Idle |  | $\overline{\text{Wait}}$ |  | WTG |  | Over |  | Idle |  | $\overline{\text{Wait}}$ |  | WTG |  | Over |  | Idle |  | $\overline{\text{Wait}}$ |  | WTG |  | Over
${0\%}$ |  | 56:45 |  | 2:44 |  | 91.50% |  | 0:51 |  | 47:01 |  | 6:06 |  | 94.86% |  | 1:07 |  | 37:40 |  | 10:55 |  | 96.88% |  | 1:46
${10\%}$ |  | 55:50 |  | 2:07 |  | 94.39% |  | 1:37 |  | 47:10 |  | 4:51 |  | 96.92% |  | 1:25 |  | 37:31 |  | 8:02 |  | 98.04% |  | 1:52
${20\%}$ |  | 57:34 |  | 1:52 |  | 94.95% |  | 3:12 |  | 47:06 |  | 4:15 |  | 96.17% |  | 2:06 |  | 37:56 |  | 6:46 |  | 98.13% |  | 2:46

##### No-Shows.

Table 5 demonstrates that higher no-show rates correspond to enhanced
adherence to waiting time guarantees and slightly increased overtime. Total
idle time is not significantly affected by higher no-show rates, which
highlights the model’s performance with no-shows. Looking at the increase from
0% to 10% and from 10% to 20%, waiting times on average decrease by 1:08
minutes, and the fulfillment of waiting time guarantees increases by 1.14%.
This pattern is driven by the elevated planning uncertainty associated with
higher no-show rates, prompting the conservatism of RASWTG, which ensures that
all waiting time guarantees are met even if exactly the patients included in
the worst-case scenario for waiting times show up. Moreover, a 10% increase in
the no-show rate leads to a 0:42-minute rise in overtime, attributed to the
planning horizon choice dependent on the number of show-ups. Finally, it is
important to note that the RASWTG approach relies on precise predictions of
the number of no-shows. If practitioners cannot accurately forecast this
number, we recommend underestimating the total number of no-shows to ensure
the fulfillment of all waiting time guarantees.

Figure 2: Average Waiting and Idle Times by Appointment (in Minutes)

(a) By Waiting Time Guarantee

$5$$10$$0$$5$$10$$15$Appointment no.

Waiting time

$5$$10$$0$$5$$10$$15$Appointment no.

Idle time

10 minutes20 minutes30 minutes

(b) By Idle Time Cost

$5$$10$$0$$5$$10$$15$Appointment no.

Idle time

$5$$10$$0$$5$$10$$15$Appointment no.

Waiting time

Decreasing costConstant costIncreasing cost

##### Waiting Time Guarantees.

Practitioners should tailor waiting time guarantees to align with their
customers’ waiting time tolerance levels. Figure 2 illustrates how waiting and
idle times vary across the planning horizon for different waiting time
guarantee choices. Table 5 shows the corresponding total idle time, average
waiting times, and adherence to the waiting time guarantee. Increasing the
waiting time guarantee by 10 minutes, on average, improves the fulfillment of
the waiting time guarantee by 1.90%, boosts capacity utilization by 18.44%,
and maintains stability in terms of overtime. This substantial capacity
utilization increase results from greater flexibility in terms of the waiting
time constraints and, correspondingly, a shorter overall planning horizon.

##### Idle Time Costs.

The idle time costs control whether idle times occur rather early or late in
the planning horizon and, oppositely, whether waiting times occur rather early
or late. Decreasing idle time costs, by definition, particularly avoid early
idle times. Thus, idle times predominantly occur later in the planning
horizon, as can be seen in Figure 2 for the base case. The opposite is true
for increasing idle time costs. Constant idle time costs do not define a
preference for when idle time occurs. Notably, both total idle time and
overtime are highest in the case of increasing idle time costs and
significantly lower and closely aligned for constant and decreasing idle time
costs. This observation suggests that the simple greedy rule which utilizes
capacities as early as possible proves effective when minimizing total idle
time. Furthermore, constant and decreasing idle time costs lead to later and,
thus, potentially more productively usable idle times.

####  5.3.2 Comparison to a Weighted Sum Approach.

In this section, we compare waiting times, idle times, and overtime acquired
using RASWTG in contrast to those obtained using a weighted sum approach.
Unless stated otherwise, we use the RASWTG approach in the base case setting.
In particular, we assume that all patients show up. We refer to the following
problem as Weighted Sum Robust Appointment Scheduling Problem (WSRAS).

$\displaystyle\\!\min_{\begin{subarray}{c}\pi,A\end{subarray}}\,$
$\displaystyle U$ (18) s.t. $\displaystyle
U\geq\sum\limits_{i=1}^{n+1}c_{i}\left(A_{i}-{C}_{i^{*},i-1}\right)^{+}+\sum\limits_{i=1}^{n}c_{w}\left({C}_{i^{*},i-1}-A_{i}\right)^{+}+c_{o}\left({C}_{i^{*}n}-L\right)^{+}$
$\displaystyle\forall i^{*}\in[n+1]$ (19)
$\displaystyle{C}_{i^{*}i}=\max\\{{A_{i},{C}_{i^{*},i-1}}\\}+\begin{cases}\sum_{j=1}^{n}\pi_{ij}\ubar{p}_{j},&i<i^{*}\\\
\sum_{j=1}^{n}\pi_{ij}\bar{p}_{j},&i\geq i^{*}\end{cases}$
$\displaystyle\forall i^{*}\in[n+1]$ (20)
$\displaystyle\sum_{j=1}^{n}\pi_{ij}=1,\sum_{i=1}^{n}\pi_{ij}=1$
$\displaystyle\forall i,j\in[n]$ (21) $\displaystyle
A_{1}=0,A_{n+1}=L,{C}_{i^{*}0}=0$ $\displaystyle\forall i^{*}\in[n+1]$ (22)

The Objective Function (18) minimizes the upper bound on total cost, as
established in Constraint (19). Specifically, Constraint (19) upper bounds the
sum of waiting times, weighted by constant cost $c_{w}$, idle times, weighted
by sequence-dependent cost $c_{i}$, and overtime, weighted by $c_{o}$; while
ensuring robustness with respect to the same worst-case scenarios as RASWTG
(see Theorem 3.6). Constraint (20) defines the completion times, while
Constraint (21) reflects the assignment constraint known from the Robust
Appointment Scheduling Problem with Waiting Time Guarantees. To enhance our
understanding of optimal WSRAS schedules, we briefly explore optimal
interappointment times, as illustrated in Figure 6 in the Online Appendix.

Notably, Mittal et al. (2014) study a related robust appointment scheduling
problem that minimizes a weighted sum of idle time and waiting time costs
under a collective worst-case scenario. Our works show, independently of each
other and with different objective functions, that it is sufficient to
consider the same $n+1$ critical service time scenarios (see Theorem 3.6).

Figure 3: WSRAS Waiting Times by Appointment (in Minutes)

(a)
$c_{w}=0.00001$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$0$$10$$20$$30$$40$$50$$60$$70$$80$$90$$30$Appointment
no.Waiting time

(b)
$c_{w}=0.1$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$0$$10$$20$$30$$40$$50$$60$$70$$80$$90$$30$Appointment
no.Waiting time

(c)
$c_{w}=1$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$0$$10$$20$$30$$40$$50$$60$$70$$80$$90$$30$Appointment
no.Waiting time

Figure 4: RASWTG Waiting Times by Appointment (in
Minutes)$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$0$$10$$20$$30$$40$$50$$60$$70$$80$$90$$30$Appointment
no.Waiting time

##### Waiting Times.

We compare, first, how to control waiting times with both approaches and,
second, the distribution of waiting times across all appointments. Applying
the weighted sum approach, we need to carefully tune the waiting time costs to
manage waiting times. In contrast, when applying RASWTG, the waiting time
guarantees constitute input parameters which (a priori) limit all worst-case
waiting times, and indirectly also the realized waiting times. It is therefore
easier to control waiting times with RASWTG than with the weighted sum
approach.

In addition, Figures 3 and 4 present boxplots illustrating patient waiting
times depending on their position in the appointment schedule. These waiting
times correspond to the optimal interappointment intervals depicted in Figure
6 in the Online Appendix. Notably, for modest waiting time costs ($c_{w}$),
waiting times with the weighted sum approach exhibit an increasing trend until
the penultimate or last appointment, and excessive waiting times for some
later appointments. High waiting time costs lead to very short waiting times
for all appointments. In contrast, the RASWTG approach demonstrates an initial
(limited) increase in waiting times followed by a gradual decrease. It is
worth mentioning that this decline can be mitigated by introducing uncertainty
budgets. Furthermore, for comparable overall costs, waiting times are
distributed more equitably across appointments with RASWTG, and excessive
waiting times are less likely.

Table 6: Cost Incurred by Idle Time and Overtime |  | WSRAS |  | WSRAS |  | RASWTG |  | WSRAS
---|---|---|---|---|---|---|---|---
|  | $c_{w}=0.00001$ |  | $c_{w}=0.1$ |  |  |  | $c_{w}=1$
Share of patients waiting at most 30 minutes: |  | 79.91% |  | 92.43% |  | 96.88% |  | 99.91%
Idle time up to the last appointment: |  | 10:07 |  | 24:45 |  | 17:11 |  | 37:30
Total idle time: |  | 37:55 |  | 39:02 |  | 37:40 |  | 42:16
Overtime: |  | 2:01 |  | 3:08 |  | 1:46 |  | 6:22

##### Costs.

We finally evaluate the cost of replacing the weighted sum approach with
RASWTG. We consider that a healthcare provider replaces WSRAS schedules with
fixed waiting time cost (i) $c_{w}=0.00001$, (ii) $c_{w}=0.1$, and (iii)
$c_{w}=1$ over all days. Our findings are summarized in Table 6.

Let us first examine overtime. For WSRAS, we observe that overtime decreases
with lower waiting time costs, as lower waiting costs allow for scheduling
appointments earlier. Surprisingly, RASWTG exhibits the lowest overtime, on
average only 1:46 minutes. This suggests that, even with hard waiting time
constraints, RASWTG permits slightly earlier scheduling of the last
appointment even compared to the weighted sum approach with low waiting time
cost. Overall, both approaches maintain reasonable average overtime within a 1
to 7-minute range, and minimal with RASWTG.

Considering total idle time, we find that it naturally increases with rising
waiting time costs for WSRAS. RASWTG displays the lowest total idle time, a
result consistent with our findings regarding overtime. It is worth noting
that idle time for both approaches could be reduced by opting for a shorter
planning horizon $L$ but at the expense of increased overtime, which we aimed
to prevent in the first place. However, as a substantial amount of idle time
remains between the last appointment and the end of the planning horizon $L$
for both approaches, we also compare the idle time up to the last appointment,
which is less dependent on the choice of $L$. Again, for all waiting time
costs except for $c_{w}=0.00001$, which comes with excessive waiting times,
RASWTG yields lower idle time than WSRAS.

We conclude with the following rule of thumb. In environments where most
customers experience acceptable waiting times, introducing RASWTG offers both
a priori waiting time guarantees and total cost reduction. The cost reduction
typically comes with a limited increase in average waiting times. In
environments where many customers experience excessive waiting times,
introducing RASWTG effectively prevents excessive waiting times with a minimum
increase in total worst-case cost. In all cases, RASWTG effectively mitigated
excessive waiting times and overtime.

##  6 Conclusion

This work was motivated by the lack of intraday appointment scheduling and
sequencing approaches to precisely control waiting times. We introduce maximum
waiting time guarantees to respect customers’ waiting time tolerance even in a
worst-case scenario of uncertain service times and no-shows. Hence, the
established guarantees prevent negative effects of waiting times on customer
dissatisfaction, perceived service quality, and loyalty shown in previous
empirical research. At the same time, we minimize worst-case costs incurred by
idle time and overtime.

We show that the presented appointment scheduling problem with waiting time
guarantees is $\mathcal{NP}$-hard and find optimal scheduling and sequencing
rules in polynomial time for practically relevant special cases. Assuming
constant idle time costs and zero no-shows, we show optimality of a sequencing
rule that schedules customers in ascending order with the amount of
uncertainty about their service times and their waiting tolerance. This rule
provides a deeper understanding of the optimality of the well-known SVF rule
and extends it to consider waiting time guarantees. Moreover, for the case of
non-increasing idle time costs, we show optimality of the ASAP scheduling rule
that sets each appointment time as early as possible while fulfilling the
waiting time guarantees. The presented sequencing and scheduling rules are
intuitive and easy to implement.

Our case study with real data from the radiology department of a large
hospital shows that robust appointment scheduling with waiting time guarantees
not only prevents excessive waiting times. Compared to weighted sum
approaches, our approach also provides more flexibility to control the timing
of idle and waiting times. Most importantly, we introduce the waiting time
guarantees with a minimal increase in worst-case costs, which in many cases is
even negative. Thus, compared to weighted sum approaches, waiting time
guarantees can even reduce costs without increasing the waiting time of the
longest waiting customer.

Our work also points to several avenues for future research. First, an
intriguing open question involves introducing uncertainty budgets to control
the level of conservatism, and adapting the presented scheduling and
sequencing rules. Second, it would be interesting to integrate individual no-
show predictions into our robust framework. Third, the concept of minimizing
costs under robust service levels is applicable to any service in which
customer disutility increases sharply upon surpassing a critical threshold.
Identifying such services and studying the corresponding problem variants
seems promising.

## References

  * Ahmadi-Javid et al. (2017) Ahmadi-Javid A, Jalali Z, Klassen KJ (2017) Outpatient appointment systems in healthcare: A review of optimization studies. _European Journal of Operational Research_ 258(1):3–34.
  * Bae and Fabry (2014) Bae SH, Fabry D (2014) Assessing the relationships between nurse work hours/overtime and nurse and patient outcomes: systematic literature review. _Nursing outlook_ 62(2):138–156.
  * Bendavid et al. (2018) Bendavid I, Marmor YN, Shnits B (2018) Developing an optimal appointment scheduling for systems with rigid standby time under pre-determined quality of service. _Flexible Services and Manufacturing Journal_ 30(1):54–77.
  * Benjaafar et al. (2023) Benjaafar S, Chen D, Wang R, Yan Z (2023) Appointment scheduling under a service-level constraint. _Manufacturing & Service Operations Management_ 25(1):70–87.
  * Bertsimas et al. (2011) Bertsimas D, Farias VF, Trichakis N (2011) The price of fairness. _Operations Research_ 59(1):17–31.
  * Bertsimas and Sim (2004) Bertsimas D, Sim M (2004) The price of robustness. _Operations Research_ 52(1):35–53.
  * Bielen and Demoulin (2007) Bielen F, Demoulin N (2007) Waiting time influence on the satisfaction-loyalty relationship in services. _Managing Service Quality: An International Journal_ 17(2):174–193.
  * Bosch (1997) Bosch PMV (1997) Scheduling and sequencing arrivals to a stochastic service system. Doctoral Dissertation, Air Force Institute of Technology. ProQuest Dissertations and Theses Database (AAT 9813076).
  * Bouch et al. (2000) Bouch A, Kuchinsky A, Bhatti N (2000) Quality is in the eye of the beholder: Meeting users’ requirements for internet quality of service. _Proceedings of the SIGCHI Conference on Human Factors in Computing Systems 2000_ , 297–304.
  * Boyd and Vandenberghe (2004) Boyd S, Vandenberghe L (2004) _Convex Optimization_ , 278 (Cambridge University Press).
  * Cayirli and Veral (2003) Cayirli T, Veral E (2003) Outpatient scheduling in health care: a review of literature. _Production and Operations Management_ 12(4):519–549.
  * Cayirli et al. (2008) Cayirli T, Veral E, Rosen H (2008) Assessment of patient classification in appointment system design. _Production and Operations Management_ 17(3):338–353.
  * Davis and Heineke (1998) Davis MM, Heineke J (1998) How disconfirmation, perception and actual waiting times impact customer satisfaction. _International Journal of Service Industry Management_ 9(1):64–73.
  * de Kemp et al. (2021) de Kemp MA, Mandjes M, Olver N (2021) Performance of the smallest-variance-first rule in appointment sequencing. _Operations Research_ 69(6):1909–1935.
  * Deceuninck et al. (2018) Deceuninck M, Fiems D, De Vuyst S (2018) Outpatient scheduling with unpunctual patients and no-shows. _European Journal of Operational Research_ 265(1):195–207.
  * Denton and Gupta (2003) Denton B, Gupta D (2003) A sequential bounding approach for optimal appointment scheduling. _IIE Transactions_ 35(11):1003–1016.
  * Garey and Johnson (1979) Garey MR, Johnson DS (1979) _Computers and intractability: A guide to the theory of NP-hardness_ (San Fransisco: WH Freeman).
  * Goitein and Jermann (2003) Goitein M, Jermann M (2003) The relative costs of proton and X-ray radiation therapy. _Clinical Oncology_ 15(1):S37–S50.
  * Gupta and Denton (2008) Gupta D, Denton B (2008) Appointment scheduling in health care: Challenges and opportunities. _IIE Transactions_ 40(9):800–819.
  * Hill and Joonas (2005) Hill CJ, Joonas K (2005) The impact of unacceptable wait time on health care patients’ attitudes and actions. _Health Marketing Quarterly_ 23(2):69–87.
  * Huang (1994) Huang XM (1994) Patient attitude towards waiting in an outpatient clinic and its applications. _Health Services Management Research_ 7(1):2–8.
  * Issabakhsh et al. (2021) Issabakhsh M, Lee S, Kang H (2021) Scheduling patient appointment in an infusion center: a mixed integer robust optimization approach. _Health Care Management Science_ 24(1):117–139.
  * Jafarnia-Jahromi and Jain (2020) Jafarnia-Jahromi M, Jain R (2020) Non-indexability of the stochastic appointment scheduling problem. _Automatica_ 118:109016.
  * Jiang et al. (2017) Jiang R, Shen S, Zhang Y (2017) Integer programming approaches for appointment scheduling with random no-shows and service durations. _Operations Research_ 65(6):1638–1656.
  * Kong et al. (2016) Kong Q, Lee CY, Teo CP, Zheng Z (2016) Appointment sequencing: Why the smallest-variance-first rule may not be optimal. _European Journal of Operational Research_ 255(3):809–821.
  * Kong et al. (2020) Kong Q, Li S, Liu N, Teo CP, Yan Z (2020) Appointment scheduling under time-dependent patient no-show behavior. _Management Science_ 66(8):3480–3500.
  * Kumar et al. (1997) Kumar P, Kalwani MU, Dada M (1997) The impact of waiting time guarantees on customers’ waiting experiences. _Marketing Science_ 16(4):295–314.
  * Mak et al. (2015) Mak HY, Rong Y, Zhang J (2015) Appointment scheduling with limited distributional information. _Management Science_ 61(2):316–334.
  * Mittal et al. (2014) Mittal S, Schulz AS, Stiller S (2014) Robust appointment scheduling. _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)_ , volume 28 of _Leibniz International Proceedings in Informatics_ , 356–370.
  * Moschis et al. (2003) Moschis GP, Bellenger DN, Curasi CF (2003) What influences the mature consumer? _Marketing Health Services_ 23(4):16–21.
  * Qi (2017) Qi J (2017) Mitigating delays and unfairness in appointment systems. _Management Science_ 63(2):566–583.
  * Robinson and Chen (2003) Robinson LW, Chen RR (2003) Scheduling doctors’ appointments: optimal and empirically-based heuristic policies. _IIE Transactions_ 35(3):295–307.
  * Roels and Staats (2021) Roels G, Staats BR (2021) OM forum—people-centric operations: Achievements and future research directions. _Manufacturing & Service Operations Management_ 23(4):745–757.
  * Samorani et al. (2021) Samorani M, Harris SL, Blount LG, Lu H, Santoro MA (2021) Overbooked and overlooked: machine learning and racial bias in medical appointment scheduling. _Manufacturing & Service Operations Management_ 24(6):2825–2842.
  * Sang et al. (2021) Sang P, Begen MA, Cao J (2021) Appointment scheduling with a quantile objective. _Computers & Operations Research_ 132:105295.
  * Schulz and Udwani (2019) Schulz AS, Udwani R (2019) Robust appointment scheduling with heterogeneous costs. _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)_ , volume 145 of _Leibniz International Proceedings in Informatics_ , 25:1–25:17.
  * Taylor and Baker (1994) Taylor SA, Baker TL (1994) An assessment of the relationship between service quality and customer satisfaction in the formation of consumers’ purchase intentions. _Journal of Retailing_ 70(2):163–178.
  * Welch and Bailey (1952) Welch J, Bailey NJ (1952) Appointment systems in hospital outpatient departments. _The Lancet_ 259(6718):1105–1108.
  * Zhou et al. (2022) Zhou M, Loke GG, Bandi C, Liau ZQG, Wang W (2022) Intraday scheduling with patient re-entries and variability in behaviours. _Manufacturing & Service Operations Management_ 24(1):561–579.

Online Supplement

The appendix is organized as follows: Section 7 presents additional proofs not
included in the main paper. In Section 8, we detail the step-by-step
derivation of the general MILP from Section 3.3.2, considering no-shows.
Section 9 provides further explanations of interappointment times from Section
4.3. Lastly, Section 10 covers details of the computational study, including
instance generation, sensitivity analysis, and the comparison to the
utilitarian approach.

Table 7: Notation Index sets: |  | $i\in[n]$ |  | appointments (sorted in the order of service receipt)
---|---|---|---|---
|  | $j\in[n]$ |  | customers
Scenarios: |  | $p\in\mathcal{P}$ |  | service times
|  | $\lambda\in\Lambda_{k}$ |  | no-shows
Parameters: |  | $L$ |  | length of the planning horizon
|  | $k$ |  | number of customers showing up
|  | $W_{j}$ |  |  waiting time guarantee for customer $j$
|  | $c_{i}$ |  |  unit cost for idle time before appointment $i$
|  | $c_{o}$ |  | unit cost for overtime
Variables: |  | $A_{i}$ |  |  appointment time of appointment $i$
|  | $C_{i}$ |  |  completion time of appointment $i$
|  | $\pi_{ij}$ |  |  assignment of customer $j$ to appointment $i$

##  7 Proofs

This section of the appendix contains the proofs for the results presented in
the main part of this paper. In contrast to the main part, where the findings
were organized for ease of understanding and applicability, here we structure
the proofs to build upon previously established results.

First, we reformulate the definition of completion times, adopting a non-
recursive computation approach. This reformulation allows for an essential
transformation of idle times into non-negative blocks. Additionally, the
reformulation of completion times facilitates to prove a crucial decomposition
of worst-case scenarios for cost maximization, dividing them into two parts:
the first one maximizing idle time and the other maximizing overtime. We
demonstrate that considering $n+1$ service time scenarios is sufficient to
maximize worst-case costs, and effectively linearize the search for
corresponding worst-case no-show scenarios. By leveraging these findings, we
establish the ASAP scheduling rule, followed by the SVF-WTG sequencing rule,
and ultimately prove $\mathcal{NP}$-hardness.

###### Lemma 7.1

For any service time scenario $p\in\mathcal{P}$ and no-show scenario
$\lambda\in\Lambda_{k}$, the completion time of appointment $i\in[n]$ equals

$\displaystyle
C_{i}=\max_{l\in[1,i]}\left({A}_{l}+\sum\limits_{k=l}^{i}\sum\limits_{j=1}^{n}\pi_{kj}\lambda_{j}p_{j}\right).$
(23)

###### Proof 7.2

Proof of Lemma 7.1. We prove by induction that the recursive computation of
the completion times
$\max\left\\{{A}_{i},C_{i-1}\right\\}+\sum_{j=1}^{n}\pi_{ij}\lambda_{j}p_{j}$
is equivalent to the maximization problem
$\max_{l\in[1,i]}\left({A}_{l}+\sum_{\sigma=l}^{i}\sum_{j=1}^{n}\pi_{\sigma
j}\lambda_{j}p_{j}\right)$. For $i=1$, the terms are equivalent. Suppose the
claim is true for all appointments $1,\ldots,i-1$. Then the recursive
definition of the completion time for appointment $i$ is equivalent to
$\max\left\\{{A}_{i},\max_{l\in[1,i-1]}\left({A}_{l}+\sum_{\sigma=l}^{i-1}\sum_{j=1}^{n}\pi_{\sigma
j}\lambda_{j}p_{j}\right)\right\\}+\sum_{j=1}^{n}\pi_{ij}\lambda_{j}p_{j}.$
Taking the last summand into the maximization problem renders this equivalent
to the above maximization problem.

$\square$

###### Proof 7.3

Proof of Lemma 3.8 (page 3.8). Given a customer sequence $\pi$, appointment
times $A$, and waiting time guarantees $W_{1},\ldots,W_{n}$, it clearly holds

$\displaystyle\max\limits_{p\in\mathcal{P},\lambda\in\Lambda_{k-1}}\left\\{\max\limits_{i\in[n]}\left\\{C_{i-1}(A,\pi,p,\lambda)-A_{i}-\sum_{j=1}^{n}\pi_{ij}W_{j}\right\\}\right\\}$
$\displaystyle\leq$
$\displaystyle\max\limits_{i\in[n]}\left\\{\max\limits_{p^{(i)}\in\mathcal{P},\lambda^{(i)}\in\Lambda_{k-1}}\left\\{C_{i-1}(A,\pi,p^{(i)},\lambda^{(i)})-A_{i}-\sum_{j=1}^{n}\pi_{ij}W_{j}\right\\}\right\\}.$

Assume the inequality holds strictly (i.e., with ”$<$”). Let
$i^{*},p^{*},\lambda^{*}$ maximize the right-hand side. Then, for any $A\geq
0$, we obtain

$\displaystyle
C_{i^{*}-1}(A,\pi,p^{*},\lambda^{*})-A_{i^{*}}-\sum_{j=1}^{n}\pi_{i^{*}j}W_{j}$
$\displaystyle\leq$
$\displaystyle\max_{i\in[n]}\left\\{C_{i-1}(A,\pi,p^{*},\lambda^{*})-A_{i}-\sum_{j=1}^{n}\pi_{ij}W_{j}\right\\}$
$\displaystyle\leq$
$\displaystyle\max_{p\in\mathcal{P},\lambda\in\Lambda_{k-1}}\left\\{\max_{i\in[n]}\left\\{C_{i-1}(A,\pi,p,\lambda)-A_{i}-\sum_{j=1}^{n}\pi_{ij}W_{j}\right\\}\right\\}$
$\displaystyle<$
$\displaystyle\max\limits_{i\in[n]}\left\\{\max\limits_{p^{(i)}\in\mathcal{P},\lambda^{(i)}\in\Lambda_{k-1}}\left\\{C_{i-1}(A,\pi,p^{(i)},\lambda^{(i)})-A_{i}-\sum_{j=1}^{n}\pi_{ij}W_{j}\right\\}\right\\}$
$\displaystyle=C_{i^{*}-1}(A,\pi,p^{*},\lambda^{*})-A_{i^{*}}-\sum_{j=1}^{n}\pi_{i^{*}j}W_{j},$

which is a contradiction.

$\square$

###### Lemma 7.4

Let $\pi$ be an assignment, $(A_{i})_{i\in[n]}$ appointment times,
$p\in\mathcal{P}$ a service time scenario, and $\lambda\in\Lambda_{k}$ a no-
show scenario. Moreover, let
$\\{i\in[n]:(A_{i}-C_{i-1})>0\\}=\\{i_{1},\ldots,i_{r}\\}=:I$ with
$i_{1}\leq\ldots\leq i_{r}$ denote the index set of appointments before which
positive idle time occurs. Then the idle time cost
$\sum_{i=1}^{n+1}c_{i}(A_{i}-C_{i-1})^{+}$ is equivalent to

$\sum_{l=1}^{r-1}(c_{i_{l}}-c_{i_{l+1}})A_{i_{l}}+c_{i_{r}}A_{i_{r}}-c_{i_{1}}A_{1}-\sum_{l=1}^{r}{c_{i_{l}}}\sum_{{\sigma}=i_{l-1}}^{i_{l}-1}{\lambda}_{{\sigma}}{p}_{{\sigma}}.$

###### Proof 7.5

Proof of Lemma 7.4. Assume w.l.o.g. that $\pi=id$. For each $i\in I$, let
$l(i)$ denote the smallest index such that
$C_{i-1}=A_{l(i)}+\sum\limits_{\sigma=l(i)}^{i-1}{p}_{\sigma}{\lambda}_{\sigma}$
(see Lemma 7.1).

We show that $l(i_{j})=i_{j-1}$ for all $j\in[r]$, $j\geq 2$, via a proof by
contradiction. First assume that $l(i_{j+1})<i_{j}$, and for the purpose of
simpler notation, let w.l.o.g. $j=2$. On the one hand, Theorem 7.1 implies
that $C_{i_{2}-1}\geq
A_{i_{1}}+\sum_{{\sigma}=i_{1}}^{i_{2}-1}{p}_{\sigma}{\lambda}_{\sigma}$. On
the other hand, it holds that
$C_{i_{2}-1}=A_{l(i_{2})}+\sum_{{\sigma}=l(i)}^{i_{1}-1}{p}_{\sigma}{\lambda}_{\sigma}+\sum_{{\sigma}=i_{1}}^{i_{2}-1}{p}_{\sigma}{\lambda}_{\sigma}\leq
C_{i_{1}-1}+\sum_{{\sigma}=i_{1}}^{i_{2}-1}{p}_{\sigma}{\lambda}_{\sigma}$.
Together, it follows that $C_{i_{1}-1}\geq A_{i_{1}}$, a contradiction to
$i_{1}\in I$. Therefore, $l(i_{2})\geq i_{1}$.
Now assume that $l(i_{2})>i_{1}$. On the one hand, as $l(i_{2})$ is the
smallest index with the above property, it must hold that
$C_{i_{2}-1}>A_{i_{1}}+\sum_{{\sigma}=i_{1}}^{i_{2}-1}{p}_{\sigma}{\lambda}_{\sigma}$.
On the other hand, because now $l(i_{2})\notin I$, it holds that $A_{i}\leq
C_{i-1}$ for all $i\in[i_{1}+1,l(i_{2})]$ and therefore
$C_{i_{2}-1}=A_{l(i_{2})}+\sum_{{\sigma}=l(i_{2})}^{i_{2}-1}{p}_{\sigma}{\lambda}_{\sigma}\leq
C_{l(i_{2})-1}+\sum_{{\sigma}=l(i_{2})}^{i_{2}-1}{p}_{\sigma}{\lambda}_{\sigma}=\max\\{C_{l(i_{2})-2},A_{l(i_{2})-1}\\}+\sum_{{\sigma}=l(i_{2})-1}^{i_{2}-1}{p}_{\sigma}{\lambda}_{\sigma}\leq\ldots\leq
A_{i_{1}}+\sum_{{\sigma}=i_{1}}^{i_{2}-1}{p}_{\sigma}{\lambda}_{\sigma}$.
Together this yields the contradiction $A_{i_{1}}\geq
C_{i_{2}-1}-\sum_{{\sigma}=i_{1}}^{i_{2}-1}{p}_{\sigma}{\lambda}_{\sigma}>A_{i_{1}}$,
from which it finally follows that $l(i_{2})=i_{1}$.

The above argument for $l(i_{2})\leq i_{1}$ can be equivalently applied to
show that $l(i_{1})=1$, so we define $i_{0}:=1$. Altogether, this yields:

$\displaystyle\sum_{i=1}^{n+1}c_{i}\left(A_{i}-C_{i-1}\right)^{+}$ (24)
$\displaystyle=$
$\displaystyle\sum_{l=1}^{r}c_{i_{l}}\left(A_{i_{l}}-C_{{i_{l}}-1}\right)$
(25) $\displaystyle=$
$\displaystyle\sum_{l=1}^{r}c_{i_{l}}\left(A_{i_{l}}-A_{i_{l-1}}-\sum_{k=i_{l-1}}^{i_{l}-1}{p}_{k}{\lambda}_{k}\right)$
(26) $\displaystyle=$
$\displaystyle\sum_{l=1}^{r-1}\left(c_{i_{l}}-c_{i_{l+1}}\right)A_{i_{l}}+c_{i_{r}}A_{i_{r}}-c_{i_{1}}A_{i_{0}}-\sum_{l=1}^{r}{c_{i_{l}}}\sum_{{\sigma}=i_{l-1}}^{i_{l}-1}{\lambda}_{{\sigma}}{p}_{{\sigma}}$
(27)

$\square$

###### Proof 7.6

Proof of Theorem 3.6 (page 3.6). We show that any service time scenario that
maximizes total cost can be decomposed into two parts: the first one
maximizing idle time and the second one maximizing overtime. Assume w.l.o.g.
that $\pi=id$.

First, using the reformulation of the completion times from Lemma 7.1, we
find:

$\displaystyle\sum_{i=1}^{n+1}c_{i}\left(A_{i}-C_{i-1}(\pi,A,p,\lambda)\right)^{+}+c_{o}\left(C_{n}(\pi,A,p,\lambda)-A_{n+1}\right)^{+}$
(28) $\displaystyle=$
$\displaystyle\sum_{i=1}^{n}c_{i}\left(A_{i}-C_{i-1}(\pi,A,p,\lambda)\right)^{+}+\max\left\\{c_{n+1}\left(A_{n+1}-C_{n}(\pi,A,p,\lambda)\right),c_{o}(C_{n}(\pi,A,p,\lambda)-A_{n+1})\right\\}$
(29) $\displaystyle=$ $\displaystyle
c_{1}A_{1}+\sum_{i=2}^{n}c_{i}\left(A_{i}-\max_{l\in[i-1]}\left\\{A_{l}+\sum_{k=l}^{i-1}\lambda_{k}p_{k}\right\\}\right)^{+}$
(30)
$\displaystyle+\max\left\\{c_{n+1}\left(A_{n+1}-\max_{l\in[n]}\left\\{A_{l}+\sum_{k=l}^{n}\lambda_{k}p_{k}\right\\}\right),c_{o}\left(\max_{l\in[n]}\left\\{A_{l}+\sum_{k=l}^{n}\lambda_{k}p_{k}\right\\}-A_{n+1}\right)\right\\}$
(31)

Now, let $\lambda\in\Lambda_{k}$ and let the service time scenario
$p^{opt}\in\mathcal{P}$ maximize total cost
$\sum_{i=2}^{n+1}c_{i}\left(A_{i}-C_{i-1}(\pi,A,p,\lambda)\right)^{+}+c_{o}\left(C_{n}(\pi,A,p,\lambda)-A_{n+1}\right)^{+}$.
We distinguish the following two cases.

_Case 1: $A_{n+1}-C_{n}(\pi,A,p^{opt},\lambda)\geq 0$._

In this case, overtime cost equals zero. Therefore, setting ${p}_{i}^{opt}$ to
$\underline{p}_{i}$ for each $i\in[n]$ will lead to an equal or higher value
of (30)–(31).

_Case 2: $C_{n}(\pi,A,p^{opt},\lambda)-A_{n+1}\geq 0$._

In this case, there are non-negative overtime costs. Let $l^{*}\in[n]$ chosen
minimally such that
$C_{n}(\pi,A,p^{opt},\lambda)=A_{l^{*}}+\sum_{k=l^{*}}^{n}\lambda_{k}p_{k}^{opt}$.
In particular, it is easy to see that idle time cannot occur after the
$l^{*}$th appointment. Then setting $p^{opt}_{i}$ to $\bar{p}_{i}$ for all
$i\geq l^{*}$ and to $\underline{p}_{i}$ for all $i\leq l^{*}-1$ will again
lead to an equal or higher value of (30)–(31).

$\square$

######  Remark 7.7 (Additional Mixed-Integer Linear Reformulation Techniques)

For each $i^{*}\in\\{0,\ldots,n+1\\}$ and $i\in[n]$, let
$z_{i^{*}i}\in\\{0,1\\}$ be auxiliary binary variables and
$M\geq\max_{i\in[n]}\max\\{A_{i},C_{i^{*},i-1}\\}$ an upper bound for the
latest realized start time of any appointment, for example,
$M:=A_{1}+\sum_{j=1}^{n}\bar{p}_{j}$. Then
$C_{i^{*}i}=\max\left\\{{A_{i},C_{i^{*}i-1}}\right\\}+\sum_{j=1}^{n}\lambda_{i^{*}ij}\ubar{p}_{j}$
can be linearized as follows:

$\displaystyle C_{i^{*}i}\geq
A_{i}+\sum_{j=1}^{n}\lambda_{ij}^{(i^{*},1)}\ubar{p}_{j}$
$\displaystyle\forall i\in[n]$ (32) $\displaystyle C_{i^{*}i}\geq
C_{i^{*},i-1}+\sum_{j=1}^{n}\lambda_{ij}^{(i^{*},1)}\ubar{p}_{j}$
$\displaystyle\forall i\in[n]$ (33) $\displaystyle C_{i^{*}i}\leq
A_{i}+\sum_{j=1}^{n}\lambda_{ij}^{(i^{*},1)}\ubar{p}_{j}+z_{i^{*}i}M$
$\displaystyle\forall i\in[n]$ (34) $\displaystyle C_{i^{*}i}\leq
C_{i^{*},i-1}+\sum_{j=1}^{n}\lambda_{ij}^{(i^{*},1)}\ubar{p}_{j}+(1-z_{i^{*}i})M$
$\displaystyle\forall i\in[n]$ (35)

###### Proof 7.8

Proof of Theorem 4.2 (page 4.2). It is straightforward to see that Algorithm 1
runs in polynomial time with the fact that line 5 in Algorithm 1 constitutes a
linear program with only $O(n)$ variables and constraints.

The waiting time constraints enforce that
$A_{i}\geq\left(\max_{l\in[i-1]}A_{l}+U_{l}-\sum_{j=1}^{n}\pi_{ij}W_{j}\right)^{+}$
for all $i\in[2,n]$. We now show that, if $A_{1}=0$, then
$A_{i}=\left(\max_{l\in[i-1]}A_{l}+U_{l}-\sum_{j=1}^{n}\pi_{ij}W_{j}\right)^{+}$
for $i\in[2,n]$ is an optimal solution in the case of non-increasing idle time
costs.

Let $A^{*}$ be optimal appointment times with
$A^{*}_{i^{\prime}}>\left(\max_{l\in[i^{\prime}-1]}A_{l}^{*}+U_{l}-\sum_{j=1}^{n}\pi_{i^{\prime}j}W_{j}\right)^{+}$
for some $i^{\prime}\in[2,n]$. As $c_{i-1}-c_{i}\geq 0$ for all $i\in[2,n]$,
and using the cost reformulation 24–27 in the proof of Lemma 7.4 with
corresponding index set $\mathcal{I}$, we distinguish the following two cases.
Firstly, if $i^{\prime}\in\mathcal{I}$, then choosing
$A^{*}_{i^{\prime}}=\left(\max_{l\in[i^{\prime}-1]}A_{l}^{*}+U_{l}-\sum_{j=1}^{n}\pi_{i^{\prime}j}W_{j}\right)^{+}$
leads to a better objective value, contradicting the optimality of $A^{*}$.
Secondly, if $i^{\prime}\in\mathcal{I}$, then choosing
$A^{*}_{i^{\prime}}=\left(\max_{l\in[i^{\prime}-1]}A_{l}^{*}+U_{l}-\sum_{j=1}^{n}\pi_{i^{\prime}j}W_{j}\right)^{+}$
does not change the optimal solution value. Thus, it is optimal to schedule
each appointment time $A_{i}$, $i\in[n]$, as early as possible.

$\square$

######  Remark 7.9 (Increasing idle time costs)

The case of increasing idle time costs seems to be more difficult, as a
balance must be found between the following strategies. On the one hand, the
last appointment should be scheduled as early as possible to avoid both idle
time and overtime. On the other hand, later idle times are more costly than
early idle times and can only be prevented by scheduling later appointments
with relatively long worst-case waiting times. To allow for longer worst-case
waiting times for later appointments while still fulfilling all waiting time
guarantees, early appointments may need to be scheduled later than necessary
due to the waiting time constraints. This may delay the appointment time of
the last appointment.

###### Proof 7.10

Proof of Lemma 4.1 (page 4.1). Consider an optimal sequence $\pi^{*}$ that
does not adhere to the SVF-WTG sequencing rule. Then there exists
$i^{\prime},j^{\prime},j^{\prime\prime}\in[n]$ satisfying
$\pi_{i^{\prime},j^{\prime}}^{*},\pi_{i^{\prime}+1,j^{\prime\prime}}^{*}=1$
and
$\bar{p}_{j^{\prime}}-\ubar{p}_{j^{\prime}}+W_{j^{\prime}}(1+c_{o})>\bar{p}_{j^{\prime\prime}}-\ubar{p}_{j^{\prime\prime}}+W_{j^{\prime\prime}}(1+c_{o})$.
To establish the optimality of the SVF-WTG sequencing rule, we prove that
(iteratively) swapping the positions of customers $j^{\prime}$ and
$j^{\prime\prime}$ does not increase the optimal worst-case cost
$\max_{i^{*}\in\\{0,\ldots,n+1\\}}\sum_{i=1}^{i^{*}}c_{i}\left(A_{i}-\ubar{C}_{i-1}(\pi^{*},A)\right)^{+}+c_{o}\left(A_{i^{*}}+\sum_{i=i^{*}}^{n}\pi_{ij}^{*}\bar{p}_{j}-L\right)^{+}=:opt$.

Since the idle time costs are constant and all customers show up, we know from
a special case of Theorem 4.2 that $A_{1}=0$ and
$A_{i}=\left(\sum_{k=1}^{i-1}\sum_{j=1}^{n}\pi_{kj}^{*}\bar{p}_{j}-\sum_{j=1}^{n}\pi_{ij}^{*}W_{j}\right)^{+}$
are optimal appointment times for $i\in[2,n]$.

First, we consider the costs associated with the case $i^{*}\in\\{0,n+1\\}$.
For $i^{*}=n+1$, using the idle time cost reformulation 27 from Lemma 7.4, the
total cost is equivalent to
$c_{n+1}(L-\sum_{i=1}^{n}\sum_{j=1}^{n}\pi_{ij}^{*}\ubar{p}_{j})$, and
swapping the position of two customers does not affect this value. For
$i^{*}=0$, where there is no idle time, swapping two customers does not affect
the value.

For each $i^{*}\in[n]$, the associated cost is
$\sum_{i=1}^{i^{*}}(A_{i}-\ubar{C}_{i-1}(\pi^{*},A))^{+}+c_{o}\left(A_{i^{*}}+\sum_{k=i^{*}}^{n}\pi_{kj}^{*}\bar{p}_{j}-L\right)$.
Moreover, we assume w.l.o.g. that
$A_{i^{*}}=\sum_{k=1}^{i^{*}-1}\sum_{j=1}^{n}\pi_{kj}^{*}\bar{p}_{j}-\sum_{j=1}^{n}\pi_{ij}^{*}W_{j}>0$.
Therefore, the total cost becomes
$\sum_{i=1}^{i^{*}}(A_{i}-\ubar{C}_{i-1}(\pi^{*},A))^{+}+c_{o}\left(\sum_{i=1}^{n}\sum_{j=1}^{n}\pi_{ij}^{*}\bar{p}_{j}-\sum_{j=1}^{n}\pi_{i^{*}j}W_{j}-L\right)$.
Using again the idle time cost reformulation 27 from Lemma 7.4, the sequence-
dependent value is:

$\displaystyle\sum_{i=1}^{i^{*}}(A_{i}-\ubar{C}_{i-1}(\pi^{*},A))^{+}-c_{o}\sum_{j=1}^{n}\pi_{i^{*}j}^{*}W_{j}$
$\displaystyle=$ $\displaystyle
A_{i^{*}}-\sum_{k=1}^{i^{*}-1}\sum_{j=1}^{n}\pi_{kj}^{*}\ubar{p}_{j}-c_{o}\sum_{j=1}^{n}\pi_{i^{*}j}^{*}W_{j}$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{i^{*}-1}\sum_{j=1}^{n}\pi_{kj}^{*}\bar{p}_{j}-\sum_{j=1}^{n}\pi_{i^{*}j}^{*}W_{j}-\sum_{k=1}^{i^{*}-1}\sum_{j=1}^{n}\pi_{kj}^{*}\ubar{p}_{j}-c_{o}\sum_{j=1}^{n}\pi_{i^{*}j}^{*}W_{j}$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{i^{*}-1}\sum_{j=1}^{n}\pi_{kj}^{*}(\bar{p}_{j}-\ubar{p}_{j})-(1+c_{o})\sum_{j=1}^{n}\pi_{i^{*}j}^{*}W_{j}.$

We now show that changing the sequence to
$\pi_{i^{\prime},j^{\prime\prime}},\pi_{i^{\prime}+1,j^{\prime}}=1$, the cost
associated with each $i^{*}\in[n]$ does not exceed the optimal solution value
obtained with $\pi^{*}$.

For each $i^{*}>i^{\prime}+1$ or $i^{*}<i^{\prime}$, the solution value does
not change when changing the sequence to
$\pi_{i^{\prime},j^{\prime\prime}},\pi_{i^{\prime}+1,j^{\prime}}=1$. For
$i^{*}=i^{\prime}$, we find

$\displaystyle\sum_{k=1}^{i^{*}-1}\sum_{j=1}^{n}\pi_{kj}^{*}(\bar{p}_{j}-\ubar{p}_{j})-(1+c_{o})\sum_{j=1}^{n}\pi_{i^{*}j}^{*}W_{j}$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{i^{*}-1}\sum_{j=1}^{n}\pi_{kj}^{*}(\bar{p}_{j}-\ubar{p}_{j})-(1+c_{o})W_{j^{\prime}}$
$\displaystyle<$
$\displaystyle\sum_{k=1}^{i^{*}-1}\sum_{j=1}^{n}\pi_{kj}^{*}(\bar{p}_{j}-\ubar{p}_{j})+\bar{p}_{j^{\prime}}-\ubar{p}_{j^{\prime}}-(\bar{p}_{j^{\prime\prime}}-\ubar{p}_{j^{\prime\prime}}+W_{j^{\prime\prime}}(1+c_{o}))$
$\displaystyle\leq$
$\displaystyle\sum_{k=1}^{i^{*}}\sum_{j=1}^{n}\pi_{kj}^{*}(\bar{p}_{j}-\ubar{p}_{j})-W_{j^{\prime\prime}}(1+c_{o})$
$\displaystyle\leq$ $\displaystyle\,opt-
c_{o}\left(\sum_{j=1}^{n}\bar{p}_{j}-L\right)$

and therefore, changing the sequence to
$\pi_{i^{\prime},j^{\prime\prime}},\pi_{i^{\prime}+1,j^{\prime}}=1$ does not
increase the optimal solution value for the case of $i^{*}=i^{\prime}$.
Finally, for $i^{*}=i^{\prime}+1$, it is easy to see that switching the
position of $j^{\prime}$ and $j^{\prime\prime}$ improves the associated costs:

$\displaystyle\sum_{k=1}^{i^{*}-2}\sum_{j=1}^{n}\pi_{kj}^{*}(\bar{p}_{j}-\ubar{p}_{j})+\bar{p}_{j^{\prime}}-\ubar{p}_{j^{\prime}}-(1+c_{o})W_{j^{\prime\prime}}$
$\displaystyle>$
$\displaystyle\sum_{k=1}^{i^{*}-2}\sum_{j=1}^{n}\pi_{kj}^{*}(\bar{p}_{j}-\ubar{p}_{j})+\bar{p}_{j^{\prime\prime}}-\ubar{p}_{j^{\prime\prime}}-(1+c_{o})W_{j^{\prime}}$

We note that $i^{*}=i^{\prime}+1$ cannot have been the maximizer of the total
worst-case cost, as this would contradict the optimality of $\pi^{*}$.

Thus, (iteratively) applying the SVF-WTG rule does not increase the total
worst-case cost.

$\square$

###### Proof 7.11

Proof of Theorem 3.4 (page 3.4). We establish the $\mathcal{NP}$-hardness of
the RASWTG problem for the case that all customers show up, have identical
waiting time guarantees $W$, and the idle time costs satisfy
$c_{1}=\ldots=c_{\sigma}>c_{\sigma+1}=\ldots=c_{n}$ for some $\sigma\in[n-1]$
and the overtime cost $c_{o}=0$. To simplify the notation, let $\epsilon$ be a
real number such that $L=\sum_{j=1}^{n}\bar{p}_{j}-W+\epsilon=:A_{n+1}$.

First, we employ Theorem 3.6 to reformulate the objective function as
$\min_{\pi,A}\left\\{\max_{i^{*}\in\\{0,\ldots,n+1\\}}\sum_{i=1}^{i^{*}}c_{i}(A_{i}-\ubar{C}_{i-1}(\pi,A))^{+}+c_{o}\left(A_{i^{*}}+\sum_{k=l^{*}}^{n}\sum_{j=1}^{n}\pi_{kj}\bar{p}_{j}-L\right)^{+}\right\\}$.
Since the overtime cost fulfill $c_{o}=0$, it suffices to consider
$i^{*}\in\\{n+1\\}$. Moreover, using Theorem 4.2, the appointment start times
can be calculated as $A_{1}=0$,
$A_{i}=(\sum_{l=1}^{i-1}\sum_{j=1}^{n}\pi_{lj}\bar{p}_{j}-W)^{+}$ for
$i\in\\{2,\ldots,n\\}$. Therefore, the worst-case cost equals:

$\displaystyle\sum\limits_{i=2}^{n+1}c_{i}\left(A_{i}-\ubar{C}_{i-1}(\pi,A)\right)^{+}$
$\displaystyle=$
$\displaystyle\sum\limits_{i=2}^{n+1}c_{i}\left(\sum\limits_{k=1}^{i-1}\sum\limits_{j=1}^{n}\pi_{kj}\bar{p}_{j}-W-\max\left\\{\sum_{k=1}^{i-1}\sum_{j=1}^{n}\pi_{kj}\ubar{p}_{j},\max_{l\in[i-1]}\left(\sum_{k=1}^{l-1}\sum_{j=1}^{n}\pi_{kj}\bar{p}_{j}+\sum_{k=l}^{i-1}\sum_{j=1}^{n}\pi_{kj}{\ubar{p}_{j}}\right)-W\right\\}\right)^{+}+c_{n+1}\epsilon$
$\displaystyle=$
$\displaystyle\sum\limits_{i=2}^{n+1}c_{i}\underbrace{\left(\min\left\\{\sum\limits_{k=1}^{i-1}\sum\limits_{j=1}^{n}\pi_{kj}(\bar{p}_{j}-\ubar{p}_{j})-W,\sum_{j=1}^{n}\pi_{i-1,j}(\bar{p}_{j}-{\ubar{p}_{j}})\right\\}\right)^{+}}_{:=s_{i}}+c_{n+1}\epsilon$

We observe that $\sum_{j=1}^{n}\pi_{i-1,j}(\bar{p}_{j}-{\ubar{p}_{j}})\geq 0$
holds for all $i\in[2,{n+1}]$ in the second term in $s_{i}$ and that $s_{i}=0$
if $\sum_{k=1}^{i-1}\sum_{j=1}^{n}\pi_{kj}(\bar{p}_{j}-\ubar{p}_{j})-W\leq 0$.
Let $l^{*}$ be the smallest index such that
$\sum_{k=1}^{l^{*}-1}\sum_{j=1}^{n}\pi_{kj}(\bar{p}_{j}-\ubar{p}_{j})-W\geq
0$. Then, for all $i>l^{*}$, it holds that
$\sum_{j=1}^{n}\pi_{i-1,j}(\bar{p}_{j}-{\ubar{p}_{j}})\leq\sum_{k=1}^{l^{*}-1}\sum_{j=1}^{n}\pi_{kj}(\bar{p}_{j}-\ubar{p}_{j})-W+\sum_{j=1}^{n}\pi_{i-1,j}(\bar{p}_{j}-{\ubar{p}_{j}})\leq\sum_{k=1}^{i-1}\sum_{j=1}^{n}\pi_{kj}(\bar{p}_{j}-\ubar{p}_{j})-W.$
Therefore, the worst-case cost finally becomes:

$\displaystyle\sum\limits_{i=1}^{n+1}c_{i}(A_{i}-\ubar{C}_{i-1})^{+}$ (36)
$\displaystyle=$ $\displaystyle
c_{l^{*}}\left(\sum\limits_{i=1}^{l^{*}-1}\sum\limits_{j=1}^{n}\pi_{ij}(\bar{p}_{j}-\ubar{p}_{j})-W\right)+\sum\limits_{i=l^{*}+1}^{n+1}c_{i}\sum\limits_{j=1}^{n}\pi_{i-1,j}(\bar{p}_{j}-\ubar{p}_{j})+c_{n+1}\epsilon.$
(37)

Now, we observe that the index $l^{*}$ is uniquely determined by the two
conditions:

  1. (i)

$\sum\limits_{i=1}^{l^{*}-1}\sum\limits_{j=1}^{n}\pi_{ij}(\bar{p}_{j}-\ubar{p}_{j})-W\geq
0$

  2. (ii)

$\sum\limits_{i=1}^{l^{*}-2}\sum\limits_{j=1}^{n}\pi_{ij}(\bar{p}_{j}-\ubar{p}_{j})-W<0$

Notably, even if
$\sum\limits_{i=1}^{l^{*}-2}\sum\limits_{j=1}^{n}\pi_{ij}(\bar{p}_{j}-\ubar{p}_{j})-W=0$,
then the worst-case sum of idle time equals (60). Therefore, the RASWTG
problem under consideration becomes:

$\displaystyle\min_{l^{*}\in[2,{n+1}]}\min_{\pi}\quad$ $\displaystyle
c_{l^{*}}\left(\sum\limits_{j=1}^{n}\sum\limits_{i=1}^{l^{*}-1}\pi_{ij}(\bar{p}_{j}-\ubar{p}_{j})\right)+\sum\limits_{j=1}^{n}\sum\limits_{i=l^{*}+1}^{n}\pi_{i-1,j}c_{i}(\bar{p}_{j}-\ubar{p}_{j})-c_{l^{*}}W+c_{n+1}\epsilon$
(38) s.t. $\displaystyle
W\leq\sum\limits_{i=1}^{l^{*}-1}\sum\limits_{j=1}^{n}\pi_{ij}(\bar{p}_{j}-\ubar{p}_{j})\leq
W+\sum\limits_{j=1}^{n}\pi_{l^{*}-1,j}(\bar{p}_{j}-{\ubar{p}}_{j})$ (39)
$\displaystyle\sum\limits_{j=1}^{n}\pi_{ij}=1,\sum\limits_{i=1}^{n}\pi_{ij}=1$
(40) $\displaystyle\pi\in\\{0,1\\}^{n\times n}$ (41)

We now reduce the following $\mathcal{NP}$-hard Subset Sum Problem (Garey and
Johnson 1979, p. 226) to a variant of (38) – (41).

$\displaystyle\max_{z}\quad$
$\displaystyle\sum\limits_{j=1}^{n}\alpha_{j}z_{j}$ (42) s.t.
$\displaystyle\sum\limits_{j=1}^{n}\alpha_{j}z_{j}\leq\beta$ (43)
$\displaystyle z\in\\{0,1\\}^{n}$ (44)

Defining $y_{j}:=1-z_{j}$ for all $j\in[n]$, the Subset Sum Problem is
equivalent to the following problem. In particular, denoting the optimal value
of the Subset Sum Problem by $OPT_{z}$ and the optimal value of the following
problem by $OPT_{y}$, it holds $OPT_{z}=\sum_{j=1}^{n}\alpha_{j}-OPT_{y}$.

$\displaystyle\min_{l^{*}\in[0,n]}\min_{y}\quad$
$\displaystyle\sum\limits_{j=1}^{n}\alpha_{j}y_{j}$ (45) s.t.
$\displaystyle\sum\limits_{j=1}^{n}\alpha_{j}-\beta\leq\sum\limits_{j=1}^{n}\alpha_{j}y_{j}$
(46) $\displaystyle\sum\limits_{j=1}^{n}y_{j}=l^{*}$ (47) $\displaystyle
y\in\\{0,1\\}^{n}$ (48)

If the $l^{*}$th problem is infeasible, we assign it a huge number. Now,
w.l.o.g. (the case $l^{*}=0$ is trivial to check), the latter problem is
equivalent to:

$\displaystyle\min_{l^{*}\in[n]}\min_{\pi}\quad$
$\displaystyle\sum\limits_{i=1}^{l^{*}}\sum\limits_{j=1}^{n}\alpha_{j}\pi_{ij}$
(49) s.t.
$\displaystyle\sum\limits_{j=1}^{n}\alpha_{j}-\beta\leq\sum\limits_{i=1}^{l^{*}}\sum\limits_{j=1}^{n}\alpha_{j}\pi_{ij}$
(50)
$\displaystyle\sum\limits_{j=1}^{n}\pi_{ij}=1,\sum\limits_{i=1}^{n}\pi_{ij}=1$
(51) $\displaystyle\pi_{ij}\in\\{0,1\\}^{n\times n}$ (52)

We can now use the similarity of (49) – (52) and (38) – (41). Let $\alpha$ and
$\beta$ be an instance for (49) – (52). For $l^{*}\in[n]$ choose $\bar{p}$,
$\ubar{p}$ fulfilling $\bar{p}_{j}-\ubar{p}_{j}:=\alpha_{j}$ for each
$j\in[n]$, $W:=\sum\limits_{j=1}^{n}\alpha_{j}-\beta$,
$c_{1}=\ldots=c_{l^{*}}:=1$, and $c_{l^{*}+1}=\ldots=c_{n+1}:=0$. Then solving
the $l^{*}$th subproblem of (49) – (52) is equivalent to solving the
respective $(l^{*}+1)$-st subproblem of (38) – (39). In particular, an optimal
solution $(i_{OPT},\pi_{OPT})$ also fulfills the second inequality in (39): If
for some $j\in[n]$ and $l\leq i_{OPT}$ such that $\pi_{lj}=1$ holds
$\sum\limits_{i\in[1,i_{OPT}]\setminus\\{l\\}}\sum_{j=1}^{n}\alpha_{j}\pi_{ij}>\sum\limits_{j=1}^{n}\alpha_{j}-\beta$,
then there exists a solution $(l^{*},\pi^{*})$, $l^{*}<i_{OPT}$ with smaller
solution value, which contradicts the optimality of $(i_{OPT},\pi_{OPT})$.

Thus, the problem (38) – (41), and therefore also the original problem, are
$\mathcal{NP}$-hard.

$\square$

##  8 Mixed-Integer Linear Program

We now derive and present the mixed-integer linear program for the Robust
Appointment Scheduling Problem with Waiting Time Guarantees, accounting for
$0\leq k\leq n$ no-shows. This involves linearizing the adversarial problems
related to maximizing waiting time for each customer and the most challenging
case of maximizing total cost.

##### Adversarial Problem of Maximizing Waiting Times.

We first address the problem of describing a no-show scenario
$\argmax_{\lambda\in\Lambda_{k},\lambda_{j}=1}\left\\{\max_{l\in[1,i-1]}\left({A}_{l}+\sum_{k=l}^{i-1}\sum_{j=1}^{n}\pi_{kj}{\lambda}_{j}\bar{p}_{j}\right)\right\\}$
that maximizes the completion time of the last appointment before appointment
$i\in[n]$, to which the $j$-th customer is assigned. Given the inner term
${A}_{l}+\sum_{k=l}^{i-1}\sum_{j=1}^{n}\pi_{kj}{\lambda}_{j}^{(i)}\bar{p}_{j}-A_{i}$,
$l\in[i-1]$, $i\in[n]$, in a worst-case no-show scenario, both the $j$-th
customer and as many as possible but at most $k-1$ of the previous $i-l$
customers show up, namely those with the longest maximum service times. Now,
following (Boyd and Vandenberghe 2004, p. 278) for the equivalent
max-$(k-1)$-sum problem, we can use total unimodularity of the constraint
matrix as well as duality to see that the objective value of
$\max_{{{\lambda}\in\Lambda_{k},{\lambda}_{j}=1}}\sum_{k=l}^{i-1}\sum_{j=1}^{n}\pi_{kj}{\lambda}_{j}\bar{p}_{j}$
equals $\min_{\alpha,z\geq
0}\left\\{(k-1)\,\alpha+\sum_{k=l}^{i-1}z_{k}\,|\,z_{k}+\alpha\geq\sum_{j=1}^{n}\pi_{kj}\bar{p}_{j}\right\\}.$
Therefore, for all appointments $i\in[n]$, $l\in[i-1]$ such that $i-l\geq k$,
the waiting time constraints in (2) can be formulated as

$\displaystyle A_{l}+\min_{\alpha,z\geq
0}\left\\{(k-1)\,\alpha+\sum_{j=1}^{n}z_{j}\,|\,\alpha+z_{j}\geq\sum\limits_{j=1}^{n}\pi_{kj}\bar{p}_{j}\,\forall
k\in[l,i-1]\right\\}-A_{i}\leq\sum_{j=1}^{n}\pi_{ij}W_{j}.$ (53)

##### Adversarial Problem of Maximizing Cost.

The problem of identifying the customers that show up when maximizing total
cost is more difficult. This is because a no-show not only incurs costs
proportional to the customer’s service time but also involves sequence-
dependent idle time and overtime costs. To tackle this issue, the following
lemma characterizes a worst-case no-show scenario structure. Specifically, it
becomes sufficient to consider, for each $i^{*}\in\\{1,\ldots,n+1\\}$, a no-
show scenario in which, among the customers scheduled for the last $n-i^{*}+1$
appointments, those with the longest maximum service times show up. If
$k>n-i^{*}+1$, all customers scheduled for these last appointment show up.
Additionally, among the customers scheduled for the first $i^{*}-1$
appointments, the $k-(n-i^{*}+1)$ ones with the smallest product of idle time
cost and minimum service time show up.

###### Lemma 8.1

Let $i^{*}\in\\{1,\ldots,n+1\\}$. For any no-show scenario
${\lambda}\in\Lambda_{k}$ and appointment $i\in[n]$, let
$c(i):=c_{\min\\{{l\in[i,n]:A_{l}-\ubar{C}_{l-1}(\pi,A,\lambda)>0\\}}}$ denote
the unit idle time cost of the next appointment before which a positive amount
of idle time is incurred under minimum service times $\ubar{p}$. If no idle
time is incurred for any of these appointments, then we choose
$c(i):=\max_{l\in[n]}{c_{l}}$.

Then ${\lambda}\in\Lambda_{k}$ maximizes the total cost
$\sum_{i=1}^{i^{*}}c_{i}(A_{i}-\ubar{C}_{i-1}(\pi,A,\lambda))^{+}+c_{o}\left(A_{i^{*}}+\sum_{k=i^{*}}^{n}\pi_{kj}\lambda_{j}\bar{p}_{j}-L\right)^{+}$
if $\lambda$ fulfills the following conditions. In case that $k\leq
n-i^{*}+1$, then ${\lambda}_{j}=1$ for any $j\in[n]$ implies that
$\sum_{i=i^{*}}^{n}\pi_{ij}\bar{p}_{j}$ is among the $k$ largest components of
$\left(\sum_{i=i^{*}}^{n}\pi_{ij}\bar{p}_{j}\right)_{j\in[n]}$. In case that
$k>n-i^{*}+1$, then it must hold $\sum_{j=1}^{n}\pi_{ij}\lambda_{j}=1$ for all
$i\geq i^{*}$, and if $\pi_{ij}\lambda_{j}=1$ for some $i<i^{*}$ and
$j\in[n]$, then $c(i)\ubar{p}_{j}$ is among the $k-(n-i^{*}+1)$ smallest
components of
$\left(\sum_{i=1}^{i^{*}-1}\pi_{ij}c(i)\ubar{p}_{j}\right)_{j\in[n]}$.

###### Proof 8.2

Proof of Lemma 8.1. Following the case distinction in the proof of Theorem
3.6, it is sufficient to consider the cost function
$\sum_{i=1}^{i^{*}}c_{i}(A_{i}-\ubar{C}_{i-1}(\pi,A,\lambda))^{+}+c_{o}\left(A_{i^{*}}+\sum_{i=i^{*}}^{n}\pi_{ij}\lambda_{j}\bar{p}_{j}-L\right)^{+}$
for each $i^{*}\in\\{0,\ldots,n+1\\}$ when maximizing total cost in the
general case. Thus, we show that a no-show scenario ${\lambda}\in\Lambda_{k}$
maximizes the total cost if ${\lambda}_{j}=1$ for some $j\in[n]$ implies the
following: If $k\leq n-i^{*}+1$, then $\sum_{i=i^{*}}^{n}\pi_{ij}\bar{p}_{j}$
is among the $k$ largest components of
$\left(\sum_{i=i^{*}}^{n}\pi_{ij}\bar{p}_{j}\right)_{j\in[n]}$. If
$k>n-i^{*}+1$, then it holds either $\pi_{ij}=1$ for some $i\geq i^{*}$ or
$\sum_{i=1}^{i^{*}-1}\pi_{ij}c(i)\ubar{p}_{j}$ is among the $k-(n-i^{*}+1)$
smallest components of
$\left(\sum_{i=1}^{i^{*}-1}\pi_{ij}c(i)\ubar{p}_{j}\right)_{j\in[n]}$.

To show the claim, we use the idle time reformulation from Lemma 7.4:

$\displaystyle\sum_{i=1}^{i^{*}}c_{i}(A_{i}-\ubar{C}_{i-1}(\pi,A,\lambda))^{+}+c_{o}\left(A_{i^{*}}+\sum_{k=i^{*}}^{n}\pi_{kj}\lambda_{j}\bar{p}_{j}-L\right)^{+}$
$\displaystyle=$
$\displaystyle\sum_{l=1}^{r-1}(c_{i_{l}}-c_{i_{l+1}})A_{i_{l}}+c_{i_{r}}A_{i_{r}}-c_{i_{1}}A_{i_{0}}-\sum_{l=1}^{r}{c_{i_{l}}}\sum_{{\sigma}=i_{l-1}}^{i_{l}-1}{\lambda}_{{\sigma}}\ubar{p}_{{\sigma}}+c_{o}\left(A_{i^{*}}+\sum_{k=i^{*}}^{n}\pi_{kj}\lambda_{j}\bar{p}_{j}-L\right)^{+}$

As the appointment times are independent of a worst-case no-show scenario for
the total idle time cost, the last term is maximized by the no-show scenario
described above.

$\square$

To reformulate this result as a mixed-integer linear program, we first
introduce auxiliary binary variables $\lambda,\pi(c),w$. Each of these
variables has an index $i^{*}$ for the worst-case scenario described in Lemma
8.1. Now, $\lambda_{i^{*}ij}$ takes the value 1 if and only if customer $j$ is
assigned to the $i$th appointment and shows up. The variable
$\pi(c)_{i^{*}jl}$ takes the value 1 if and only if the $j$th customer is
assigned idle time cost $c_{l}$. The variable $w_{i^{*}j_{1}j_{2}}$ takes the
value 1 if and only if both customer $j_{1}$ and $j_{2}$ are assigned to the
first $i^{*}-1$ appointments, $j_{2}$ shows up, and $j_{1}$ is a no-show.

Secondly, for any given but fixed $i^{*}\in\\{0,\ldots,n+1\\}$, we compute
each appointment $i$’s cost function $c(i)$ from Lemma 8.1 via
$c(i)=\sum_{l=1}^{n+1}\gamma_{il}c_{l}$ with $c_{n+1}:=\max_{l\in[n]}{c_{l}}$
using any feasible solution $\gamma\in\\{0,1\\}^{n\times(n+1)}$ of the
following mixed-integer linear problem.

$\displaystyle\gamma_{il}$ $\displaystyle\leq\Delta_{l}M$
$\displaystyle\forall l\in[n]\forall i\in[n+1]$ (54)
$\displaystyle\sum_{\alpha=i}^{l-1}\Delta_{\alpha}$ $\displaystyle\leq
L(1-\gamma_{il})$ $\displaystyle\forall\alpha\in[n]\forall i\in[n+1]$ (55)
$\displaystyle\sum_{l=1}^{i-1}\gamma_{il}$ $\displaystyle=0$
$\displaystyle\forall i\in[n]$ (56) $\displaystyle\sum_{l=i}^{n+1}\gamma_{il}$
$\displaystyle=1$ $\displaystyle\forall i\in[n]$ (57)

Constraints (49) ensure that, if there is no positive amount of idle time
before an appointment $l\in[n]$, then $\gamma_{il}=0$. We carefully choose
$M\geq\frac{1}{\min_{l\in[n]}\\{\Delta_{l}:\Delta_{l}>0\\}}$ to ensure
numerical stability. An alternative approach involves replacing (54) with an
indicator constraint, namely $\Delta_{l}=0\Rightarrow\gamma_{il}=0$.
Constraints (51)and (52) ensure that each appointment $i$ is assigned a unit
idle time cost $c_{l}$ with $l\geq i$. Constraints (50) ensure that, if
$\gamma_{i\alpha}=1$, then there occurs no idle time before any of the
appointments $i,...,\alpha-1$. Therefore, Constraints (49) to (52) ensure that
$\gamma_{il}=1$ holds if and only if $l\in[i,n]$ is the next appointment
before which a positive amount of idle time occurs, and $\gamma_{i,n+1}=1$ if
there is no such appointment.

##### MILP.

Hence, we have derived the following mixed-integer formulation for the general
Robust Appointment Scheduling Problem with Waiting Time Guarantees and $k$
show-ups (RASWTG):

$\displaystyle\min\,$ $\displaystyle U$ (58) s.t. $\displaystyle
U\geq\sum_{i=2}^{i^{*}}c_{i}\Delta_{i^{*}i}+c_{o}\sigma_{i^{*}}$
$\displaystyle\forall{i^{*}}\in[n+1]$ (59)
$\displaystyle\Delta_{i^{*}i}\geq{A}_{i}-\ubar{C}_{i^{*}i-1}$
$\displaystyle\forall{i^{*}},i\in[n+1]$ (60)
$\displaystyle\ubar{C}_{i^{*}i}=\max\left\\{A_{i},\ubar{C}_{i^{*}i-1}\right\\}+\sum_{j=1}^{n}\lambda_{i^{*}ij}\ubar{p}_{j}$
$\displaystyle\,\forall{i^{*}}\in[n+1]\forall i\in[n]$ (61)
$\displaystyle\sigma_{i^{*}}\geq
A_{i^{*}}+\sum_{k=i^{*}}^{n}\sum_{j=1}^{n}\lambda_{i^{*}kj}\bar{p}_{j}-L$
$\displaystyle\forall i^{*}\in[n]$ (62)
$\displaystyle\lambda_{i^{*}ij}\leq\pi_{ij}$ $\displaystyle\forall
i^{*}\in[n+1]\forall i,j\in[n]$ (63)
$\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{n}\lambda_{i^{*}ij}=k$
$\displaystyle\forall i^{*}\in[n+1]$ (64)
$\displaystyle\sum_{j=1}^{n}\lambda_{i^{*}ij}=1$
$\displaystyle\forall{i^{*}}\in[n+1-k,n+1]\forall i\in[i^{*},n]$ (65)
$\displaystyle\sum_{j=1}^{n}\lambda_{i^{*}ij}=0$
$\displaystyle\forall{i^{*}}\in[n-k]\forall i\in[i^{*},n]$ (66)
$\displaystyle\sum_{i=1}^{n}\lambda_{i^{*}ij_{2}}-\sum_{i=1}^{n}\lambda_{i^{*}ij_{1}}\leq
w_{i^{*}j_{1}j_{2}}$ $\displaystyle\forall{i^{*}}\in[n+1]\forall
j_{1},j_{2}\in[n]$ (67) $\displaystyle w_{i^{*}j_{1}j_{2}}\leq
1-\sum_{i=1}^{n}\lambda_{i^{*}ij_{1}},\sum_{i=1}^{n}\lambda_{i^{*}ij_{2}}$
$\displaystyle\forall{i^{*}}\in[n+1]\forall j_{1},j_{2}\in[n]$ (68)
$\displaystyle\sum_{l=1}^{n+1}c_{l}(\pi(c)_{i^{*}j_{2}l}\ubar{p}_{j_{2}}-\pi(c)_{i^{*}j_{1}l}\ubar{p}_{j_{1}})\leq
M(1-w_{i^{*}j_{1}j_{2}})$ $\displaystyle\forall{i^{*}}\in[n+1-k,n+1]\forall
j_{1},j_{2}\in[n]$ (69) $\displaystyle\bar{p}_{j_{2}}-\bar{p}_{j_{1}}\leq
M(1-w_{i^{*}j_{1}j_{2}})$ $\displaystyle\forall{i^{*}}\in[n-k]\forall
j_{1},j_{2}\in[n]$ (70) $\displaystyle(\ref{helo})-(\ref{21})\text{ with
additional index }i^{*}\in[n+1]$ (71)
$\displaystyle-1+\pi_{ij}+\gamma_{i^{*}il}\leq\pi(c)_{i^{*}jl}$
$\displaystyle\forall i^{*}\in[n+1]\forall j,l\in[n]$ (72) $\displaystyle
A_{l}+\sum\limits_{k=l}^{i-1}\sum_{j=1}^{n}\pi_{kj}\bar{p}_{j}-A_{i}\leq\sum_{j=1}^{n}\pi_{ij}W_{j}$
$\displaystyle\forall i,l:i\in[n],l\in[i-1],i-l\leq k-1$ (73) $\displaystyle
A_{l}+(k-1)\,\alpha_{i,l}+\sum_{\sigma=l}^{i-1}p_{il\sigma}-A_{i}\leq\sum_{j=1}^{n}\pi_{ij}W_{j}$
$\displaystyle\forall i\in[n],l\in[i-1]:i-l>k-1$ (74)
$\displaystyle\alpha_{il}+p_{il\sigma}\geq\sum_{j=1}^{n}\pi_{\sigma
j}\bar{p}_{j}$ $\displaystyle\forall i,l,\sigma\in[n]$ (75)
$\displaystyle\sum_{j=1}^{n}\pi_{ij}=1,\sum_{i=1}^{n}\pi_{ij}=1,\sum_{j=1}^{n}\pi(c)_{i^{*}jl}=1$
$\displaystyle\forall i,j,l\in[n]$ (76) $\displaystyle
A_{1}=0,\ubar{C}_{i^{*}0}=0,A_{n+1}=L$ $\displaystyle\forall{i^{*}}\in[n+1]$
(77)
$\displaystyle\Delta_{i^{*}i},\Delta_{n+1,i},\sigma_{i^{*}},\alpha_{i,l},p_{il\sigma}\geq
0$ $\displaystyle\forall{i^{*}}\in[n+1]\forall i,l,\sigma\in[n]$ (78)
$\displaystyle\lambda_{i^{*}ij},\pi(c)_{i^{*}jl},\gamma_{il}^{(i^{*})},w_{i^{*}j_{1}j_{2}}\in\\{0,1\\}$
$\displaystyle\forall{i^{*}}\in[n+1]\forall i,j,j_{1},j_{2},l\in[n]$ (79)
$\displaystyle A_{i}\geq 0,\pi_{ij}\in\\{0,1\\}$ $\displaystyle\forall
i,j\in[n]$ (80)

The Objective Function (53) minimizes the upper bound on the total cost, which
is computed in Constraints (54) – (66). Specifically, Constraint (54) sets the
upper bound for cost incurred from idle time $\Delta_{i^{*}i}$ and overtime
$\sigma_{i^{*}}$ in each worst-case scenario corresponding to $i^{*}\in[n+1]$
(see Lemma 8.1). Constraint (55) – (56) define the worst-case idle time before
the $i^{*}$th appointment as a function of $\lambda$. Similarly, Constraint
(57) defines the worst-case overtime accumulated starting from the $i^{*}$th
appointment. Constraint (59) ensures that a total of $k$ customers show up.
The following constraints implement the results from Theorem 3.6. Constraints
(60) ensure that if $k\geq n-i^{*}+1$, then all customers schedules for the
$k-(n-i^{*}+1)$ last appointments show up. Constraint (61) allows customers to
show up for the first $i^{*}-1$ appointments only if $k>n-i^{*}+1$.
Constraints (62) – (65) determine that among the first $i^{*}$ appointments,
only those with the smallest product $c_{l}\ubar{p}_{j}$ show up, and among
the subsequent appointments those with the longest maximum service times.
Finally, Constraints (67) – (69) ensure the waiting time guarantees as derived
in (53).

##  9 Optimal Interappointment Times

The finding of the optimal ASAP scheduling rule in Theorem 4.2 under non-
increasing idle time costs provides valuable insights, enhancing our
understanding of the depicted optimal interappointment times in Figure 1:

In the case of zero no-shows, the ASAP rule implies increasing or varying
interappointment times at the beginning of the scheduling horizon to avoid
early idle times, followed by a constant pattern (limited by the waiting time
guarantees). In this sense, the semi-plateau-dome pattern is a customer-driven
variant of the plateau-dome-shaped pattern for zero-no shows.

Moving on to the case that only $k<n$ patients show up, no-shows do not affect
the worst-case completion times of the first $k$ appointments, but they affect
the worst-case completion times of later appointments. In particular, some
later interappointment times can be shortened in favor of lower cost. Due to
the adherence to the waiting time guarantees, the interappointment times rise
again to their previous level afterward. This observation leads to spikes
typically after $k$ customers. We consider this structure a customer-driven
variant of the plateau-dome-shaped pattern with no-shows.

##  10 Computational Study Details

###  10.1 Instances

Figure 5: Service Times by Examination Type (Number of Observations in
Parentheses)$0$$20$$40$$60$$80$$100$$120$$140$$160$$180$Thorax (2.197)Throat
(832)Abdomen (476)Whole body (168)Pancreas (155)Brain skull (123)Knee
(114)Service time (in minutes)

The chosen patient numbers, $n\in\\{5,10,20\\}$, are aligned with our daily CT
examination records and are consistent with previous computational studies
utilizing distributionally robust optimization approaches (Qi 2017, Jiang et
al. 2017, Kong et al. 2020). To capture the variability in real-world
scenarios, and following consultation with radiology management, we introduce
variations in no-show rates across 0%, 10%, and 20%, achieved by setting
$k\in\\{n,\lfloor 0.9n\rfloor,\lfloor 0.8n\rfloor\\}$. Figure 5 presents a
boxplot illustrating the service times for the most common examination types.

###  10.2 Sensitivity Analysis: The Number of Customers

As can be seen in Table 4, the RASWTG approach leads to shorter waiting times
and longer idle times as the number of scheduled customers increases.
Specifically, the ASAP scheduling rule from Theorem 4.2, which is optimal for
constant and decreasing costs, provides a rationale for this trend:

The first few appointments can all be scheduled at the start time of the
scheduling horizon, as long as the sum of their maximum service times does not
exceed the waiting time guarantee of the subsequent appointment. For these
appointments, waiting times accumulate in proportion to the service times
realized. For all subsequent appointments, the start time can be calculated as
the worst-case sum of the previous service times minus the waiting time
guarantee. As the number of customers treated increases, we consider it
increasingly unlikely that all customers require their maximum service time.
Consequently, we expect short waiting times and longer idle times before late
appointments.

We note that this trend could be mitigated by using uncertainty budgets that
control the number of customers who require maximum service time.

###  10.3 Utilitarian Approach

Figure 6: Optimal Interappointment Times (in Minutes)

(a) WSRAS with
$c_{w}=0.00001$$A_{2}-A_{1}$$A_{3}-A_{2}$$A_{4}-A_{3}$$A_{5}-A_{4}$$A_{6}-A_{5}$$A_{7}-A_{6}$$A_{8}-A_{7}$$A_{9}-A_{8}$$A_{1}0-A_{9}$$0$$10$$20$$30$$40$$50$$60$$70$

(b) WSRAS with
$c_{w}=0.1$$A_{2}-A_{1}$$A_{3}-A_{2}$$A_{4}-A_{3}$$A_{5}-A_{4}$$A_{6}-A_{5}$$A_{7}-A_{6}$$A_{8}-A_{7}$$A_{9}-A_{8}$$A_{1}0-A_{9}$$0$$10$$20$$30$$40$$50$$60$$70$

(c) WSRAS with
$c_{w}=1$$A_{2}-A_{1}$$A_{3}-A_{2}$$A_{4}-A_{3}$$A_{5}-A_{4}$$A_{6}-A_{5}$$A_{7}-A_{6}$$A_{8}-A_{7}$$A_{9}-A_{8}$$A_{1}0-A_{9}$$0$$10$$20$$30$$40$$50$$60$$70$

WSRASRASWTG

We briefly explore optimal interappointment times to enhance our understanding
of optimal WSRAS schedules, as illustrated in Figure 6. We again compute the
interappointment times for ten identical customers with a minimum service time
of 15 minutes, a maximum service time of 25 minutes, and a waiting time
guarantee of 30 minutes. In contrast to RASWTG, WSRAS interappointment times
start at a higher level. Then, depending on the waiting time weight, they
gradually decrease until a certain point. For small waiting time weights, most
interappointment times match the minimum service time of 15 minutes, leading
to little idle time but exploding waiting times. Conversely, higher waiting
time weights yield interappointment times closer to the maximum service time
of 25 minutes, resulting in short waiting times but extended idle time.
Intriguingly, when $c_{w}=0.1$, WSRAS accumulates waiting times until, at a
certain point, they are alleviated by a single long interappointment time.

Finally, we note that the WSRAS problem with constant idle time costs closely
resembles problem (1) in Schulz and Udwani (2019), except that the latter does
not consider a fixed planning horizon $L$. While initially minimizing a
weighted sum of idle times and waiting time costs under a collective worst-
case scenario, Schulz and Udwani (2019) demonstrate the sufficiency of
considering the same $n+1$ scenarios as in WSRAS.

Moreover, comparing an RASWTG-optimal schedule that does not consider a fixed
planning horizon (e.g., $c_{n+1}=c_{o}=0$) to a schedule computed with the
optimal scheduling rule in Schulz and Udwani (2019) and under the respective
assumptions, we find that RASWTG improves capacity utilization for
sufficiently long waiting time guarantees. In particular, it is easy to show
that the RASWTG schedule reduces worst-case idle time costs in the case of
$W>\sum_{i=1}^{n-1}\sum_{j=1}^{n}\pi_{ij}\frac{u}{u+o_{\geq
i}}\left(\bar{p}_{j}-\ubar{p}_{j}\right)$.