Advance Multi-Priority,Multi-Appointment Patient Scheduling With Dependent Demand and Lead Times

Abstract

This study examines a patient scheduling problem with multiple appointment types and priority levels, where certain appointments must precede others and lead times play a crucial role. Although both factors significantly influence the quality of care—particularly when specialist assessments depend on timely diagnostic tests—they have been largely overlooked in existing healthcare scheduling models. To address this gap, we propose a dynamic scheduling model that explicitly incorporates appointment dependencies, lead times, and patient heterogeneity across multiple priority levels. The model reflects the real-world complexities of coordinating diagnostic and consult appointments in time-sensitive clinical settings. Using Approximate Dynamic Programming techniques, we develop an Approximate Optimal Policy (AOP) that efficiently allocates clinical resources, minimizes patient wait times, and ensures the availability of test results prior to consult appointments. We further derive a closed-form solution for the optimal approximation parameters, supported by a mathematical proof, which offers significant computational advantages. We evaluate the performance of the proposed AOP through simulation and compare it against a set of benchmark policies, including heuristics adapted from existing scheduling logic and current clinical practice. The solution is applied to a case study created based on data from a Stroke Prevention Clinic (SPC), where the complexity of care protocols and high demand present substantial scheduling challenges. The results demonstrate that the AOP consistently outperforms all benchmarks in terms of reducing wait times, ensuring timely diagnostic completion before consults, and meeting wait-time targets. We also introduce a practical, easy-to-implement heuristic called (MSP), which is derived from the AOP and designed for operational use. While simpler in structure, MSP performs comparably well and is well-suited for adoption in real healthcare settings due to its interpretability and minimal computational requirements. Finally, although the proposed approach is demonstrated in the context of an SPC, it has broader applicability to other areas such as cancer care, kidney transplant scheduling, and other complex care pathways involving interdependent appointments and prioritization.

1. Introduction

Patient scheduling is one of the most important challenges in healthcare operations. It has been studied in numerous contexts, including outpatient clinics and treatment centers (Cayirli and Veral, 2003; Patrick et al., 2008; Samorani and LaGanga, 2015; Sauré et al., 2015), cancer treatment centers (Gocgun and Puterman, 2014; Sauré et al., 2012; Wenzel et al., 2023), surgical units (Meskens et al., 2013; Sauré et al., 2020), rehabilitation centers (Bikker et al., 2020), and home care (Khorasanian et al., 2024). Since most health centers do not have excess capacity, scheduling policies can have a dramatic impact on patients’ timely access to care.

Patient scheduling problems are typically categorized into two types (Magerlein and Martin, 1978). The first type, called advance or interday scheduling, assigns patients to different days in the booking horizon (Zacharias et al., 2024). The second type, called appointment or intraday scheduling, narrows the focus to the day of service and assigns an exact time of day to each patient (Zacharias et al., 2024). This paper focuses on advanced scheduling decisions.

The complexity of advanced scheduling decisions is exacerbated by the scarcity of resources, the heterogeneity of patient requirements, and the inherent uncertainty in patient demand. Booking agents are often tasked with managing multiple resources and appointment requests coming from multiple types of patients (Babashov et al., 2023; Jiang et al., 2020; Sauré et al., 2020). Patients are typically differentiated by their level of urgency and clinical requirements. Compounding the difficulty of patient scheduling are potential interdependencies between treatment stages, and potential lead times, making evident the need for advanced solution approaches that take into account these precedence relationships between types of appointments in order to better estimate the immediate and future impact of scheduling decisions and thus help provide timely access to quality patient care.

In many healthcare settings, patients must undergo diagnostic tests before a physician consultation, but test results are not immediately available. This situation arises in areas such as oncology, stroke prevention, and transplant assessments. Booking agents must schedule both testing and consultation appointments while accounting for capacity and patient priority levels, each tied to a maximum recommended wait time. The precedence of tests, together with the time required for individual test results to become available—hereafter referred to as “lead time”—often leads to consultations occurring without complete diagnostic information, potentially compromising care quality. Ensuring test results are ready before the consultation is therefore essential.

To address this challenge, we model the advanced multi-priority, multi-appointment patient scheduling problem—with dependent demand and lead time—as a discounted infinite-horizon Markov decision process (MDP). This is the first study, to our knowledge, to apply such a model to interdependent appointments with the goal of maximizing diagnostic information availability at the time of consultation. Given the problem’s complexity and large state-action space, we adopt an affine value function approximation, formulate an equivalent linear program, and solve its dual via column generation. For a small instance, we derive a closed-form solution for the optimal approximation parameters, enabling efficient solution of a real, large-scale case based on data from a regional Stroke Prevention Clinic (SPC). Finally, we propose a simple, computationally light heuristic, “MSP,” which effectively replicates the behavior of the Approximate Optimal Policy (AOP).

Through simulation, we compare the performance of the AOP and MSP policies with that of the current practice and existing heuristic approaches adapted specifically for this problem and demonstrate a significant improvement with respect to all performance criteria. The latter includes modified versions of the day with the minimum number of bookings (DMB) policy (Sauré et al., 2015), the Patrick–Puterman–Queyranne (PPQ) policy (Patrick et al., 2008), and a hybrid policy combining both. To the best of our knowledge, this is the first paper to consider the precedence relationship between different types of appointments, and their lead times, and provide a closed-form solution as well as an easy-to-use scheduling policy in the context of multi-appointment, multi-priority advance patient scheduling.

The remainder of the paper is organized as follows. Section 2 provides a comprehensive review of the relevant literature and outlines our contributions. Section 3 introduces the particular patient scheduling problem to be solved and provides a mathematical formulation of the problem. Section 4 presents the description of the proposed solution approach. In Section 5, we present the numerical results for a small instance of the problem, provide a closed-form solution for the optimal value of the approximation parameters, characterize the resulting appointment scheduling policy, and provide a sensitivity analysis. We also present a real case study to evaluate the performance of the proposed policies compared with a number of benchmark policies. Finally, Section 6 provides a discussion of the limitations of this study, managerial insights taken from this research, and future research avenues.

2. Literature Review

Patient scheduling is essential for timely access to care, effective use of critical resources (Ala et al., 2023), and improved patient satisfaction and health outcomes (Woodcock, 2022). To be effective, scheduling policies must account for the dynamic nature of patient arrivals, appointment precedence relationships, lead times, and multiple sources of uncertainty. As expanding capacity is often not feasible, the primary goal becomes maximizing the efficiency of existing resources to improve care accessibility.

As mentioned earlier, patient scheduling has been categorized into two broad categories: advance and allocation/appointment scheduling (Gocgun and Ghate, 2012; Magerlein and Martin, 1978). While there are many papers in each group individually (readers are referred to Dexter et al. (1999), Gupta and Denton (2008), and Marynissen and Demeulemeester (2019) for comprehensive literature reviews on the use of optimization approaches to address scheduling problems), addressing both problems simultaneously is very difficult and computationally challenging (Zacharias et al., 2024). Mathematical programming, in the form of mixed integer programming has been broadly used to find an optimal sequence of patients within a given day with the goal of minimizing the direct wait time for patients as well as idle time and overtime (Ala et al., 2021; Bastos et al., 2019; Ghandehari and Kianfar, 2022; Issabakhsh et al., 2021; Lyon et al., 2023; Moradi et al., 2022). The uncertainties related to no-shows, cancellations, patients’ unpunctuality, stochastic service times, patients’ re-entry to the system, etc., have all been addressed in different ways (Zhou et al., 2022). Simulation has also been found useful in simulating patient flow, sequencing slots, and incorporating optimization to achieve the same goals (Rezaeiahari and Khasawneh, 2020). Elalouf and Wachtel (2015) and Xiao and Yoogalingam (2022), for example, propose alternative sequencing methods to improve patient flow using simulation-based approaches. Advance appointment scheduling, on the other hand, aims to minimize the indirect wait time (or appointment delay) for patients (see Gupta and Denton 2008). Indirect waiting time is a major problem for a healthcare system as it can cause deterioration of a patient’s condition if their waiting time is excessive (Babashov et al., 2023).

We formulate the advanced patient scheduling problem as a discounted infinite-horizon MDP, a suitable framework for sequential decision-making under uncertainty (Alagoz et al., 2010). The proposed approach accounts for multiple patient types, priority levels, resource requirements, and appointment uncertainties while considering precedence relationships and lead times. By capturing system dynamics, MDPs help optimize priority-specific service levels and improve patient care and resource utilization in complex healthcare settings.

One of the inherent challenges in solving MDP models is the exponential growth of the state space and action sets that makes models for realistically sized problem settings intractable. This phenomenon is referred to as the “curse of dimensionality” (Bellman, 1957; Rust, 1997). Fortunately, there exists a suite of methods, called Approximate Dynamic Programming (ADP), designed to provide approximately optimal solutions to intractable MDPs (Powell, 2007). Most of these methods rely on choosing the right approximation architecture for the value function in the MDP formulation. Geramifard et al. (2013) provide a comprehensive review of different forms of approximation architectures for value functions. Studies such as Gocgun and Puterman (2014), Marquinez et al. (2021), Patrick et al. (2008), Sauré et al. (2012), and Wenzel et al. (2023) use an affine approximation in the predecision state variables, while there exists studies such as Sauré et al. (2015) that use a nonlinear approximation in the post-decision state variables. While nonlinear approximation architectures may offer improved fit for more complex value functions, their utilization comes with certain drawbacks. These methods often lack intuitive interpretability and introduce additional computational challenges. Further, simulation is usually the common approach used to find approximation parameters, which is usually very time-consuming and heavily dependent on the basis functions.

From a methodological point of view, the present paper builds upon the solution approach originally developed by Patrick et al. (2008) and then extended by Sauré et al. (2012). Patrick et al. (2008) was one of the first papers to model the scheduling of single appointments for multi-priority patients with priority-specific wait time targets using an MDP. Considering the heterogeneous nature of patient classes, attributable to their varying clinical requirements and different treatment steps, (Sauré et al., 2012) extended the modeling and solution approach to the multi-appointment setting. The appointment scheduling policy proposed by Patrick et al. (2008), named PPQ after the authors’ last names, was developed for a single clinical resource and without considering different types of appointments and their potential interdependencies. Unlike Patrick et al. (2008), we consider a problem setting that involves a sequence of interdependent appointments that are associated with lead times. We identify an approximate optimal scheduling policy capable of incorporating these complexities.

