where
T_{i} is the planned time for client
i appointment, as is the standard time for
s, and
𝜎 is variability in service time. The parameters
𝐾 $$
K
,
𝑘1,𝑘2 $$
k
1
,
k
2
are the early breakpoints, delay breakpoints and the multipliers.
(𝑘1/𝑘2 $$
(
k
1
/
k
2
)
) controls the earliness rate imposed on the first
𝐾
patients and the rate of lateness imposed on the remaining patients.
The most prominent finding in the study of variable interval rules is the “dome” rule, including absences and appointments, and patient categorization. The universal appointment rule demonstrate effective performance, independent of the clinical environment
[52]^{[44]}. Optimal scheduling exhibits a dome pattern, whereby appointment intervals begin to grow later in the session and then decrease. Dome mode reduces wait times compared to other scheduling rules
[53]^{[45]}. Considering no-shows and walk-ins, the patient count scheduled to achieve the target T patients served at a session is calculated as follows
[54]^{[46]}.
$$$$
N
=
T
(
1
−
P
n
+
P
w
)
In this formula,
𝑃𝑛 is that a patient fails to attend and
𝑃𝑤 is the probability of coming without an appointment.
The appointment times are determined through a two-step process employing the subsequent formula:
$$$$
A
i
=
m
a
x
{
0
,
k
(
i
−
1
)
μ
−
σ
i
⋅
π
}
f
o
r
i
=
1
,
…
,
N
w
h
e
r
e
π
=
(
N
+
i
)
/
(
N
−
1
)
In this formula,
𝐴𝑖 is the patient
𝑖’s scheduled time, with the mean duration of service
μ, and variability in service time
𝜎. The k controls the appointment intervals for different appointment rules by setting different values.
π is a parameter utilized to establish a pattern resembling a “dome” in the appointment intervals.
$$$$
K
=
f
(
N
,
C
v
,
P
n
,
P
w
,
C
R
)
In Equation (4),
𝐶𝑣 is the coefficient of variation; and CR is the ratio of the cost of the doctor’s time to that of the patients’ time.
Considering the combined impact of no-shows and walk-ins on the consultation durations, the updated formulas for the mean and variance are shown
:
$$$$
μ
′
=
(
1
−
P
n
+
P
w
)
μ
$$$$
σ
′
2
=
(
1
−
P
n
−
P
w
)
(
σ
2
+
(
P
n
−
P
w
)
2
μ
2
+
P
n
(
1
−
P
n
+
P
w
)
2
μ
2
+
P
w
(
2
σ
2
+
(
1
+
P
n
−
P
w
)
2
μ
2
- The “plateau-dome” appointment rule.
Doctors could find advantages in implementing a “plateau-dome” rule with fixed individual blocks evenly distributed in the middle of the appointment session
[55]^{[47]}, explicitly modelling the impact that the doctor’s interruptions may have on optimal appointment times, and thereby affecting waiting times for patients. A traditional pattern for the high number of interrupts and flat dome mode for a low number of interrupts performs better
[56]^{[48]}. This was achieved by conducting an additional run with the supplementary constraint:
$$$$
x
i
−
2
x
i
+
1
+
x
i
+
2
=
0
f
o
r
i
ϵ
[
α
,
β
]
In this formula,
𝑥𝑖 is the appointment time, and
𝛼 and
𝛽 are the appointment slots corresponding to the beginning and end of the plateau portion, respectively.
2.2.2. Patient Classification
Several investigations have explored the implementation of patient classification (PC) based on the assumption that populations can be categorized into distinct groups. For example, in practice, a prevalent method of classifying patients is according to whether they are new or old who have been examined for a different length of time. This allows patients to be sorted at the time of the appointment, and diversity in consultation duration is combined by patient categorization to adjust the length of the appointment interval according to the characteristics of each group. Most studies are only concerned with the scheduling of patients attending elective appointments [57]^{[49]}. Meersman et al. proposed the scheduling horizon involves the time slots for elective and urgent patient categories [58]^{[50]}, considering the slot allocation of non-elective patients.
2.3. AS System Decision Framework
In AS system design and planning, a range of decisions and planning determine the main structure of the optimization research system. They can be categorized into three types which are strategic, tactical and operational
[18]^{[51]}. Strategic decisions are the keys in shaping the modeling process and determining the practical applicability of the proposed solutions. Such decisions are usually considered as inputs to the AS system. Tactical decisions aim at determining the system structure. While operational decisions rely on the first two to develop optimization models and rules.
2.3.1. Strategic Decisions
Strategic decisions are considered as inputs and are long-term decisions that determine the main structure of the AS system. Robinson et al.
[61]^{[52]} proposed three main types of access strategies for scheduled patients: traditional, open access, and hybrid. Traditional policies mean all capacity is allocated to pre-scheduled patients, which results in higher no-show rates and longer wait times.
Walk-in patients refer to patients who go to the clinic without an appointment during the consultation period. Accepting appointments is a means of mitigating the negative impact of no-shows while increasing modeling complexity due to the dynamic random arrival of non-appointment patients
[65]^{[53]}. Appointment scheduling methods are categorized into online and offline
[66]^{[54]}. In the offline method, arranged once all requests have been received, whereas in the online method, patients are promptly scheduled after requests arrive.
2.3.2. Tactical Decisions
The primary purpose of approaching the decision problem at the tactical level is to characterize the system to optimize resource utilization and the integrity of the consultation service. For example, in allocating capacity among various groups, the decision should consider factors such as the needs of each patient group, prioritization, probability of absence, revenue per patient group, and patient and physician preferences
[68]^{[55]}, which affect the absence rate and hence the system efficiency. A decrease in the scheduling window results in a reduction of indirect wait time, consequently leading to decrease the absence rate. This enables a more effective use of the clinic’s capacity. Excessive constraints on scheduling windows may result in a reduced patient count, leading to a decline in clinic revenue
[69]^{[56]}. Issues such as appointment intervals (slots), block size, panel size, etc., are essentially capacity allocation issues as well, affecting tactical-level decisions
[70,71,72]^{[57][58][59]}.
2.3.3. Operational Decisions
Operational decisions are associated with plans at the individual-patient level. Rule-based approaches (RBA) and optimization-based approaches (OBA) are used to determine these decisions
[68]^{[55]}. RBA refers to a set of instructions having associated rules and parameters, but it does not guarantee the realization of optimal performance compared to OBA. Whereas OBA specifies the level of operational decisions, its goal is to attain globally optimal answers for operational decisions
[73]^{[60]}.
3. Optimization Framework
3.1. Optimization Objective
3.1.1. Societal Benefit
Many studies in the literature on AS have been devoted to minimizing pathway completion time or maximizing patient satisfaction, which leads to better societal benefits and is the primary goal that hospital management needs to follow. The key performance indicators for minimizing the time to complete all tasks include the average waiting time of patients (WAIT), the average idle time of physicians (IDLE) and the average overtime of physicians (OVER).
Dharmadhikari et al.
[79]^{[61]} used performance metrics of average rewards per patient to assess the effectiveness of the proposed block scheduling strategy with prioritization. Cordier et al.
[80]^{[62]} developed algorithmic tools to construct one-day schedules and optimize these schedules to optimize the length of patient stay. Nazanin et al.
[81]^{[63]} conducted case studies for different healthcare settings and selected the most effective scheduling model that fits the case in terms of the balance between three types of metrics related to patient appointment scheduling systems: patient satisfaction, scheduler utilization, and scheduling system cost. Accessibility was a factor of patient satisfaction, measured by the average waiting time before connecting to the dispatch program and the average duration of call.
3.1.2. Economic Performance
The appointment scheduling system is a potentially useful tool for reducing health management costs and maximizing medical benefits. Improving system reliability and cost savings are the main ideas of optimization
[101,102,103,104]^{[64][65][66][67]}. Profit maximization is becoming a major research objective due to the need for cost efficiency and facing budget cuts. Some hospitals maximize profits by rising the number of patients scheduled and maximizing contribution margins. El-Sharo et al.
[83]^{[68]} modeled an overbooking scheduling model for multi-provider practices to optimize patient overbooking and maximize expected profits.
3.1.3. Resource Utilization
With limited healthcare resources, clinics are under tremendous pressure to the increasing demand. Therefore, rational capacity allocation is one of the main goals of AS. Previous papers on outpatient capacity assignment can be divided into two broad categories. One category is where the overall capacity is a constant, the hospital must assign limited medical capacity to various types of patients. For instance, Nguyen et al.
[91]^{[69]} presented a mixed-integer planning model with the aim of minimizing the maximum demand capacity to plan the demand of outpatient physicians to achieve the service goal of patient appointment lead time. The other category, where the capacity is a variable that needs to be solved in conjunction with the allocation scheduling problem, is categorized into static and dynamic cases. The former means that the decision is made before the session, e.g., Zeng et al.
[92]^{[70]} investigated the appointment booking problem for heterogeneous patients. The features of optimal scheduling with heterogeneous patients are determined, and a method of local search algorithm is proposed to for finding the locally optimized scheduling. The latter means that appointments are made sequentially, and when a patient calls in, capacity allocation is conducted online, and the hospital needs to decide how much capacity is available for each time slot.
3.1.4. Other Objectives
In general, the literature on optimization studies of AS systems covers many aspects, as well as the optimization of objectives through other aspects to obtain better social and economic effects.
Savelsbergh et al.
[98]^{[71]} investigated methods based on optimization and cohorts to SA for patients in a chronic disease management program. The objective was to minimize the overall probability of a patient entering an uncontrolled health state. The approach considers transitions in disease control since the last appointment time and the probability of the patient not attending the appointment. Ozen et al.
[72]^{[59]} used the probability of demand exceeding capacity as a measure of access capacity. Formulating the problem of minimizing the maximum overflow of a multi-medicine practitioner clinic as a non-linear integration programming problem describes how the frequency of overflow varies from physician to physician and demonstrates how these supply and demand imbalances can be minimized in the long run using real-world data from primary care practices.
3.2. Decision Variable
About the optimizing appointment scheduling’s study, the decision variables for optimization show the strategy and actions taken to enhance the objectives
[105]^{[72]}. Appointment time is one of the common decision variables in the AS problem. Tito et al.
[106]^{[73]} considered whether patient absence was affected by appointment time using arrival time as the decision variable and investigates a stochastic optimization problem with a random distribution of service times and patient decision-dependent no-show behavior. Solutions are given for different patterns of absenteeism behavior, and it is shown that disrupting the hypothesis of a fixed probability of attendance greatly alters the scheduling scheme.
3.3. Constraints
Various optimization decisions about appointment scheduling systems will have different constraints. Optimization studies of ASs are often inseparable from the optimization of operational costs as well as time from the perspective of economic or social benefits
[110]^{[74]}. Considering the minimum cost of AS operation and the minimum waiting time or the minimum physician overtime time, the constraints consist of appointment sequence, resource capacity, time constraints, etc.
4. Optimization Algorithms
Numerous studies have been undertaken to determine the optimal allocation of AS systems to reduce operational and time costs, improve patient satisfaction and system reliability dependability. Various algorithms are applied to the optimization of AS systems, with genetic algorithms (GAs) being the most utilized. For instance, Braune et al.
[112]^{[75]} proposed a combination of GAs and Monte Carlo simulation to heuristically solve a stochastic optimization model developed for planning the appointment times of healthcare units under uncertain activity durations, allowing to minimize the waiting time of patients while maximizing the use of resources. Fan et al.
[113]^{[76]} considered patient preferences for highly qualified general practitioners and specialist doctors. By analyzing real data from hospital outpatient clinics, a behavioral pattern was derived in which the patient’s tolerance limit adapted to the expected waiting time. A simulation optimization framework for maximizing clinic benefits and minimizing patient dissatisfaction is proposed. Utilizing multi-objective optimization and a genetic algorithm, a simulation budget allocation approach is integrated to derive an approximate Pareto scheme for joint capacity planning and patient scheduling across multiple servers.
In addition, the key to the appointment dilemma is the challenge of solving the multi-objective optimization problem; therefore, many decisions need to be made using a multi-objective evolutionary algorithm. Mohammad et al.
[115]^{[77]} improved the quality of operational efficiency and healthcare quality by writing a MOPSO algorithm and introducing a MO-PASS architecture. Ali et al.
[116]^{[78]} investigated a multi-criteria approach in appointment scheduling by WOA. optimization for hospital management quality and patient satisfaction.
There are some other methods to solve this problem. Garaix et al.
[118]^{[79]} proposed a heuristic to calculate the order in which patients receive treatment at outpatient chemotherapy centers called the GRASP algorithm. It optimizes the facility’s closing time and overtime working time. It can reach near-optimal solutions quickly and the performance of the patient-listing strategy is comparable to more complex scheduling strategies.
4.1. Genetic Algorithm
Genetic algorithms (GAs) offer an efficient approach to optimizing complex systems. Previous research indicates that many scholars have employed GAs to address optimization problems in the scheduling fields. For example, Squires et al.
[124]^{[80]} proposed a new genetic algorithm designed for scheduling repetitive transcranial magnetic stimulation (rTMS) appointments. The mentioned algorithm (LSWT-GA) combines a novel survivor selection strategy with heuristic population initialization. The objective of the algorithm is to enhance the operational efficiency of medical centers by optimizing the scheduling of repetitive transcranial magnetic stimulation (rTMS) appointments.
4.1.1. Objective Function and Constraint
The primary goal of the initial aim in the experiment is to minimize the job processing time expressed as
𝐶max and aim to minimize weighted flowtime
𝐹𝑤 secondly. The problem can be under the category of minimizing make span in a parallel machine scenario, where job processing times are deterministic, and preemption is not allowed.
$$$$
P
∥
C
m
a
x
P
∥
F
w
$$$$
min
C
m
a
x
$$$$
F
w
=
∑
j
=
1
x
w
j
F
j
$$$$
min
F
w
where
$$$$
F
j
=
C
j
−
r
j
In this formula,
𝑃 is a group of patients waiting for a treatment,
𝐹𝑗 denotes the flowtime of patient
𝑃𝑗;
𝐶𝑗 is the time to finish the treatment for
𝑃𝑗 and
𝑟𝑗
is the release time of the job.
4.1.2. Optimization Process
Th
ise study presents the new genetic algorithm used. Drawing inspiration from evolution, the genetic algorithm relies on natural selection to choose the most suitable chromosomes, as determined by a fitness function, for the reproduction phase of the genetic algorithm.
Figure 2 illustrates the flowchart of the optimization algorithm.
Figure 2. Flowchart of genetic algorithm modules.
4.2. Whale Optimization Algorithm
The WOA algorithm is a meta-heuristic algorithm designed with both subtlety and character, which is derived from simulating the hunting behavior of humpback whale groups in nature and realizes the purpose of optimizing search through the process of searching, pursuing, and attacking prey by the whale group. The WOA literature has been widely used in solving various of optimization problems, and Ali et al.
[116]^{[78]} explores the multi-criteria in AS were analyzed using both algorithms, WOA and NSGA techniques. They are computed using various assumptions to meet the requirements and aspects associated with WOA and NSGA.
4.2.1. Optimization Model
Scheduling and counseling patients for scheduling to the hospital is the issue discussed. Each hospital section has a varying number of operators to handle distinct operations. Moreover, each capable of providing specific services. In this system, there are n patients, categorized as either emergency or general patients. There are several surgeries for each patient that must be performed in different departments. In addition to this, it may diagnose a patient as an emergency at the time of planning. Emergency patients are usually visited earlier than general patients and are given precedence (fairness). After doing something such as seeing a doctor, the diagnosis depending on the patient’s condition, in which case the patient is referred to an inpatient unit with limited beds.
4.2.2. Objective Function
The objective function is to minimize the average total weighted patient time and to reduce dissatisfaction because of increased waiting time for patients.
$$$$
min
c
w
=
1
∑
i
=
1
n
w
i
∑
i
=
1
n
(
w
i
.
C
N
i
)
$$$$
min
Z
=
ρ
∑
i
=
1
n
(
C
N
i
−
r
i
)
4.2.3. Constraint
Examination or processing of each patient’s procedure is exclusive in one location on one ward, as shown in the formula below. And for the restriction in a sequencing assured to prevent patients from being assigned to a segment of the surgery when another area is empty, as shown in the Formulas (33) and (34).
$$$$
∑
m
=
1
M
∑
l
=
2
L
x
i
j
l
m
=
1
,
j
=
1
,
…
,
h
i
,
i
=
1
,
…
,
n
,
$$$$
∑
i
=
1
n
∑
j
=
1
h
i
x
i
j
l
m
≤
∑
i
=
1
n
∑
j
=
1
h
i
x
i
j
(
l
−
1
)
m
,
m
=
1
,
…
,
M
,
l
=
3
,
…
,
L
,
where
x is the Appointment System Decision Variables and is equivalent to 1 if the action
𝑂𝑖𝑗 is performed in section
𝑚𝑡ℎ at position
𝑖𝑡ℎ
. It is also important to consider the indexes used for appointments, appointment durations, association variables, etc.
4.2.4. Model Solving
Th
ise study solves the model by introducing a local search operator to optimize the solution, using the stochastic WOA nature of the meta-heuristic algorithm. The WOA begins with stochastic solutions. Depending on each search factor, the search agent arbitrarily changes according to the optimal solution. The position of the task agent can be updated through two methods. If
|A| > 1, a random search agent is chosen; otherwise, the optimal solution is selected. The whale can transition between two types of motions, either spiral or rotational, depending on the
p-value. Eventually, the algorithm concludes when it attains a predefined satisfaction criterion, where
x* represents the best solution, as shown in
Figure 3.
Figure 3. Proposed flowchart for the whale optimization algorithm.
4.3. Tabu Search Algorithm
4.3.1. The Integer Programming Model in a Definitive Model
The optimization objective is reducing waiting periods and the cost of completion times to a minimum. Every patient went through three phases of initial admission and surgery and recovery phases of surgery.
where Proposed flowchart for the whale optimization algorithm.
4.3. Tabu Search Algorithm
4.3.1. The Integer Programming Model in a Definitive Model
The optimization objective is reducing waiting periods and the cost of completion times to a minimum. Every patient went through three phases of initial admission and surgery and recovery phases of surgery.
$$$$
min
∑
j
∑
t
∑
p
γ
p
q
j
,
t
,
p
+
β
m
𝑞𝛾 is the resource capacity content, and
𝛽 denotes the patient visit or procedure completion time. Meanwhile, patient queue balance as well as resource capacity versus the number of patients to be served are constraints of the appointment system.
4.3.2. Algorithm Optimal Progress
The random solution called at the beginning of the algorithm is 𝑥0
. And the best-found neighbor solution, . And the best-found neighbor solution,
𝑥′
, is named as a pivot. Tabu tenure comes into play to navigate away from local optima throughout the search process. An iterative update of the list is implemented to enable the algorithm to adapt to the status of the search. This methodology ensures the comprehensive exploration of the entire solution space while simultaneously addressing the objectives of intensification and diversification. Additionally, in specific instances, the aspiration criterion is applied to supersede the Tabu list. , is named as a pivot. Tabu tenure comes into play to navigate away from local optima throughout the search process. An iterative update of the list is implemented to enable the algorithm to adapt to the status of the search. This methodology ensures the comprehensive exploration of the entire solution space while simultaneously addressing the objectives of intensification and diversification. Additionally, in specific instances, the aspiration criterion is applied to supersede the Tabu list.
Figure 4 illustrates the proposed TS algorithm, where X* represents the best solution.
Figure 4. The flowchart of the Tabu search algorithm.
The term of Tabu was determined from some preliminary experiments. The taboo retention period specified the upper limit for the number of iterations. The maximum computation time is set as the criterion for terminating the algorithm when no improvement is observed within the specified number of iterations. The second method uses integer programming with stochastic models, which are executed separately and then compared.
4.4. Other Heuristic Algorithm
4.4.1. Problem Description
A heuristic optimization algorithm is an intuitively or empirically constructed algorithm that provides a viable solution for the combinatorial optimization problem at an acceptable cost, considering computational time and space constraints. This means that the heuristic algorithm solves the problem empirically or according to some rules, and the solution to the problem is not necessarily optimal but is likely to be approximate (or near optimal). Akbarzadeh et al.
[124]^{[80]} proposed a three-phase heuristic algorithm for constructing high-quality feasible solutions using column generation, which is further improved by local branching. The surgical case replanning and scheduling problem with resource rescheduling is investigated in the presence of a chunk release time when the OR planners aim to achieve equilibrium between the capacity and demand for operating rooms. The following equation involves four components that reflect the benefits, resulting in weighted sums of various metrics.
$$$$
M
i
n
ω
=
−
α
∑
i
d
j
w
i
d
×
A
P
i
d
j
×
x
j
α
M
a
x
+
β
∑
i
W
T
i
β
m
a
x
+
γ
N
u
r
R
e
γ
m
a
x
+
δ
S
u
r
R
e
δ
m
a
x
where the initial component compels the model to allocate surgical cases to an appropriate day. Following this, the second component seeks to minimize waiting time. Subsequently, the next component aims to minimize the overall nurse rescheduling cost. Finally, the last component focuses on minimizing the deviation of the surgeon’s schedule from the Master Surgery Schedule (MSS). The weights assigned to these different objective functions are relative and collectively sum to 1, i.e.,
α + β + γ + δ = 1.
4.4.2. Constraint
There needs to be a requirement for nurses to perform only one procedure at a time, and to assign procedures to nurses only if they have been assigned a shift. In fact, a surgeon is restricted to one operating room at any given time, and each surgery is limited to being conducted only once.
$$$$
∑
j
N
T
n
t
d
j
×
x
j
≤
∑
v
n
x
n
v
d
$$$$
∑
r
j
S
X
s
b
r
d
j
×
x
j
≤
1
$$$$
∑
d
j
A
P
i
d
j
×
x
j
=
P
X
i
In Equation (
3719),
𝑁𝑇𝑛𝑡𝑑𝑗 denotes the case where nurse n received the task for schedule
𝑗 at time
t on day
𝑑,
𝑥𝑗 indicates whether the scheduling is accepted or not,
𝑛𝑥𝑛𝑣𝑑 indicates whether nurse
n worked on shift
𝑣 on day
𝑗;
𝑆𝑋𝑠𝑏𝑟𝑑𝑗 denotes whether surgeon s is assigned to the
r-room
b area on day d of program
𝑗;
𝐴𝑃𝑖𝑑𝑗 denotes if surgical case
i is included in schedule
𝑗, day
𝑑; and
𝑃𝑋𝑖 is the decision variable implies that the surgery is performed within the time frame under consideration.
4.4.3. Solution Methodology
The solution procedure named Column Generation and Local Branching Heuristic (CLH) is proposed to address the integrated problem.
Figure 5 provides an overview for the solution procedure, consisting of three distinct steps. Firstly, the CLH algorithm employs a computationally feasible column generation procedure to address the impracticality of generating all possible OR schedules directly. If the solution is an integer, it is optimal; otherwise, transforming fractional solutions into feasible integer solutions offers an upper bound on the optimal solution. If the upper bound matches the lower, the optimal solution is identified. If not, the optimal upper bound is used as input for an improvement step, using local branches to narrow the optimality gap.
Figure 5. Summary of the Column Generation and Local Branching Heuristic.