The literature on advanced scheduling in the presence of independent and dependent appointment requests is notably sparse. The closest study in the literature is the paper by Diamant et al. (2018). The authors propose an MDP model and a solution approach for a multi-stage outpatient setting in which patients undergo several assessments before surgery. Similar to Patrick et al. (2008), they employ an affine approximation architecture in the predecision state variables but solve the resulting model through variable aggregation. Patient types are defined solely based on treatment progress rather than clinical requirements, and without taking into account multiple priority levels. A key distinction between the present paper and Diamant et al. (2018) is that our study considers a more complex precedence relationship between different types of appointments that involves lead times. From a practical standpoint, we provide an intuitive characterization of the approximate optimal policy that makes it easy to use by practitioners. From a theoretical point of view, we offer a closed-form solution for the optimal values of the approximation parameters that determine the approximate optimal policy, facilitating its determination for problems of any size. To the best of our knowledge, this paper is the first in the literature that offers an array of good policies based on the literature and develops approximately optimal policies and easy-to-use heuristics for a scheduling problem that consists of a dependent series of appointments with lead times and shared testing and consultation capacity with a heterogeneous pool of patients based on priority and clinical needs (patient types).

In summary, the key contributions of this paper to the patient scheduling literature are fourfold. First, we formulate a multi-appointment, multi-priority patient scheduling model that incorporates appointment dependencies and lead times for patients with varying medical needs. Second, we designed a scheduling approach for consultation appointments that ensures physicians have access to all required test results at the time of seeing their patients. Third, through the characterization of the approximate optimal decision policy, we propose an easy-to-use scheduling heuristic, along with a suite of adapted policies inspired by the existing literature. Fourth, we provide a closed-form solution for the approximation parameters, supported by a rigorous mathematical proof.

3. Problem and Formulation

Consider a clinic that classifies patients into $I$ priority classes and $J$ patient types based on the exams they require prior to physician consultation. Each priority class is associated with a maximum recommended wait time for a consult appointment. We represent the wait time target (in days) for priority class $i$ by $T_i$ . A patient of type $j$ requires a subset $M{C}_j$ of tests whose results must be available prior to the consult date, and where $L{T}_m$ denotes the number of days required (i.e., lead time) until the result of test $m$ becomes available. Daily demand for priority $i$ patients of type $j$ follows a discrete probability distribution with mean ${\lambda }_{ij}$ requests per day. The demand distribution is independent for each priority–type combination and does not change over time. The clinic divides its testing and consultation capacity into discrete capacity units called appointment slots. While all patient types share the same examination resources, personalized consultation capacity is allocated to each type. The number of appointment slots booked for resource $m$ on any given day and considering all patient types cannot exceed $C_m^R+C_m^O$ units, where $C_m^R$ and $C_m^O$ are fixed and correspond to the daily regular-hour and overtime capacities associated with resource $m$ , respectively. The daily number of consult appointments allocated to patients of type $j$ cannot exceed $C_{cj}^R+C_{cj}^O$ units. The parameters $C_{cj}^R$ and $C_{cj}^O$ are also fixed and correspond to the daily regular-hour and overtime consultation capacities, respectively. The process explained above is illustrated in Figure 1.

Figure 1.

A diagram illustrating the multi-appointment, multi-priority setting.

We assume that testing and consultation capacities are measured in fixed-length, discrete units called “appointment slots” and that each patient requires a single appointment slot. While uncertainty in service durations is a key factor in allocation and appointment (i.e., intraday) scheduling, it is less relevant in advance scheduling, which is the focus of our study. Advance scheduling methods usually assume that a second level of scheduling is needed, which assigns patients to specific appointment times. Furthermore, service time variability in settings such as SPCs is very low for both testing and consultation appointments. Sauré et al. (2020) demonstrated that the approximate optimal policies derived using deterministic service times remain highly effective for multi-priority, multi-class advance scheduling settings with stochastic service times. Their numerical analysis showed that incorporating stochastic service times into advance scheduling models yields only marginal benefits in settings where idle time and wait times through the day are not that important, with an expected reduction in the total discounted cost of $<4\mathrm{\%}$ , even under significant service time variability.

Once all the booking requests for a given day are known, the booking agent observes the number of appointment slots booked from today to the end of the booking horizon for each clinical resource and determines how to allocate available examination and consultation capacity to the patients on the wait list. The agent has three primary courses of action: to schedule appointments during regular hours, to schedule using overtime, or to defer the decisions for some patients to the next day. Scheduling decisions are made on a daily basis, and bookings can be made at most $N$ days in advance. The main goal is to ensure patients see a physician within their maximum recommended wait times while making sure that all test results are available prior to consultation.

3.1. Mathematical Formulation

We formulate this problem as a discounted infinite-horizon MDP model with a rolling $N$ -day booking horizon. Table 1 provides the notation used to formulate the problem.

Table 1.

Notations for modeling the problem as a discounted infinite-horizon Markov decision process (MDP).

Sets and indices
Set	Index
$M$ : Resources (testing and consultation)	$m$ : A resource, $m\in M$
$M_T$ : Testing resources, $M_T=M\setminus \{c\}$	$n,t$ : A day in the booking horizon
$I$ : Priority levels	$i$ : A priority level, $i\in I$
$J$ : Patient types	$j$ : A patient type, $j\in J$
$M{C}_j$ : Set of tests required by patients of type $j$
Parameters
$N$	Number of days in the booking horizon (days)
$u_{mj}$	1 if an appointment with resource $m$ is needed for patients of type $j$ , 0 otherwise
$T_i$	Maximum recommended wait time for priority $i$ patients (days)
$U_j$	Total number of appointments needed for patients of type $j$
$C_m^R$	Number of regular-hour appointment slots for resource $m\in M_T$ (slots/day)
$C_{cj}^R$	Number of regular-hour appointment slots for consults of type $j$ (slots/day)
$C_m^O$	Number of overtime appointment slots for resource $m\in M_T$ (slots/day)
$C_{cj}^O$	Number of overtime appointment slots for consults of type $j$ (slots/day)
${\lambda }_{ij}$	Arrival rate of requests from priority $i$ patients of type $j$ (requests/day)
$b_i^n$	Cost of booking the consult appointment of a priority $i$ patient on day $n$ (from now) ($)
$g_i$	Penalty for postponing the booking of a priority $i$ patient until the next day ($/patient)
$d_m$	Unit overtime cost associated with resource $m$ ($/slot)
$\gamma$	Discount factor
State variables
$x_m^n$	Number of patients scheduled on day $n$ (from now) for resource $m\in M_T$
$x_{cj}^n$	Number of type $j$ patients scheduled on day $n$ (from now) for consultation
$o_m^n$	Number of overtime bookings on day $n$ (from now) for resource $m\in M_T$
$o_{cj}^n$	Number of overtime bookings on day $n$ (from now) for consultation of type $j$
$d_{ij}$	Number of priority $i$ patients of type $j$ waiting to be scheduled
Decision variables
$a_{mij}^n$	Number of priority $i$ patients of type $j$ to schedule on day $n$ for resource $m\in M_T$
$a_{cij}^n$	Number of priority $i$ patients of type $j$ to schedule on day $n$ for consultation
$z_m^n$	Number of overtime appointments slots required on day $n$ for resource $m\in M_T$
$z_{cj}^n$	Number of overtime appointments slots required on day $n$ for consultation of type $j$
Random variables
$D_{ij}^{\mathrm{\prime }}$ : Number of new appointment requests from priority $i$ patients of type $j$

3.2. Decision Epochs

Decisions are made at the end of each day over an infinite planning horizon.

3.3. State Space

The state can be represented as a vector $\overrightarrow{s}=(\overrightarrow{x},\overrightarrow{o},\overrightarrow{d})$ , where $\overrightarrow{x}$ consists of, $x_m^n$ , the number of patients scheduled on day $n$ for examination resource $m$ , and $x_{cj}^n$ , which is the number of type $j$ patients scheduled on day $n$ for consultation resource $c$ . Similarly, $\overrightarrow{o}$ consists of $o_m^n$ , which represents the number of patients scheduled in overtime of day $n$ (from now) for consultation resource $m$ , and $o_{cj}^n$ , which corresponds to the number of type $j$ patients scheduled on overtime on day $n$ for consultation resource $c$ . Finally, $\overrightarrow{d}$ consists of $d_{ij}$ , which is the number of priority $i$ patients of type $j$ waiting to be scheduled. Because of the rolling horizon approach, at the beginning of each decision epoch $x_m^N$ , $x_{cj}^N$ , $o_m^N$ , and $o_{cj}^N$ are equal to zero.

3.4. Action Sets

Any action available to the booking agent can be written as a vector $\overrightarrow{a}=(\overrightarrow{a},\overrightarrow{z})$ , where $a_{mij}^n$ represents the number of priority $i$ patients of type $j$ to schedule on day $n$ for resource $m$ and $\overrightarrow{z}$ consists of $z_m^n$ , the number of overtime appointments slots required on day $n$ for examination resource $m$ , and $z_{cj}^n$ , which corresponds to the number of overtime appointment slots of type $j$ required on day $n$ for consultation resource $c$ . Unlike Patrick et al. (2008), who consider overtime booking as an independent action component, we regard overtime booking as an auxiliary dependent decision variable that only takes positive values when the total number of bookings on a given day exceeds the regular-hour capacity. Taking this approach grants us a significant computational advantage as overtime usage is captured by a lower-dimensional variable $z_m^n$ , which leads to shorter execution times and a less complex mathematical formulation.

To determine the feasible action space compatible with each state $\overrightarrow{s}=(\overrightarrow{x},\overrightarrow{o},\overrightarrow{d})$ , denoted by $A_{\overrightarrow{s}}$ , we define the following constraints:

$$\begin{array}{rl}& \sum _n{a}_{mij}^n\le d_{ij}{u}_{mj},\mathrm{\forall }i,j,m,\end{array}$$

(1)

$$\begin{array}{rl}& \frac{1}{U_j}\sum _n\sum _m{a}_{mij}^n=\sum _n{a}_{m^{\prime }ij}^n,\mathrm{\forall }i,j,m^{\prime }\in M{C}_j\cup c,\end{array}$$

(2)

$$\begin{array}{rl}& x_m^n+\sum _i\sum _j{a}_{mij}^n\le C_m^R+z_m^n,\mathrm{\forall }n,m\in M_T,\end{array}$$

(3)

$$\begin{array}{rl}& z_m^n+o_m^n\le C_m^O,\mathrm{\forall }n,m\in M_T,\end{array}$$

(4)

$$\begin{array}{rl}& x_{cj}^n+\sum _i{a}_{cij}^n\le C_{cj}^R+z_{cj}^n,\mathrm{\forall }n,j,\end{array}$$

(5)

$$\begin{array}{rl}& z_{cj}^n+o_{cj}^n\le C_{cj}^O,\mathrm{\forall }n,j,\end{array}$$

(6)

$$\begin{array}{rl}& \sum _{t=1}^n{a}_{cij}^t\le \sum _{t=1}^{n-L{T}_m}{a}_{mij}^t,L{T}_m+1\le n\le N,\mathrm{\forall }m\in M{C}_j,i,j,\end{array}$$

(7)

$$\begin{array}{rl}& \sum _{t=1}^{L{T}_m}{a}_{cij}^t=0,\mathrm{\forall }m\in M{C}_j,i,j.\end{array}$$

(8)

Constraint (1) ensures that the total number of bookings for each resource does not exceed the number on the waiting list. Constraint (2) makes sure that if a patient is booked, then all the required appointments, including the required tests and consultation, are booked. Here $U_j=\sum _{m\in M{C}_j\cup c}{u}_{mj}$ represents the total number of appointments, required exams, and consults, needed for a patient of type $j$ . Constraints (3) and (5) restrict the total number of appointments booked on day $n$ to be less than or equal to the available testing and consult capacity, respectively. Any booking beyond regular-hour capacity is considered overtime, captured through the auxiliary variables $z_{nm}$ and $z_{ncj}$ for tests and consult, respectively. Constraints (4) and (6) limit the total overtime utilization on day $n$ (from today) to be less than or equal to the overtime capacity. Constraint (7) states the precedence relationship between test and consult appointments. It ensures that the results of the required tests are available prior to a consultation visit. Finally, constraint (8) makes sure no consult appointment is scheduled before the minimum lead times for the required tests.

3.5. Transitions

Given a rolling booking horizon, the number of regular-hour and overtime bookings on day $n$ is determined by the number of previous bookings on day $n+1$ plus all the new appointments booked on day $n+1$ . Consequently, the $N^{\mathrm{th}}$ day in the booking horizon has no appointments in it. Thus, the capacity utilization components of the state of the system the next day, denoted by $\overrightarrow{\tilde{x}}$ and $\overrightarrow{\tilde{o}}$ , are computed as follows:

$$\begin{array}{rl}& {\tilde{x}}_m^n=x_m^{n+1}+\sum _i\sum _j{a}_{mij}^{n+1}-z_m^{n+1},\mathrm{\forall }m\in M_T,1\le n\le N-1,\end{array}$$

(9)

$$\begin{array}{rl}& {\tilde{x}}_m^N=0,\mathrm{\forall }m\in M_T,\end{array}$$

(10)

$$\begin{array}{rl}& {\tilde{x}}_{cj}^n=x_{cj}^{n+1}+\sum _i{a}_{cij}^{n+1}-z_{cj}^{n+1},\mathrm{\forall }j,1\le n\le N-1,\end{array}$$

(11)

$$\begin{array}{rl}& {\tilde{x}}_{cj}^N=0,\mathrm{\forall }j,\end{array}$$

(12)

$$\begin{array}{rl}& {\tilde{o}}_m^n=o_m^{n+1}+z_m^{n+1},\mathrm{\forall }m\in M_T,1\le n\le N-1,\end{array}$$

(13)

$$\begin{array}{rl}& {\tilde{o}}_m^N=0,\mathrm{\forall }m\in M_T,\end{array}$$

(14)

$$\begin{array}{rl}& {\tilde{o}}_{cj}^n=o_{cj}^{n+1}+z_{cj}^{n+1},\mathrm{\forall }j,1\le n\le N-1,\end{array}$$

(15)

$$\begin{array}{rl}& {\tilde{o}}_{cj}^N=0,\mathrm{\forall }j.\end{array}$$

(16)

The number of new appointment requests of each type and priority is the only source of uncertainty. Given $D_{ij}^{\prime }$ new requests of priority $i$ patients of type $j$ , equation (17) determines the new requests waiting to be booked, denoted by ${\tilde{d}}_{ij}$ , as the number of requests that have not yet been booked plus the new requests. The difference between the first two terms of the right-hand side of (17) defines the number of patients whose booking decisions are postponed to the next day:

$${\tilde{d}}_{ij}=d_{ij}-\frac{1}{U_j}\sum _m\sum _n{a}_{mij}^n+D_{ij}^{\prime }\mathrm{\forall }i,j.$$

(17)

Therefore, as a result of taking action $\overrightarrow{a}=(\overrightarrow{a},\overrightarrow{z})$ in state $\overrightarrow{s}=(\overrightarrow{x},\overrightarrow{o},\overrightarrow{d})$ , $\overrightarrow{a}\in A_{\overrightarrow{s}}$ and $\overrightarrow{s}\in S$ , the state of the system the next day, $\overrightarrow{s^{\prime }}\in S$ , will be determined by the following probability distribution:

$$\begin{array}{rl}& P(\overrightarrow{s^{\prime }}|\overrightarrow{s},\overrightarrow{a})=\\ & \{\begin{array}{ll}P(\overrightarrow{D^{\prime }})=\prod _{i,j}P(D_{ij}^{\prime })& \text{if }\overrightarrow{s}\text{ satisfies equations}(9)\text{to}(16),\\ 0& \text{otherwise},\end{array}\end{array}$$

(18)

where $P(D_{ij}^{\prime })$ is the probability of having $D_{ij}^{\prime }$ new appointment requests from priority $i$ patients of type $j$ . We assume that the probability distribution is independent for each priority–type combination and does not change over time.

3.6. Immediate Costs

The total immediate cost $c(\overrightarrow{s},\overrightarrow{a})$ associated with taking action $\overrightarrow{a}=(\overrightarrow{a},\overrightarrow{z})$ in state $\overrightarrow{s}=(\overrightarrow{x},\overrightarrow{o},\overrightarrow{d})$ , comes from three sources: the penalties associated with booking consult appointments beyond their priority-specific maximum recommended wait times; the cost associated with the use of overtime to deliver test and consult appointments; and the penalties associated with postponing any booking decisions. Thus, $c(\overrightarrow{s},\overrightarrow{a})$ is equal to:

$$\begin{array}{rl}\sum _n\sum _i\sum _j{b}_i^n{a}_{cij}^n& +(\sum _n\sum _{m\in M_T}{d}_m{z}_m^n+\sum _n\sum _j{d}_c{z}_{cj}^n)\\ & +\sum _i\sum _j{g}_i(d_{ij}-\frac{1}{U_j}\sum _n\sum _m{a}_{mij}^n),\end{array}$$

(19)

where $b_i^n$ represents the penalty for booking a consult of priority $i$ on day $n$ , $d_m$ corresponds to the cost associated with an overtime booking scheduled for resource $m$ , and $g_i$ is the penalty associated with postponing the booking decision for a priority $i$ patient.

The $b_i^n$ penalties, those incurred when the wait time for physician consultation goes beyond the patient-specific target, are assumed to have the following form:

$$\begin{array}{r}{b}_i^n=\{\begin{array}{ll}{\displaystyle \sum _{k=1}^{n-T_i}{\gamma }^{k-1}{g}_i,}& \text{for all }n>T_i,\\ 0& \text{otherwise}.\end{array}\end{array}$$

(20)

where $\gamma$ is the discount factor. In this way, the penalty for postponing a consult booking $k$ days and then booking it within the priority-specific wait time target is equal to the penalty for booking the consult $k$ days past the wait time target initially.

3.7. Optimality Equations

In our model, the value function $V:S\to \mathbb{R}$ captures the minimum expected discounted cost over an infinite planning horizon and satisfies Bellman’s optimality equation. Therefore, to determine an optimal stationary booking policy, we must solve the following system of equations:

$$\begin{array}{r}V(\overrightarrow{s})=\underset{\overrightarrow{a}\in A_{\overrightarrow{s}}}{min}\{c(\overrightarrow{s},\overrightarrow{a})+\gamma \sum _{\overrightarrow{s^{\prime }}\in S}P(\overrightarrow{s^{\prime }}|\overrightarrow{s},\overrightarrow{a})V(\overrightarrow{s^{\prime }})\},\mathrm{\forall }\overrightarrow{s}\in S.\end{array}$$

(21)

The major challenge with solving this system of equations is the exponential increase in the size of the state space and action sets with the size of the problem. To tackle this challenge, we present a solution methodology based on linear programming.

4. Solution Methodology

In this section, we first rewrite the MDP model in its equivalent linear programming form. We then use an affine value function approximation in the state variables to formulate an approximate linear program. Lastly, we solve the dual of the latter through column generation to obtain an approximately optimal policy for the original MDP.

4.1. Linear Programming (LP) Model

For any strictly positive value of $\overrightarrow{\alpha }$ , the solution to the optimality equations in (21) is the same as the solution to the following LP model (Puterman, 1994):

$$\begin{array}{rl}& \underset{\overrightarrow{V}}{max}\{\sum _{\overrightarrow{s}\in S}\alpha (\overrightarrow{s})V(\overrightarrow{s}):c(\overrightarrow{s},\overrightarrow{a})\\ & +\gamma \sum _{\overrightarrow{s^{\prime }}\in S}P(\overrightarrow{s^{\prime }}|\overrightarrow{s},\overrightarrow{a})V(\overrightarrow{s^{\prime }})\ge V(\overrightarrow{s})\mathrm{\forall }\overrightarrow{s}\in S,\overrightarrow{a}\in A_{\overrightarrow{s}}\},\end{array}$$

(22)

where $\alpha (\overrightarrow{s})>0$ is the weight given to state $\overrightarrow{s}\in S$ in the objective function. We will assume $\sum _{\overrightarrow{s}\in S}\alpha (\overrightarrow{s})=1$ and consider $\overrightarrow{\alpha }$ as a probability distribution over the initial state of the system.

For any reasonably sized problem setting, the number of states and actions makes the resulting LP model intractable as it includes one variable for each state and one constraint for each state–action pair. A common approach to deal with this challenge is to approximate the value function. While there are different approximation architectures for this purpose, affine approximations in the state variables are not only easier to interpret but also provide computational advantages. Due to these advantages, we consider the following affine value function approximation in the state components:

$$\begin{array}{rl}\overline{V}(\overrightarrow{s})& =W_0+\sum _n\sum _{m\in M_T}{V}_m^n{x}_m^n+\sum _n\sum _j{V}_{cj}^n{x}_{cj}^n+\sum _n\sum _{m\in M_T}{G}_m^n{o}_m^n\end{array}$$

(23)

$$\begin{array}{rl}& +\sum _n\sum _j{G}_{cj}^n{o}_{cj}^n+\sum _i\sum _j{W}_{ij}{d}_{ij},\\ & \mathrm{\forall }\overrightarrow{s}\in S,\overrightarrow{V},\overrightarrow{G},\overrightarrow{W}\ge 0,W_0\in \mathbb{R},\end{array}$$

where $V_m^n$ and $V_{cj}^n$ can be interpreted as the marginal expected discounted cost of having one more regular-hour appointment slot booked for test $m$ and consultation of type $j$ on day $n$ , respectively. Similarly, $G_m^n$ and $G_{cj}^n$ correspond to the marginal expected discounted costs of having an additional overtime slot occupied for tests and consults, respectively. Lastly, $W_{ij}$ is the marginal expected discounted cost of having one more priority $i$ patient of type $j$ waiting to be booked.

4.2. Approximate Linear Programming (ALP) Model

If we substitute (23) into (22), we obtain the following ALP model:

$$\begin{array}{rl}\underset{\overrightarrow{V},\overrightarrow{G},\overrightarrow{W},W_0}{max}& [W_0+\sum _n\sum _{m\in M_T}{E}_{\alpha }(X_m^n)V_m^n+\sum _n\sum _j{E}_{\alpha }(X_{cj}^n)V_{cj}^n\\ & +\sum _n\sum _{m\in M_T}{E}_{\alpha }(O_m^n)G_m^n+\sum _n\sum _j{E}_{\alpha }(O_{cj}^n)G_{cj}^n\\ & +\sum _i\sum _j{E}_{\alpha }(D_{ij})W_{ij}]\end{array}$$

(24)

subject to:

$$\begin{array}{rl}& (1-\gamma )W_0+\sum _n\sum _{m\in M_T}\\ & \times [x_m^n(\overrightarrow{s})-\gamma (x_m^{n+1}(\overrightarrow{s})+\sum _i\sum _j{a}_{mij}^{n+1}(\overrightarrow{a})-z_m^{n+1}(\overrightarrow{a}))]V_m^n\\ & +\sum _n\sum _j[x_{cj}^n(\overrightarrow{s})-\gamma (x_{cj}^{n+1}(\overrightarrow{s})+\sum _{i=1}^I{a}_{cij}^{n+1}(\overrightarrow{a})-z_{cj}^{n+1}(\overrightarrow{a}))]V_{cj}^n\\ & +\sum _n\sum _{m\in M_T}[o_m^n(\overrightarrow{s})-\gamma (o_m^{n+1}(\overrightarrow{s})+z_m^{n+1}(\overrightarrow{a}))]G_m^n\\ & +\sum _n\sum _j[o_{cj}^n(\overrightarrow{s})-\gamma (o_{cj}^{n+1}(\overrightarrow{s})+z_{cj}^{n+1}(\overrightarrow{a}))]G_{cj}^n\\ & +\sum _i\sum _j[d_{ij}(\overrightarrow{s})-\gamma (d_{ij}(\overrightarrow{s})+{\lambda }_{ij}-\frac{1}{U_j}\sum _m\sum _n{a}_{mij}^n(\overrightarrow{a}))]\\ & \times W_{ij}\le c(\overrightarrow{s},\overrightarrow{a}),\mathrm{\forall }\overrightarrow{s}\in S,\overrightarrow{a}\in A_{\overrightarrow{s}},\end{array}$$

(25)

where $E_{\alpha }(X_m^n)$ , $E_{\alpha }(X_{cj}^n)$ , $E_{\alpha }(O_m^n)$ , $E_{\alpha }(O_{cj}^n)$ , and $E_{\alpha }(D_{ij})$ are the expected values of the different state components according to the probability distribution over the initial state of the system $\overrightarrow{\alpha }$ . The additional variables $x_m^{N+1}$ , $a_{mij}^{N+1}$ , $z_m^{N+1}$ , $x_{cj}^{N+1}$ , $a_{cij}^{N+1}$ , $z_{cj}^{N+1}$ , $o_m^{N+1}$ , $z_m^{N+1}$ , $o_{cj}^{N+1}$ , and $z_{cj}^{N+1}$ are set equal to zero as no bookings can occur beyond day $N$ .

4.3. Dual ALP (D-ALP) Model

The ALP model still has one constraint for each state–action pair, but the number of variables is now manageable. We therefore solve its dual in (26), where $X(\overrightarrow{s},\overrightarrow{a})$ is the dual variable corresponding to state–action pair $(\overrightarrow{s},\overrightarrow{a})$ , through column generation:

$$\begin{array}{r}\underset{\overrightarrow{X}\ge 0}{min}\sum _{\overrightarrow{s}\in S,\overrightarrow{a}\in A_{\overrightarrow{s}}}c(\overrightarrow{s},\overrightarrow{a})X(\overrightarrow{s},\overrightarrow{a})\end{array}$$

(26)

subject to:

$$\begin{array}{rl}& (1-\gamma )\sum _{\overrightarrow{s}\in S,\overrightarrow{a}\in A_{\overrightarrow{s}}}X(\overrightarrow{s},\overrightarrow{a})=1,\\ & \sum _{\overrightarrow{s}\in S,\overrightarrow{a}\in A_{\overrightarrow{s}}}[x_m^n(\overrightarrow{s})-\gamma (x_m^{n+1}(\overrightarrow{s})+\sum _{i=1}^I\sum _{j=1}^J{a}_{mij}^{n+1}(\overrightarrow{a})-z_m^{n+1}(\overrightarrow{a}))]\\ & \times X(\overrightarrow{s},\overrightarrow{a})\ge E_{\alpha }(X_m^n),\mathrm{\forall }n,m\in M_T,\\ & \sum _{\overrightarrow{s}\in S,\overrightarrow{a}\in A_{\overrightarrow{s}}}[x_{cj}^n(\overrightarrow{s})-\gamma (x_{cj}^{n+1}(\overrightarrow{s})+\sum _{i=1}^I{a}_{cij}^{n+1}(\overrightarrow{a})-z_{cj}^{n+1}(\overrightarrow{a}))]\\ & \times X(\overrightarrow{s},\overrightarrow{a})\ge E_{\alpha }(X_{cj}^{n+1}),\mathrm{\forall }n,j,\\ & \sum _{\overrightarrow{s}\in S,\overrightarrow{a}\in A_{\overrightarrow{s}}}[o_m^n(\overrightarrow{s})-\gamma (o_m^{n+1}(\overrightarrow{s})+z_m^{n+1}(\overrightarrow{a}))]\\ & \times X(\overrightarrow{s},\overrightarrow{a})\ge E_{\alpha }(O_m^n),\mathrm{\forall }n,m\in M_T,\\ & \sum _{\overrightarrow{s}\in S,\overrightarrow{a}\in A_{\overrightarrow{s}}}[o_{cj}^n(\overrightarrow{s})-\gamma (o_{cj}^{n+1}(\overrightarrow{s})+z_{cj}^{n+1}(\overrightarrow{a}))]\\ & \times X(\overrightarrow{s},\overrightarrow{a})\ge E_{\alpha }(O_{cj}^n),\mathrm{\forall }n,j,\\ & \sum _{\overrightarrow{s}\in S,\overrightarrow{a}\in A_{\overrightarrow{s}}}[d_{ij}(\overrightarrow{s})-\gamma (d_{ij}(\overrightarrow{s})+{\lambda }_{ij}-\frac{1}{U_j}\sum _{m\in M}\sum _n{a}_{mij}^n(\overrightarrow{a}))]\\ & \times X(\overrightarrow{s},\overrightarrow{a})\ge E_{\alpha }(D_{ij}),\mathrm{\forall }i,j.\end{array}$$

4.4. Column Generation Algorithm

The column generation algorithm solves (26) by starting with a small set of feasible state–action pairs and then finding the state–action pair associated with the most violated primal constraint in (24). It iteratively adds a feasible state–action pair before resolving (26) until no primal constraint is violated or until we are close enough to quit (stopping criterion of $0.001$ ). Thus, the algorithm involves solving two optimization problems, the restricted version of (26) and the pricing problem. The latter iteratively determines a new state–action pair to add to the former, that associated with the most negative reduced cost. The pricing problem is formulated as follows:

$$\begin{array}{rl}& \underset{\overrightarrow{s}\in S,\overrightarrow{a}\in A_{\overrightarrow{s}}}{\arg min}\{c(\overrightarrow{s},\overrightarrow{a})-(1-\gamma )W_0\\ & -\sum _n\sum _{m\in M_T}[x_m^n(\overrightarrow{s})-\gamma (x_m^{n+1}(\overrightarrow{s})+\sum _i\sum _j{a}_{mij}^{n+1}(\overrightarrow{a})-z_m^{n+1}(\overrightarrow{a}))]V_m^n\end{array}$$

$$\begin{array}{rl}& -\sum _n\sum _j[x_{cj}^n(\overrightarrow{s})-\gamma (x_{cj}^{n+1}(\overrightarrow{s})+\sum _i{a}_{cij}^{n+1}(\overrightarrow{a})-z_{cj}^{n+1}(\overrightarrow{a}))]V_{cj}^n\\ & -\sum _n\sum _{m\in M_T}[o_m^n(\overrightarrow{s})-\gamma (o_m^{n+1}(\overrightarrow{s})+z_m^{n+1}(\overrightarrow{a}))]G_m^n\\ & -\sum _n\sum _j[o_{cj}^n(\overrightarrow{s})-\gamma (o_{cj}^{n+1}(\overrightarrow{s})+z_{cj}^{n+1}(\overrightarrow{a}))]G_{cj}^n\\ & -\sum _i\sum _j[d_{ij}(\overrightarrow{s})-\gamma (d_{ij}(\overrightarrow{s})+{\lambda }_{ij}-\frac{1}{U_j}\sum _m\sum _n{a}_{mij}^n(\overrightarrow{a}))]W_{ij}\},\end{array}$$

(27)

subject to constraints (1) to (8).

Solving the pricing problem in (27) requires a finite state space. For this reason, we impose an upper bound on the number of patients of each type and priority level waiting to be booked. The bounds are set sufficiently high, at 10 times the nearest nonzero integer value of the corresponding mean arrival rate, so they are of little practical significance. A pseudo-code of the column generation algorithm is provided in the E-Companion file that is available as an online supplement.

4.5. Optimal Form of the Approximation Parameters

Once the D-ALP model is solved, the shadow price associated with each constraint determines the optimal value of the corresponding approximation coefficient. The analysis of the solutions obtained for a wide range of small problem settings led to a conjecture of the form of the optimal solution to the ALP model. This, in turn, led to the theorem below, which provides interpretable conditions under which the optimal values of the approximation parameters can be computed directly.

Theorem 1 (Optimal form and optimality conditions)

Assume that the unit overtime cost is the same for all priority classes and only differs between tests and consults, the wait-time targets are strictly increasing in the priority level, and the following conditions hold:

$$\begin{array}{rl}& {\displaystyle \sum _m{\gamma }^{(T_i-T_1)}{u}_{mj}{d}_m\le \frac{g_i}{(1-\gamma )},\mathrm{\forall }i,j,}\end{array}$$

(28)

$$\begin{array}{rl}& b_i^n+{\gamma }^{(n-T_1)}{d}_c-b_i^{T_i}-{\gamma }^{(T_i-T_1)}{d}_c>0,\mathrm{\forall }i,n>T_i,\end{array}$$

(29)

$$\begin{array}{rl}& \sum _{t=n}^N{\gamma }^{(t-n)}{E}_{\alpha }(X_m^t)+\frac{\sum _{i,j}{\gamma }^{(T_i-L{T}_m-n)}{\mathbb{1}}_{(T_i>n+L{T}_m)}{u}_{mj}{\lambda }_{ij}}{1-\gamma }\le \frac{C_m^R}{1-\gamma },\\ & \mathrm{\forall }m\in M_T,n\ge T_1-L{T}_m,\end{array}$$

(30)

$$\begin{array}{rl}& \sum _{t=n}^N{\gamma }^{(t-n)}{E}_{\alpha }(X_{jc}^t)+\frac{\sum _i{\gamma }^{(T_i-n)}{\mathbb{1}}_{(T_i>n)}{\lambda }_{ij}}{1-\gamma }\le \frac{C_{cj}^R}{1-\gamma },\mathrm{\forall }j,n\ge T_1,\end{array}$$

(31)

where ${\mathbb{1}}_x$ is an indicator function with condition $x$ . Then, the optimal values of the approximation parameters will have the following form:

$$\begin{array}{rl}{V}_{cj}^n& =\{\begin{array}{ll}0& 1\le n\le {\widehat{LT}}_j,\\ d_c& {\widehat{LT}}_j<n\le T_1,\\ d_c{\gamma }^{(n-T_1)}& T_1<n\le N-{\widehat{LT}}_j,\\ 0& N-{\widehat{LT}}_j<n\le N,\end{array}\mathrm{\forall }j,\end{array}$$

(32)

$$\begin{array}{rl}{V}_m^n& =\{\begin{array}{ll}{d}_m& 1\le n\le T_1-L{T}_m,\\ d_m{\gamma }^{(n-T_1+L{T}_m)}& T_1-L{T}_m<n\le N-L{T}_m,\\ 0& N-L{T}_m<n\le N,\end{array}\mathrm{\forall }m\in M_T,\end{array}$$

(33)

$$\begin{array}{rl}{G}_m^n& =0,\mathrm{\forall }n,m,\end{array}$$

(34)

$$\begin{array}{rl}{G}_{cj}^n& =0,\mathrm{\forall }n,j,\end{array}$$

(35)

$$\begin{array}{rl}{W}_{ij}& =\sum _{m\in M{C}_j}{V}_m^{(T_i-L{T}_m)}+V_{cj}^{T_i},\mathrm{\forall }i,j,\end{array}$$

(36)

$$\begin{array}{rl}{W}_0& =\frac{1}{1-\gamma }[\sum _{m\in M_T}[(T_1-L{T}_m-1)(\gamma d_m-d_m)-d_m]C_m^R\\ & +\sum _j[(T_1-{\widehat{LT}}_j-1)(\gamma d_c-d_c)-d_c]C_{cj}^R\\ & +\sum _i\sum _j\sum _{m\in M{C}_j}{\gamma }^{(T_i-T_1+1)}{u}_{mj}{d}_m{\lambda }_{ij}],\end{array}$$

(37)

where ${\widehat{LT}}_j=max\{L{T}_m:m\in M{C}_j\}$ .

Equation (28) states that the cost of postponing the booking decisions for a priority $i$ patient of type $j$ indefinitely must be greater than the cost of using overtime $T_i-T_1$ days into the future for all the required appointments. This condition implies that postponing the booking decisions is never a convenient option. Equation (29) requires that the cost of booking a priority $i$ consult on day $n>T_i$ and then resorting to overtime $n-T_1$ days into the future be greater than the cost of booking the consult on day $T_i$ and then resorting to overtime $T_i-T_1$ days into the future. Put simply, this condition ensures that the increase in cost due to booking late is higher than the benefit of delaying overtime. Equation (30) requires that for any given test resource $m$ and day $n\ge T_1-L{T}_m$ , there is sufficient regular-hour capacity to book the average demand for any class of patient with a wait-time target exceeding $n+L{T}_m$ days. Similarly, equation (31) requires that for any given patient type $j$ and day $n\ge T_1$ , there is sufficient regular-hour consultation capacity to book the average demand for any priority level with a wait-time target longer than $n$ days. This condition thus implies that overtime is only needed for the highest priority patients. If the aforementioned conditions are not met, it typically indicates either the use of unrealistic cost structure (e.g., an excessively high overtime cost compared to the cost of postponement or booking beyond wait-time targets being unrealistically inexpensive) or a severe capacity shortage. In either case, the choice of scheduling policy becomes less relevant—unrealistic cost structures lead to irrational decisions, while an undercapacitated system inevitably results in increasing waiting lists or excessive overtime usage.

The mathematical proof for the above closed-form solution is presented in the E-Companion file available as an online supplement. A significant advantage of having a closed-form solution for the optimal values of the approximation parameters is the ability to circumvent the computationally intensive procedures involved in solving the ALP model for real-world problem configurations, some of which cannot even be solved directly. Thus, large-scale settings are now solvable.

4.6. Approximate Optimal Policy (AOP)

To identify the approximate optimal booking decisions for any given state of the system, we must solve the integer programming model in (38). The model is obtained by inserting the optimal value function approximation defined by Theorem 1 into the right-hand side of the optimality equations and ignoring constant terms. We call the resulting decision policy the AOP.

$$\begin{array}{rl}& {\overrightarrow{a}}^{*}(\overrightarrow{s})\in \underset{\overrightarrow{a}\in A_{\overrightarrow{s}}}{\arg min}\\ & =\{\sum _{n=1}^N\sum _i\sum _j{\tilde{b}}_{ij}^n{a}_{cij}^n+\sum _{n=1}^N\sum _{m\in M_T}\sum _i\sum _j{\tilde{b}}_{mij}^n{a}_{mij}^n\\ & +\sum _{n=1}^N\sum _{m\in M_T}{\tilde{d}}_m^n{z}_m^n+\sum _{n=1}^N\sum _j{\tilde{d}}_{cj}^n{z}_{cj}^n\},\mathrm{\forall }\overrightarrow{s}\in S,\end{array}$$

(38)

where

$$\begin{array}{rl}{\tilde{b}}_{ij}^n& =b_i^n+\gamma V_{cj}^{n-1}-\frac{1}{U_j}{g}_i-\frac{1}{U_j}{W}_{ij},\mathrm{\forall }n,i,j,\end{array}$$

(39)

$$\begin{array}{rl}{\tilde{b}}_{mij}^n& =\gamma V_m^{n-1}-\frac{1}{U_j}{g}_i-\frac{1}{U_j}{W}_{ij},\mathrm{\forall }n,i,j,m\in M_T,\end{array}$$

(40)

$$\begin{array}{rl}{\tilde{d}}_{cj}^n& =d_c+\gamma G_{cj}^{n-1}-\gamma V_{cj}^{n-1},\mathrm{\forall }n,j,\end{array}$$

(41)

$$\begin{array}{rl}{\tilde{d}}_m^n& =d_m+\gamma G_m^{n-1}-\gamma V_m^{n-1},\mathrm{\forall }n,m\in M_T.\end{array}$$

(42)

Based on equation (39), the adjusted coefficient ${\tilde{b}}_{ij}^n$ balances the penalty associated with booking a consult appointment for a priority $i$ patient of type $j$ on day $n$ and the marginal opportunity cost of having one fewer appointment slot available in regular time, $b_i^n+\gamma V_{cj}^{n-1}$ , against the benefit resulting from not having the booking decision postponed and the request reappearing in tomorrow’s demand, $(1/U_j)W_{ij}+(1/U_j)g_i$ . Similarly, the adjusted coefficient ${\tilde{b}}_{mij}^n$ in equation (40) balances the cost and benefits associated with booking a test appointment of type $m$ for a priority $i$ patient of type $j$ . In this equation, the term $\gamma V_m^{n-1}$ represents the marginal opportunity cost due to the loss of available regular-hour capacity in the future, which is offset by the benefits associated with booking the corresponding consult appointment. Finally, the adjusted coefficients ${\tilde{d}}_{cj}^n$ and ${\tilde{d}}_m^n$ , respectively, balance the cost associated with a one unit increase in the total consultation and test capacity on day $n$ and the opportunity cost due to the loss of available overtime capacity on day $n-1$ tomorrow, $d_c+\gamma G_{cj}^{n-1}$ and $d_m+G_m^{n-1}$ , against the benefit of freeing regular-hour capacity on day $n-1$ tomorrow, $\gamma V_{cj}^{n-1}$ and $\gamma V_m^{n-1}$ .

The various mathematical programming models and algorithms described throughout the paper, including the simulation algorithm introduced later, were implemented in Python 3.9.13, using Gurobi 10.0.1 as the optimization solver.

5. Numerical Experiments

In this section, we begin by examining a small instance of the scheduling problem, analyzing the actions suggested by the AOP and deriving an easy-to-use heuristic which we call MSP. Then, to evaluate the performance of the AOP and MSP policies for a full-scale instance, we consider the problem faced by a regional SPC. Through simulation, we compare the performance of these two policies to that of the following six benchmark policies. The policies are compared based on the proportion of patients whose waiting time for consultation exceeds the priority-specific target, the proportion of patients who are served using overtime, the average regular-hour capacity utilization, the average waiting time for a consult appointment, and the total discounted cost. Given the absence of preexisting booking policies tailored to multi-priority, multi-appointment scheduling with dependent demand and lead times, we adapted the core principles of prevalent scheduling policies from the literature and tailored them to suit this specific problem setting. The corresponding pseudo-codes can be found in the E-Companion file.

Myopic. Consults and tests are booked according to the immediate cost function defined in (19). This policy ignores the impact of today’s booking decisions on the future performance of the system and, mathematically speaking, can be formulated as follows:

$${\overrightarrow{a}}^{*}(\overrightarrow{s})\in {\arg min}_{\overrightarrow{a}\in A_{\overrightarrow{s}}}\{c(\overrightarrow{s},\overrightarrow{a})\},\mathrm{\forall }\overrightarrow{s}\in S,$$

(43)

The main logic for each of the following three benchmark policies has been adopted from the literature. In each case, the booking agent books appointments in increasing priority order and, within each priority, in an increasing patient type sequence (i.e., type 1, type 2, etc.).

Adapted DMB (A-DMB). Consults and tests are booked according to the DMB guidelines originally introduced by Sauré et al. (2015). The DMB policy books patients as soon as possible, in increasing priority order, first on day 1 while regular-hour capacity is still available and then on the day with the minimum number of bookings within the corresponding wait-time target. Overtime is used only when there is no available capacity within the wait-time target. A pseudo-code of the adaptation of the DMB policy to the particular problem setting under consideration is provided in the E-Companion file.

Adapted PPQ (A-PPQ). Consults and tests are booked according to the PPQ booking guidelines derived by Patrick et al. (2008). The PPQ policy books patients in priority order within their respective wait-time targets. Priority 1 patients are scheduled as soon as possible on days 1 to $T_1$ , whereas lower priority patients are booked starting with day 1, then day $T_i$ , and working backwards to day 2. Overtime is used for any remaining appointment requests. A pseudo-code of the adaptation of the PPQ policy is presented in the E-Companion file.

Hybrid. Tests are booked according to the A-DMB policy, whereas consults are booked according to the A-PPQ policy. This policy book consults as far out as possible while respecting the priority-specific wait-time targets so as to provide as much time as possible to complete tests.

Heuristic 1. In practice, consults are sometimes performed with an incomplete set of test results. This typically occurs in clinical settings where the main goal is to book consults within their corresponding wait-time targets, regardless of the availability of test results. The booking agent then books as many tests as possible within the time windows defined by the day of the consult appointment and the respective lead times. To reflect the current practice, Heuristic 1 books patients in increasing priority order. For each patient, it first schedules their consult as late as possible within the priority-specific wait-time target and then uses a First Available Slot (FAS) policy to book the required tests, prioritizing regular-hour bookings over overtime on a daily basis. A pseudo-code of the Heuristic 1 policy is provided in the E-Companion file.

Heuristic 2. Heuristic 1 alternates between regular time and overtime as it works backward, looking for available consultation capacity. This is done to keep the booking window for the required tests as wide as possible. Heuristic 2 follows the same booking guidelines as Heuristic 1 but uses the regular-hour capacity in full before switching to overtime. A pseudo-code of the Heuristic 2 policy is provided in the E-Companion file.

To better reflect the current practice, we also consider versions of Heuristics 1 and 2 in which overtime bookings are not allowed. We call these additional scheduling policies Heuristic 1 ${}^{*}$ and Heuristic 2 ${}^{*}$ , respectively.

5.1. A Small Instance

Consider a clinic that divides demand into three priority classes, with wait-time targets of 5, 10, and 15 days, and two patient types. Demand from each patient type–priority combination is assumed to be Poisson with means given in Table 2. Every patient requires two out of three possible tests according to the requirements and lead times presented in the same table. The clinic has a consultation capacity of 10 appointment slots per day for each patient type and test capacities of 10, 10, and 20 appointment slots per day, respectively. The clinic chooses a 16-day booking horizon. The overtime cost is 50, the late booking penalties are 20, 10, and 5, and the discount factor is 0.99. Obtaining the approximation parameters for this small instance through column generation took <5 min. For larger instances, it is much more time-consuming, but having the closed-form solution for the approximation parameters renders it unnecessary. For the simulation, each booking policy was simulated for 2,500 days using common patient arrivals with statistics collected for each of 100 simulation runs after a warm-up period of 1,250 days. The warm-up period was simulated under the Myopic policy. Simulation results are displayed in Figure 2. Executing the simulation model for such a long period of time takes almost 2 h.

Table 2.

Small example used to evaluate the performance of the different policies and characterize the approximate optimal policy (AOP).

Tests	Test 1	Test 2	Test 3	Consult	Priority 1	Priority 2	Priority 3
				Capacity
Patient types	Required appointments			(slots/day)	Arrival rates (requests/day)
1	✓	–	✓	10	5	3	2
2	–	✓	✓	10	5	3	2
Lead time (days)	1	1	2	–	–	–	–
Capacity (slots/day)	10	10	20	–	–	–	–
Target dates (day)	–	–	–	–	5	10	15
Postponement unit cost ($)	–	–	–	–	20	10	5
Overtime unit cost ($)	50	50	50	50	–	–	–

Figure 2.

Performance of the various booking policies in terms of different metrics for a small example. (a) Total discounted cost ($), (b) proportion of consults booked late, (c) proportion of demand diverted to overtime, and (d) regular-hour capacity utilization.

The results in Figure 2(a) (with numbers displayed in Table 5) for the baseline scenario demonstrates that the AOP outperforms all the benchmark policies with respect to the mean total discounted cost, with MSP (explained in detail later) being the second-best policy. The A-PPQ emerges as the third-best policy while Heuristic 1 ${}^{*}$ and Heuristic 2 ${}^{*}$ , together with the Myopic policy, exhibit the worst performance. Both versions of Heuristics 1 and 2 (in which overtime booking is allowed) manage to provide all test results by the consultation dates, but at a much higher cost than the AOP. Table 3 provides the 95% confidence interval for the mean proportion of consults performed with a complete set of test results for Heuristic 1 ${}^{*}$ and Heuristic 2 ${}^{*}$ by priority level. The unavailability of test results occurs frequently under these two policies and is a more serious issue for high-priority patients, as their wait-time target is shorter, leading to a tighter booking window. The results reflect the current practice where more urgent patients are more likely to experience longer-than-recommended wait times and receive consultation appointments before all the required test results are available. For this reason, and given the fact that the versions without overtime more closely reflect reality, we omit Heuristics 1 and 2 in Figure 2(b) to (d).

Table 3.

Resulting 95% confidence interval for the mean proportion of consults performed with a complete set of test results for Heuristic 1 ${}^{*}$ and Heuristic 2 ${}^{*}$ by priority level.

	Proportion of tests completed (%)
Priority	Test 1	Test 2	Test 3
1	$0.75\pm 0.07$	$0.71\pm 0.06$	$0.83\pm 0.04$
2	$0.87\pm 0.05$	$0.80\pm 0.06$	$0.95\pm 0.03$
3	$0.97\pm 0.01$	$0.95\pm 0.01$	$0.99\pm 0.01$

Table 4.

Details of six scenarios for systematically changing the main parameters.

		Resource				Priority level
Scenario	Parameter	Test 1	Test 2	Test 3	Consult	Priority 1	Priority 2	Priority 3
Scenario 1	$d_m$	50	50	50	50	–	–	–
(Baseline)	$g_i$	–	–	–	–	20	10	5
	$T_i$	–	–	–	–	5	10	15
	$b_i^n$	Discounted
Scenario 2	$d_m$	50	50	50	50	–	–	–
	$g_i$	–	–	–	–	20	15	15
	$T_i$	–	–	–	–	5	10	10
	$b_i^n$	Discounted
Scenario 3	$d_m$	50	50	50	50	–	–	–
	$g_i$	–	–	–	–	20	15	15
	$T_i$	–	–	–	–	5	10	15
	$b_i^n$	Discounted
Scenario 4	$d_m$	20	30	40	100	–	–	–
	$g_i$	–	–	–	–	20	10	5
	$T_i$	–	–	–	–	5	10	15
	$b_i^n$	Discounted
Scenario 5	$d_m$	50	50	50	150	–	–	–
	$g_i$	–	–	–	–	20	10	5
	$T_i$	–	–	–	–	5	10	10
	$b_i^n$	Exponential
Scenario 6	$d_m$	150	150	150	50	–	–	–
	$g_i$	–	–	–	–	20	10	5
	$T_i$	–	–	–	–	5	10	15
	$b_i^n$	Exponential

As can be seen from Figure 2(b), the AOP and the A-PPQ policy excel at meeting wait time targets, while all the other policies book some consultation appointments late. The A-DMB and Hybrid policies exhibit fewer late consult bookings compared with the heuristics and the Myopic policy, especially for higher priority patients. Figure 2(c) shows that nearly all the policies maintain an overtime utilization below 3% and 8% for the tests and consults, respectively, with all the benchmark policies exhibiting higher usage of overtime for consults. The Myopic policy uses the least amount of overtime, keeping higher congestion levels, at the expense of a higher number of late bookings. The AOP’s judicious use of overtime for the tests is one of the key factors enabling the AOP to efficiently meet the wait-time targets for consultation. Finally, Figure 2(d) demonstrates that all policies provide a mean average regular-hour capacity utilization close to 100% for the three tests. However, the A-DMB, A-PPQ, and Hybrid policies show some underutilization, relatively speaking. Overall, we can conclude that the AOP is the dominant policy.

5.2. Sensitivity Analysis

In this subsection, we conduct a sensitivity analysis around the optimality conditions stated in the theorem for the problem setting introduced in subsection 5.1. We define six distinct scenarios in which we vary the unit costs and wait-time targets to evaluate the robustness of the conditions and the validity of the closed-form solution. These scenarios account for situations where wait-time targets are not strictly increasing, allowing some priority levels to share the same target date, while other priority-specific unit costs might differ. Additionally, we explore scenarios where overtime costs vary across resources, and late booking cost follows a steeper, exponentially increasing function rather than the current discounted structure. The six scenarios are summarized in Table 4. Scenario 1 represents the baseline scenario defined by the parameter values in Table 2. In the E-Companion file, graphical displays are provided to illustrate in all scenarios, including the baseline, all conditions (i.e., inequalities (28), (29), (30), and (31)) are satisfied, and the closed-form solution remains valid. As the figure demonstrates, the difference between the RHS and LHS of the four conditions is rather significant, which shows that the conditions are easy to meet. The simulation results presented in Table 5 show that although the performance of all policies is affected, the AOP provides the best average discounted cost for each scenario.

Table 5.

Results for different scenarios.

Scenario	AOP	Myopic	A-DMB	A-PPQ	Hybrid	MSP	Heuristic 1*	Heuristic 2*
1	$\mathbf{3}\mathbf{,}\mathbf{879}$	$47,318$	$21,198$	$7,329$	$21,226$	$5,120$	$47,606$	$47,606$
(Baseline)	$\pm \mathbf{902}$	$\pm 7,570$	$\pm 1,933$	$\pm 1,185$	$\pm 1,939$	$\pm 1,088$	$\pm 9,526$	$\pm 9,526$
2	$\mathbf{4}\mathbf{,}\mathbf{739}$	$47,775$	$21,980$	$8,407$	$21,868$	$6,379$	$45,536$	$45,536$
	$\pm \mathbf{923}$	$\pm 7,285$	$\pm 1,795$	$\pm 1,242$	$\pm 1,838$	$\pm 1,071$	$\pm 8,277$	$\pm 8,277$
3	$\mathbf{4}\mathbf{,}\mathbf{280}$	$50,661$	$22,672$	$7,912$	$22,616$	$5,820$	$51,091$	$51,091$
	$\pm \mathbf{976}$	$\pm 7,282$	$\pm 1,951$	$\pm 1,270$	$\pm 1,975$	$\pm 1,088$	$\pm 9,189$	$\pm 9,189$
4	$\mathbf{5}\mathbf{,}\mathbf{133}$	$44,289$	$26,597$	$12,833$	$27,558$	$8,647$	$49,710$	$49,710$
	$\pm \mathbf{1}\mathbf{,}\mathbf{073}$	$\pm 5,972$	$\pm 2,275$	$\pm 1,812$	$\pm 2,328$	$\pm 1,434$	$\pm 8,812$	$\pm 8,812$
5	$\mathbf{8}\mathbf{,}\mathbf{598}$	$49,104$	$32,162$	$20,513$	$33,774$	$14,415$	$44,766$	$44,766$
	$\pm \mathbf{1}\mathbf{,}\mathbf{554}$	$\pm 7,464$	$\pm 2,731$	$\pm 2,689$	$\pm 2,796$	$\pm 2,158$	$\pm 8,038$	$\pm 8,038$
6	$\mathbf{9}\mathbf{,}\mathbf{274}$	$58,409$	$26,567$	$12,185$	$26,529$	$10,084$	$51,884$	$51,884$
	$\pm \mathbf{1}\mathbf{,}\mathbf{769}$	$\pm 9,526$	$\pm 3,167$	$\pm 2,372$	$\pm 3,197$	$\pm 2,200$	$\pm 9,311$	$\pm 9,311$

Note. AOP = approximate optimal policy; A-DMB = adapted day with the minimum number of bookings; A-PPQ = adapted Patrick–Puterman–Queyranne.

According to our analysis, it appears that sharing target dates makes the policies indifferent between the affected priority levels with respect to them (scenarios 2 and 5). Also, since the AOP does not postpone the booking of patients to later days, its performance is not affected in scenarios in which only the postponement cost changes (scenarios 1 and 3). It appears that in the realistic settings where consultation has a higher overtime cost compared to tests, the AOP is even more superior to other policies due to its small overtime usage for the consultation (scenarios 4 and 5). In contrast, when tests are associated with higher overtime costs, the difference becomes less significant, as other policies perform relatively well (scenario 6). In scenarios 5 and 6, where late booking follows an exponential structure, no significant difference was observed in the performance and behavior of the AOP, as postponement and late booking are never recommended even under the baseline scenario.

5.3. AOP Characterization

Closely observing the actions suggested by the AOP reveals that the actions are driven by the adjusted coefficients multiplying the booking and capacity-increase decision variables in (38). The coefficients defined by equations (39) to (42), however, do not directly model the dependency between the booking of testing and consultation appointments.

Let us consider a priority $i$ patient of type $j$ . It is evident that if we book at least one required test $m\in M{C}_j$ later than day $T_i-L{T}_m$ , and we impose that all test results must be available prior to consultation, then the consult appointment will unavoidably take place after $T_i$ and a penalty will incur. However, this additional cost does not directly appear in the definition of the adjusted coefficient ${\tilde{b}}_{mij}^n$ in equation (40), illustrating again the extra layer of complexity introduced by the precedence relationship between test and consult appointment and the associated lead times. Figure 3(a) shows the values of the ${\tilde{b}}_{mij}^n$ coefficient for each patient type–priority combination for the small instance described earlier, disregarding this dependency. As can be seen, if we rely solely on the values of ${\tilde{b}}_{mij}^n$ , and after using all the available capacity of day 1, we should book all the required testing appointments on day $N$ , which does not reflect the AOP. Therefore, to capture the interdependence between the two types of booking decisions and thus accurately characterize the AOP, we redefine (for analysis purpose only) the adjusted coefficient ${\tilde{b}}_{mij}^n$ to consider a consult delay penalty when a required test $m\in M{C}_j$ is booked later than day $T_i-L{T}_m$ . The new coefficient is denoted by ${\hat{b}}_{mij}^n$ and is defined as:

$$\begin{array}{rl}{\hat{b}}_{mij}^n& =b_i^{n+L{T}_m}+\gamma V_m^{n-1}-\frac{1}{U_j}{g}_i-\frac{1}{U_j}{W}_{ij},\\ & \mathrm{\forall }1\le n\le N-L{T}_m,i,j,m\in M_T.\end{array}$$

Figure 3.

Graphical display of the values of ${\tilde{b}}_{mij}^n$ versus ${\hat{b}}_{mij}^n$ for a small problem setting. (a) Coefficient ${\tilde{b}}_{mij}^n$ and (b) coefficient ${\hat{b}}_{mij}^n$ .

Figure 3(b) displays the values of ${\hat{b}}_{mij}^n$ for the small problem setting. Based on these values, the tests required by the highest priority patients should be booked as soon as possible on days 1 to $T_i-L{T}_m$ . After using the capacity of day 1, a FAS policy is assumed suitable as the values of the coefficient ${\hat{b}}_{mij}^n$ are the same for days 2 to $T_i-L{T}_m$ . The tests required by lower priority patients, on the other hand, should be booked starting with day 1, then day $T_i-L{T}_m$ , and working backwards to day 2. Similar to the previous case, a backward progression is assumed suitable within the first $T_1-L{T}_m$ days as the coefficient values are the same within this range. Booking test $m$ after day $N-L{T}_m$ does not leave sufficient time to book the corresponding consult, so this is never done.

Consult booking decisions are driven by the values of coefficient ${\tilde{b}}_{ij}^n$ , which was defined in equation (39). Figure 4(b) provides such values for the small problem setting. Consult appointments for the highest priority patients should be booked as soon as possible, starting with day ${\widehat{LT}}_j$ , as there is no way that the test results will be ready before then. Consult appointments for lower priority patients, on the other hand, should be scheduled starting with day ${\widehat{LT}}_j$ , then day $T_i$ , and working down to day ${\widehat{LT}}_j+1$ . According to Figures 3(b) and 4(b), the booking of a test $m$ after day $T_i-L{T}_m$ and for a consult, after day $T_i$ is associated with an increasing cost due to the increasing structure of $b_i^n$ . It is worth mentioning that considering more steeply increasing $b_i^n$ values would not have any practical impact on the AOP, as it would simply increase the cost of actions that are already not recommended.

Figure 4.

Graphical display of the values of ${\hat{b}}_{mij}^n+{\tilde{d}}_m^n$ and ${\tilde{b}}_{ij}^n$ versus ${\tilde{b}}_{ij}^n+{\tilde{d}}_{cj}^n$ for a small problem setting. (a) Coefficient ${\hat{b}}_{mij}^n+{\tilde{d}}_m^n$ and (b) coefficient ${\tilde{b}}_{ij}^n$ versus ${\tilde{b}}_{ij}^n+{\tilde{d}}_{cj}^n$ (RT: regular-time; OT: overtime).

The use of overtime is a dependent decision variable as it depends on the main booking decisions given by the values of $a_{ijm}^n$ . The AOP prioritizes regular-hour bookings over overtime bookings given their lower cost. However, when no regular-hour appointment slot is available, the AOP resorts to overtime. Therefore, the total cost associated with booking tests and consults through overtime is given by ${\hat{b}}_{mij}^n+{\tilde{d}}_m^n$ and ${\tilde{b}}_{ij}^n+{\tilde{d}}_{cj}^n$ , respectively. Figure 4(a) and (b) provides the total cost values for the small problem setting. As can be seen, the overtime coefficients are always higher than those of regular time. For consults, the AOP prefers resorting to overtime rather than booking appointments late. A FAS policy is also suitable for booking overtime appointments within the wait-time targets. For tests, similar to consults, booking overtime is allowed only once all regular-hour appointment slots within the wait-time target have been booked, and provided there is enough overtime capacity within the booking windows defined by days 1 and $T_i-L{T}_m$ .

The set of booking guidelines derived from the characterization of the AOP is outlined in Algorithm 1 and called the MSP policy. As can be seen from Figure 2, the MSP policy closely reflects the AOP outperforming the other benchmark policies in terms of the total discounted cost. The main advantage of the MSP policy over the AOP is its simplicity and the fact that there is no need to solve an optimization model every time that the optimal booking actions need to be determined.

The main difference between the AOP and the MSP policy lies in the use of overtime. Every time that there is available regular-hour consultation capacity on day ${\widehat{LT}}_j$ and not enough regular-hour resource capacity earlier in the booking horizon, the AOP will book the consult appointment on day ${\widehat{LT}}_j$ and the required tests earlier on the first day with available capacity. In this way, the AOP avoids delaying the booking of the consult appointment, which in turn results in a better utilization of the regular-hour consultation capacity on day ${\widehat{LT}}_j$ . This characteristic of the AOP is easy to see from the values of the adjusted booking coefficients presented in Figure 4. Although this rule is simple to explain, it is not easy to incorporate into the definition of the MSP policy. While the AOP determines the approximate optimal booking actions for all patient types and priorities simultaneously using an optimization model, the MSP policy inevitably schedules sequentially by imposing a booking order on patient types.

Overall, both the AOP and the MSP policy book appointments in such a way that consults take place within their respective wait-time targets and with all the required test results available. However, as can be seen from Table 6, the AOP does a superior job at keeping the wait times for consult appointments short compared to all other policies, making the best use of regular-hour capacity and lowering overtime usage for consult appointments. The MSP policy is the second-best policy in this regard.

Table 6.

Resulting 95% confidence interval for the mean average wait time for consultation for each policy and priority level.

	Average wait time for consultation (days)
Policy	Priority 1	Priority 2	Priority 3
AOP	2.52 $\pm$ 0.04	6.58 $\pm$ 0.17	10.98 $\pm$ 0.14
Myopic	$10.75\pm 0.37$	$10.96\pm 0.32$	$11.81\pm 0.09$
A-DMB	$4.36\pm 0.07$	$8.16\pm 0.04$	$11.41\pm 0.07$
A-PPQ	$3.15\pm 0.04$	$8.32\pm 0.04$	$12.01\pm 0.07$
Hybrid	$4.28\pm 0.07$	$8.26\pm 0.03$	$11.43\pm 0.06$
MSP	$2.87\pm 0.04$	$8.06\pm 0.05$	$11.92\pm 0.05$
Heuristic 1 ${}^{*}$	$10.67\pm 0.68$	$10.69\pm 0.40$	$12.10\pm 0.03$
Heuristic 1	$3.97\pm 0.00$	$8.55\pm 0.01$	$12.11\pm 0.03$
Heuristic 2 ${}^{*}$	$10.67\pm 0.68$	$10.69\pm 0.40$	$12.10\pm 0.03$
Heuristic 2	$3.86\pm 0.00$	$8.55\pm 0.01$	$12.11\pm 0.03$

Note: ‘*’ indicates that the use of overtime is not allowed. AOP = approximate optimal policy; A-DMB = adapted day with the minimum number of bookings; A-PPQ = adapted Patrick–Puterman–Queyranne.

Next, we describe the performance of the AOP and the MSP policy for a practical case study.

5.4. A Practical Application

A practical instance was created based on data provided by a regional SPC, with increased arrival rates to reflect the operations of a large clinic and illustrate the scalability of the proposed solution approach. The goal of the SPC is to ensure that individuals who are at high risk for stroke receive timely, evidence-based care. To access the SPC, a patient needs a referral by an emergency room physician, their family physician, or another medical specialist. Upon receipt of the referral, an administrative assistant will contact the patient with an appointment to see a neurologist. Because treatment depends on the type of stroke, the results of one or more tests may be needed at the time of this initial consultation. The tests used by neurologists at the SPC include an Echocardiogram (Echo), a Holter test, a Doppler test, and a CT scan. At the clinic, the patient will meet with the stroke neurologist and the stroke prevention nurse specialist to discuss their risk factors. Patients may then receive treatment, have additional tests, or be referred to another specialist. The SPC is currently facing long patient wait times from referral to consult, with required test results often not ready for use before the initial visit.

The clinic divides demand into four priority classes with wait-time targets of 5, 10, 15, and 20 days, respectively, and uses a 30-day booking horizon. It also classifies patients into 16 types depending on the set of medical tests required. Demand from each patient type–priority combination is assumed to be Poisson with arrival rates, lead times, and patient types provided in Table 7. Regular-hour and overtime capacities for each testing resource and type of consultation are presented in the same table. The overtime cost is $50 per appointment slot, the postponement penalties are $20, $15, $10, and $5 per patient for each priority level, and the discount factor is 0.99. It is worth mentioning that the practical problem setting and the value of the different input parameters were discussed with the analytics lead assisting the clinic at the time of the study. However, the arbitrary nature of the aforementioned unit costs and the ones used for creating the small instance is of little concern, as what really matters are the relative values of the cost parameters, and the resulting policy is robust to these. Similar values have been used in previous studies (Patrick et al., 2008; Sauré et al., 2012). Additionally, as discussed in subsection 5.2, the performance of the AOP is very robust to changes in the cost parameter, and the policy works well for a wide range of these parameter values, making the specific values being used of less concern.

Table 7.

Characteristics of a practical application based on a regional SPC.

	Required appointments				Consult capacity	Arrival rates (requests/day)
Patient type	CT	Doppler	Holter	Echo	(slots/day)	Priority 1	Priority 2	Priority 3	Priority 4
1	✓	–	✓	–	11	4	2	4	1
2	✓	✓	✓	–	11	3	3	3	2
3	–	✓	✓	–	7	3	2	1	1
4	✓	–	–	✓	7	1	2	3	1
5	✓	–	✓	✓	10	2	3	2	3
6	✓	✓	–	–	11	2	4	3	2
7	–	✓	–	–	7	3	2	1	1
8	–	–	✓	–	7	1	2	3	1
9	✓	–	–	–	10	2	3	2	3
10	–	✓	–	✓	11	2	4	3	2
11	✓	✓	–	✓	7	3	2	1	1
12	–	–	–	–	7	1	2	3	1
13	–	–	–	✓	10	2	3	2	3
14	–	✓	✓	✓	11	2	4	3	2
15	✓	✓	✓	✓	9	3	3	2	1
16	–	–	✓	✓	11	4	2	3	2
Lead time (days)	1	1	1	1	Target (days)	5	10	15	20
Capacity (slots/day)	76	74	77	76	–	–	–	–	–

Note. SPC = Stroke Prevention Clinic; CT = computed tomography.

The SPC’s operation was simulated under the AOP and the MSP policy for 2,500 days using probabilistic patient arrivals with statistics collected for 1,250 simulation days after a warm-up period of 1,250 days. The warm-up period was simulated under the Myopic policy. The performances of the AOP and MSP are compared to those of the other six benchmark policies. The simulation results are presented in Figure 5. While solving a problem of this size is computationally challenging, if not impossible, using column generation, the closed-form solution for the optimal value of the approximation parameters allows us to determine the AOP policy easily. The simulation time for such a large instance takes almost 7 h on a 2022 MacBook Pro with an M1 chip.

Figure 5.

Performance of the various booking policies in terms of different metrics for a practical example. (a) Total discounted cost ($), (b) proportion of consults booked late, (c) proportion of demand diverted to overtime, (d) regular-hour capacity utilization, and (e) average wait time for consultation (days).

As can be seen from Figure 5(a), the AOP outperforms all other policies with respect to the total discounted cost, although the performance of the other policies does not exactly match the order observed for the small problem setting. The AOP is able to book all consult appointments within their wait time targets (see Figure 5(b)) and ensures that all the required test results are available before seeing a physician. The second-best policy, in terms of total discounted cost, is still the MSP policy, which is closely followed by the A-PPQ policy. The actual 95% confidence intervals from which Figure 5 is created are available in the E-Companion file.

The main difference between the AOP and the other policies is that it uses slightly more overtime for tests in order to maximize the utilization of regular-hour consultation capacity. Figure 5(c) shows that the overtime usage for the AOP is higher than that for the other policies for tests, and lower for consults, while Figure 5(d) demonstrates that the utilization of regular-hour consultation capacity for the AOP is higher than that for the other policies.

As can be observed in Figure 5(b), the AOP, MSP, and A-PPQ policies all meet the priority-specific wait-time targets, while all the other policies perform poorly, particularly for higher priority patients. Finally, Figure 5(e) shows the dominance of the AOP with respect to minimizing the average wait times for consults. Heuristics 1 and 2, which reflect the current practice at the SPC, offer the longest average wait times for consults across priority levels, especially for the highest priority patients.

6. Conclusion

Prior to this research, there were no scheduling policies in the literature that could be applied to a multi-appointment, multi-priority patient scheduling problem with a precedence relationship between different types of appointments and lead times. This paper offers an array of scheduling policies capable of handling such complexities. The first group of policies is based on two prevalent booking guidelines for a simpler problem, the PPQ and DMB policies, which have been adjusted to suit this specific setting. Our analysis shows that among these policies, the A-PPQ policy provides the best performance. Compared to Heuristics 1 and 2, the A-PPQ performs better with respect to the mean total discounted cost, avoiding late bookings and unnecessary use of overtime. This highlights the benefit of having overtime capacity, as current practice (closely resembling Heuristic 1 ${}^{*}$ and Heuristic 2 ${}^{*}$ ) performs significantly worse.

Using ADP techniques, we have been able to determine an approximate optimal policy which offers several advantages that make it an appealing choice for practitioners. While the policies resembling the current practice fail to provide some test results at the time of physician consultation, the AOP and the MSP heuristic policy derived from characterization of the AOP ensure that all test results are available by the consult date to help the physician make a more informed decision. While above 80% of consult appointments are currently booked later than the priority-specific wait-time targets at the SPC, the proposed appointment scheduling policies ensure wait-time targets are met. This was achieved by a slight use of overtime and a more efficient use of regular time capacity. Compared to alternative policies that work relatively well, such as A-PPQ, A-DMB, and the hybrid policies, the AOP uses a slightly higher amount of overtime for tests and significantly lower overtime for the consult in order to make the best use of regular-hour consultation capacity. As demonstrated in numerical experiments, the performance of the MSP policy closely matches that of the AOP. Beyond its strong overall effectiveness, the MSP policy offers significant practical advantages. Unlike the AOP, it does not require solving an optimization model to determine the best course of action, making it computationally efficient and easily interpretable. Additionally, the MSP policy is highly scalable as it can be applied to scheduling problems of any size without the need for advanced mathematical expertise or expensive computational resources.

While we aimed to model the problem as realistically as possible, some assumptions were inevitable. For instance, in practice, consult appointments can potentially proceed with an incomplete set of test results. We formulated another version of the model where tests were classified into two groups: urgent tests (whose results are required at the time of the consultation) and nonurgent tests (otherwise). However, the results showed that, even when permissible, booking tests late was never optimal.

While some studies that address simpler, more tractable problems have attempted to obtain the optimality gap of the AOP through comparison with optimal solutions determined by solving simplified versions of the problem (Gökalp et al., 2023; Khorasanian et al., 2024), these approaches are not viable for our setting due to computational limitations and dependencies. There are few theoretical performance bounds for ALP, and those that do exist often lack practical value (De Farias and Van Roy, 2003; de Farias and Van Roy, 2006). Rather than computing an optimality gap by solving simplified problem instances, we evaluate the performance of the AOP and MSP policy against best-known benchmark policies and current practice on a large-scale problem tackled in an SPC. This approach enables us to demonstrate the advantages of the proposed policies across a broad range of performance metrics.

While employing an affine value function approximation in the state variables offered us computational advantages and facilitated the use of a commercial solver, this approximation architecture may not be the best choice. Alternative nonlinear approximation architectures, such as in Sauré et al. (2015), have shown promise in terms of performance. Despite this, the present study marks the first attempt to identify an optimal decision policy tailored to a complex patient scheduling context characterized by dependent demand, lead times, and various degrees of heterogeneity among patients and resources.

Supplemental Material

sj-pdf-1-pao-10.1177_10591478251356474 - Supplemental material for Advance Multi-Priority, Multi-Appointment Patient Scheduling With Dependent Demand and Lead Times

Supplemental material, sj-pdf-1-pao-10.1177_10591478251356474 for Advance Multi-Priority, Multi-Appointment Patient Scheduling With Dependent Demand and Lead Times by Shahryar Moradi, Antoine Sauré and Jonathan Patrick in Production and Operations Management