A hybrid imperialist competitive algorithm for the outpatient scheduling problem with switching and preparation times

Abstract

During recent years, the outpatient scheduling problem has attracted much attention from both academic and medical fields. This paper considers the outpatient scheduling problem as an extension of the flexible job shop scheduling problem (FJSP), where each patient is considered as one job. Two realistic constraints, i.e., switching and preparation times of patients are considered simultaneously. To solve the outpatient scheduling problem, a hybrid imperialist competitive algorithm (HICA) is proposed. In the proposed algorithm, first, the mutation strategy with different mutation probabilities is utilized to generate feasible and efficient solutions. Then, the diversified assimilation strategy is developed. The enhanced global search heuristic, which includes the simulated annealing (SA) algorithm and estimation of distribution algorithm (EDA), is adopted in the assimilation strategy to improve the global search ability of the algorithm.?Moreover, four kinds of neighborhood search strategies are introduced to?generate new?promising?solutions.?Finally, the empires invasion strategy?is?proposed to?increase the diversity of the population. To verify the performance of the proposed HICA, four efficient algorithms, including imperialist competitive algorithm, improved genetic algorithm, EDA, and modified artificial immune algorithm, are selected for detailed comparisons. The simulation results confirm that the proposed algorithm can solve the outpatient scheduling problem with high efficiency.

Keywords

Flexible job shop scheduling outpatient scheduling hybrid imperialist competitive algorithm neighborhood search strategies

1 Introduction

Hospitals are critical elements of health care systems and access to their services is very competitive around the world. As the core department of the hospital, outpatient service is considered as the “facade” of the hospitals, accounting for a large proportion of hospitals’ expenditures and profitability. Outpatient service, however, is very challenging due to its conflicted preferences and priorities from many stakeholders and limited resources to meet the needs. In response, scheduling is introduced to optimize outpatient visits [1].

Scheduling problems have been investigated in recent years and have been utilized in many practical problems. One of the most difficult problems in this area is the job shop scheduling problem (JSP). However, a type of classical JSP that is similar to a real-world manufacturing situation is called the FJSP [2]. There are lots of meta-heuristic algorithms which have been proposed to solve the FJSP, such as the genetic algorithm (GA) presented by Chen et al. [3] which can find the global optimal solution of the optimization problem. The imperialist competitive algorithm (ICA) proposed by Atashpaz-Gargari [4] with fast convergence speed, high convergence accuracy and strong global convergence. The particle swarm optimization algorithm investigated by Boukef et al. [5] with strong robustness. Luo et al. [6] presented the multi-objective grey wolf optimization algorithm with strong convergence performance, few parameters and easy to implement. Furthermore, Li et al. [7] studied an improved multi-objective algorithm for realistic distributed scheduling problems to minimize two objectives. Du et al. [8] proposed a hybrid estimation of distribution algorithm for distributed FJSP where makespan and total energy consumption are considered as objectives. Cao et al. [9] presented a knowledge-based cuckoo search algorithm to the FJSP with a mating operation, in which a reinforcement learning algorithm with self-adjusting parameters is used to solve the problem of parameter selection.

In recent years, much attention has been paid to the outpatient scheduling problem. Zhu et al. [10] transformed the designated bidding method into a group role assignment problem to solve the outpatient scheduling problem. By analyzing some scenarios that study the tradeoff between patient-related measures and doctor-related measures or system-related measures, a Markov decision model is proposed to determine the optimal outpatient scheduling problem [11]. Geng and Xie [12] proposed a finite-horizon Markov decision process model for optimal outpatients scheduling by considering their waiting time target, i.e., the maximal waiting time the patient can endure. Creps and Lotf [13] proposed a dynamic approach for outpatient scheduling where patients are expected to have multiple appointments, such as physical therapy, occupational therapy, primary care, and dentistry. Deceuninck et al. [14] studied outpatient scheduling with unpunctual patients and no-shows and introduced a numerical methodology for the evaluation of outpatient schedules to obtain accurate performance predictions at a low computational cost. Sun et al. [15] established the optimal appointment schedule in outpatient-inpatient hospital system to minimize the total cost of outpatient waiting time, radiology equipment idle time, day shift staff overtime, and the number of inpatient exam cancellations during the day shift. Li et al. [16] propose an integrated optimization approach for patient-centered outpatient scheduling to improve patient satisfaction.

From previous studies, it can be found that outpatient scheduling has been studied extensively, but most of the studies are general and consider the outpatient scheduling process as a whole. Therefore, it is not suitable for practical application. This study systematically analyzed the whole process of outpatient scheduling problem, including the selection of medical resources at each stage and the time consumption between different stages, so as to make effective outpatient scheduling in advance. During the novel Coronavirus epidemic period, effective outpatient scheduling can promote hospital personnel mobility, reduce potential risks and promote the effective use of resources.

Keeping the above consideration in mind, this study proposes a hybrid ICA, named HICA, to solve the outpatient scheduling problem with switching and preparation times. Our main contributions are as follows: (1) the mutation strategy with different mutation probabilities is utilized to generate feasible and efficient solutions; (2) the diversified assimilation strategy is developed; (3) the enhanced global search heuristic, which includes the simulated annealing (SA) algorithm and estimation of distribution algorithm (EDA), is adopted in the assimilation strategy to improve the global search ability of the algorithm;(4) four kinds of neighborhood search strategies are introduced to generate new promising solutions; and (5) the empires invasion strategy is proposed to increase the diversity of the population.

The rest of the paper is organized as follows. The problem formulation is described in Section 2. Then, Section 3 describes the proposed algorithm with all of the components. The simulation tests and analysis are presented in Section 4. Finally, Section 5 gives the conclusions and future research directions.

2 Problem description

2.1 Problem description

Considering a realistic process in a typical outpatient scheduling system, as shown in Fig. 1, the patient is generally considered as scheduling unit. The process considers different stages, including registration, consultation room, and so on. Each patient has its own route dynamically assigned according to the current medical device state; that is, the route differs for different patients. In each stage, each patient selects one medical resource from the candidate medical resource set; medical resource selection is thus flexible. Based on the above analysis of the outpatient scheduling problem, we can model this scheduling as an FJSP, in which the patients are treated as jobs.

Fig. 1

Outpatient scheduling process.

There are a set of patients J ={ J₁, …, J_n } and a set of medical resources M ={ M₁, …, M_m }. Each independent patient J_j contains n_j stages of seeking medical treatment O_j,q, where q = 1, …, n_j. Each stage can be processed by a set of medical resources in a certain sequence. Then, the two realistic constraints, i.e., the switching and preparation times of patients are considered. Furthermore, considering the time it takes for the patient to arrive at the first medical resource, a dummy medical resource with zero processing time, say medical resource 0, is defined.

The assumptions in this study are described as follows:

All patients are ready at time zero.

Each patient has a given number of stages of seeking medical treatment.

Each stage of seeking medical treatment can only be processed by an available medical resource.

Pre-emption is not feasible, which means each stage of seeking medical treatment must be fulfilled without interruption as soon as it initiates.

All the stages of seeking medical treatment belonging to the same patient should be processed one after another in a fixed order.

The status of medical resources is known before scheduling begins.

The switching and preparation times of patients are considered.

2.2 Mathematical modeling

The notations used in this section are described in Table 1. The position-based mathematical model which considers the position of the patient on the medical resource is developed. The objective is to minimize the makespan of the outpatient scheduling. Therefore, the objective function can be expressed as: $min C_{\max}$ (1) $\sum_{i = 1}^{m} \sum_{f = 1}^{R_{i}} X_{j, 1, i, f, 0} = 1 \forall j \in {1, 2, \dots, n}$ (2) $\sum_{i = 1}^{m} \sum_{f = 1}^{R_{i}} \sum_{k = 1}^{m} X_{j, q, i, f, k} = 1 \forall j \in {1, 2, \dots, n}, q \in {2, \dots, n_{j}}$ (3) $\sum_{j = 1}^{n} \sum_{q = 2}^{n_{j}} \sum_{k = 1}^{m} X_{j, q, i, f, k} + \sum_{j = 1}^{n} X_{j, 1, i, f, 0} \leq 1 \forall i \in {1, 2, \dots, m}, f \in R_{i}$ (4) $\sum_{f = 1}^{R_{i}} \sum_{k = 1}^{m} X_{j, q, i, f, k} \leq E_{j, q, i} \forall j \in {1, 2, \dots, n}, q \in {2, \dots, n_{j}}, i \in {1, 2, \dots, m}$ (5) $\sum_{f = 1}^{R_{i}} X_{j, 1, i, f, 0} \leq E_{j, 1, i} \forall j \in {1, 2, \dots, n}, i \in {1, 2, \dots, m}$ (6) $\sum_{f = 1}^{R_{i}} X_{j, q, i, f, k} \leq \sum_{f = 1}^{R_{k}} \sum_{t = 1}^{m} X_{j, q - 1, k, f, t} \forall j \in {1, 2, \dots, n}, q \in {2, \dots, n_{j}}, i, k \in {1, 2, \dots, m}$ (7) $\sum_{f = 1}^{R_{i}} X_{j, 2, i, f, k} \leq \sum_{f = 1}^{R_{k}} X_{j, 1, k, f, 0} \forall j \in {1, 2, \dots, n}, i, k \in {1, 2, \dots, m}$ (8) $C_{j, q} \geq C_{j, q - 1} + \sum_{i = 1}^{m} \sum_{f = 1}^{R_{i}} \sum_{k = 1}^{m} X_{j, q, i, f, k} (P_{j, q, i} + \sum_{u = 1}^{n} W_{j, k, i} \cdot S_{j, k, i} + p r_{i, j}) \forall j \in {1, 2, \dots, n}, q \in {2, \dots, n_{j}}$ (9) $C_{j, 1} \geq \sum_{i = 1}^{m} \sum_{f = 1}^{R_{i}} X_{j, 1, i, f, 0} (P_{j, 1, i} + \sum_{u = 1}^{n} W_{j, k, i} \cdot (T_{j, 0, i} + p r_{i, j}) \forall j \in {1, 2, \dots, n}$ (10) $C_{j, q} \geq C_{u, g} + P_{j, q, i} - M \cdot (3 - \sum_{k = 1}^{m} X_{j, q, i, f, k} - \sum_{s = 1}^{f - 1} \sum_{k = 1}^{m} X_{u, g, i, s, k} - W_{j, k, i}) \forall j, u \in {1, 2, \dots, n}, j \neq u, i \in {1, 2, \dots, m}, q \in {2, \dots, n_{j}}, f \in R_{i} > 1$ (11) $C_{j, 1} \geq C_{u, 1} + P_{j, 1, i} - M \cdot (3 - \sum_{k = 1}^{m} X_{j, 1, i, f, 0} - \sum_{s = 1}^{f - 1} X_{u, g, i, s, k} - W_{j, k, i}) \forall j, u \in {1, 2, \dots, n}, q \in {2, \dots, n}, j \neq u, i \in {1, 2, \dots, m}, f \in R_{i} > 1$ (12) $C_{j, q} \geq C_{u, 1} + P_{j, q, i} - M \cdot (3 - \sum_{k = 1}^{m} X_{j, q, i, f, k} - \sum_{s = 1}^{f - 1} X_{u, 1, i, s, k} - W_{j, k, i}) \forall j, u \in {1, 2, \dots, n}, q \in {2, \dots, n_{j}}, j \neq u, i \in {1, 2, \dots, m}, f \in R_{i} > 1$ (13) $C_{j, 1} \geq C_{u, g} + P_{j, 1, i} - M \cdot (3 - \sum_{s = 1}^{f - 1} X_{u, g, i, s, k} - X_{j, 1, i, f, 0} - W_{j, k, i}) \forall j, u \in {1, 2, \dots, n}, j \neq u, i \in {1, 2, \dots, m}, f \in R_{i} > 1$ (14) $C_{u, g} \geq C_{j, q} + P_{u, g, i} - M \cdot (2 - \sum_{s = 1}^{f - 1} \sum_{k = 1}^{m} X_{u, g, i, s, k} - \sum_{k = 1}^{m} X_{j, q, i, f, k} - W_{j, k, i}) \forall j, u \in {1, 2, \dots, n}, j \neq u, q, g \in {2, \dots, n_{j}}, f \in R_{i} > 1, i \in {1, 2, \dots, m}$ (15) $C_{u, g} \geq C_{j, 1} + P_{u, g, i} - M \cdot (2 - \sum_{s = 1}^{f - 1} \sum_{k = 1}^{m} X_{u, g, i, s, k} - X_{j, 1, i, f, 0} - W_{j, k, i}) \forall j, u \in {1, 2, \dots, n}, j \neq u, g \in {2, \dots, n_{j}}, i \in {1, 2, \dots, m}, f \in R_{i} > 1$ (16) $C_{u, 1} \geq C_{j, q} + P_{u, 1, i} - M \cdot (2 - \sum_{k = 1}^{m} X_{j, q, i, f, k} - \sum_{s = 1}^{f - 1} X_{u, 1, i, s, 0} - W_{j, k, i}) \forall j, u \in {1, 2, \dots, n}, q \in {2, \dots, n_{j}}, i \in {1, 2, \dots, m}, f \in R_{i} > 1$ (17) $C_{u, 1} \geq C_{j, 1} + P_{u, 1, i} - M \cdot (2 - \sum_{s = 1}^{f - 1} X_{u, 1, i, s, 0} - X_{j, 1, i, f, 0} - W_{j, k, i}) \forall j, u \in {1, 2, \dots, n}, q \in {2, \dots, n_{j}}$ (18) $C_{max} \geq C_{j, n_{j}} \forall j \in {1, 2, \dots, n}$ (19) $X_{j, q, i, f, k}, W_{j, k, i} \in {0, 1}$ (20)

Table 1

Notations definition

Notations	Comment
j, u	Indices of patients.
i, k, t	Indices of medical resources.
f, s	Indices of positions.
q, g	Indices for the stage of seeking medical treatment.
n	Number of patients.
m	Number of medical resources.
n _j	The total number of stages in the process of seeking medical treatment of patient j.
O _j,q	q^th stage of seeking medical treatment of patient j.
P _j,q,i	Processing time of O_j,q by medical resource i.
S _j,k,i	Switching time of patient j from medical resource k to medical resource i.
Pr _i,j	Preparation time of the patient j on medical resource i.
R _i	Number of stages that can be processed by medical resource i.
M	A large positive number.
C _j,q	Completion time of O_j,q.
E _j,q,i	Binary variable taking value 1 if O_j,q is eligible to be processed by medical resource i, and 0 otherwise.
W _j,k,i	Binary variable taking value 1 if patient j needs switching time from medical resource k to medical resource i, and 0 otherwise.
X _j,q,i,f,k	Binary variable taking value 1 if O_j,q is processed in position f of medical resource i after the processing of patient j by medical resource k, and 0 otherwise.

The objective function is to minimize the makespan. Constraint (2) represents that the first stage of every patient is exactly assigned to one position of one available medical resource. Constraint (3) guarantees that every stage (except the first stage) should be allocated to only one position of one medical resource among all of the available medical resource. Constraint (4) guarantees that each position of each medical resource is occupied once. Constraint (5) enforces that every stage (except the first stage) of seeking medical treatment of each patient should be processed on the feasible medical resources. Constraint (6) enforces that the first stage of seeking medical treatment of each patient should be processed on the feasible medical resources. Constraints (7) and (8) guarantee that O_j,q-1 is processed by medical resource k when O_j,q is processed by medical resource i. Constraints (9) and (10) are logical precedence constraints that take into account the switching and preparation times of patients. The completion time of the latter stage is greater than or equal to the completion time of the previous stage of the same patient. While ensuring that each medical resource deals with only one stage of patient at a time, constraints (11)-(18) describe that the completion time of the later stage is greater than or equal to the completion time of the previous stage of the same resource. Constraint (19) defines the makespan, and constraint (20) defines the values of the decision variables.

3 Proposed algorithm

3.1 Framework of HICA

To solve the outpatient scheduling problem in hospital systems, we propose a hybrid ICA, named HICA. The HICA is based on the ICA. ICA consists of mutation, assimilation, imperialist competition, and so on. The main features of the HICA are as follows: (1) the mutation strategy with different mutation probabilities is utilized to generate feasible and efficient solutions, which is described in Section 3.4; (2) the diversified assimilation strategy is adopted, which is described in Section 3.5; (3) the enhanced global search heuristic, which includes the SA algorithm and EDA, is developed in the assimilation strategy to improve the global search ability of the algorithm, which is presented in Section 3.6; and (4) the empires invasion strategy?is?proposed to?increase the diversity of the population, which is presented in Section 3.9. The framework of the HICA is shown in Algorithm 1.

Algorithm 1 HICA

1: Generate initial population

2: Construct the initial empires, select Nim best individuals from population as imperialists

3: while the stopping criterion is not met do

4: for x =1 to Nim do

5: Conduct the mutation strategy with different mutation probabilities (c.f. Section 3.4)

6: Perform the diversified assimilation strategy (c.f. Algorithm 2)

7: The enhanced global search heuristic is used (c.f. Section 3.6)

8: Update the empires (c.f. Section 3.8)

9: Execute the empires invasion strategy (c.f. Section 3.9)

10: end for

11: end while

3.2 Encoding scheme

Encoding explains how to represent a real solution. In this paper, we use the encoding scheme proposed by Zhang et al. [17]. The solution consists of two parts: medical resource selection (MRS) and the treatment stage sequence (TSS), as illustrated in Fig. 2. The MRS part stores the available medical resource number, while the TSS part contains the patient number. Moreover, in the MRS part, the local selection was adopted. In the TSS part, the sequence of all the stages is randomly determined.

Fig. 2

Representation of a solution.

3.3 Initialization of empires

In the HICA, countries with better fitness values are imperialists and others are the colonies of these imperialists. The population size (Pop) includes several imperialists (Nim) and their colonies (Ncl), that is an empire includes an imperialist and its colonies. The number of colonies in each empire is expressed as NCx, where x =1, 2,..., Nim. $Pop = Nim + Ncl$ (21)

The roulette wheel selection procedure is used to calculate the power of each imperialist as $power (x) = \frac{1}{makespan (x)}$ (22) After the calculation of the power of the imperialists, we normalize them as follows $colnum (x) = Ncl \cdot \frac{power (x)}{\sum_{n = 1}^{Nim} power (x)}$ (23) where colnum (x) is the probability of assigning each colony to the x^th imperialist.

3.4 Mutation strategy

Mutation is a strategy adopted by imperialists to reduce duplication and increase diversity of solutions. Through many experiments, it could be found that the higher the fitness, the better the solution can be obtained by mutation. Therefore, the probability formula of mutation is described as follows: $η = {\begin{matrix} 1 & F \leq F_{avg} \\ 1 - \frac{F - F_{avg}}{2 (F_{avg} - F_{min})} & F > F_{avg} \end{matrix}$ (24) where η is the individual’s mutation probability, F is the individual’s fitness, F_avg is the average individual’s fitness, and F_min is the worst individual’s fitness. Better individual fitness increases the mutation probability of the individual, enlarges the search space of the individual, and avoids falling into a locally optimal solution. Worse individual fitness reduces the mutation probability of the individual.

We use different mutation methods depending on the component. For the MRS part, mutation is performed by randomly changing the available medical resource of the relevant stage. For the TSS part, the crossover operator is conducted. The mutation process is illustrated in Fig. 3.

Fig. 3

The mutation procedure of algorithm.

3.5 Diversified assimilation strategy

Assimilation strategy is the main strategy to produce new solutions. Generally, the strategy is implemented in the same way. In this study, the diversified assimilation strategy is adopted. For the Empire 1, there are two strategies: (1) all the colonies in the empire adopt the assimilation strategy, (2) randomly select colonies to perform the assimilation strategy. For the remaining Empire x, the assimilation strategy is conducted by learning from any other imperialists.

In the process of assimilation, for the MRS part, the two-point crossover strategy is adopted. First, two points of the imperialist are selected randomly. Then, the elements between the two points are inserted into the corresponding positions of the new colony, and the remaining positions insert the elements of the old colony. For the TSS part adopts the POX crossover strategy. First, several elements are selected at random. Then, the elements selected from the imperialist are inserted into the new colony, and the remaining elements are inserted into the new colony according to the position of the old colony. In the assimilation strategy, the enhanced global search heuristic which includes the SA algorithm and EDA is adopted to improve the global search ability of the algorithm. The main steps of assimilation are displayed in Algorithm 2.

Algorithm 2 Diversified assimilation strategy

Input: All empires

Output: The new solution

1: for x = 1 to Nim do

2: if x = 1 then

3: r = rand () % 2

4: if r = 0 then

5: All colonies in the Empire 1 are chosen for assimilation

6: end if

7: if r = 1 then

8: Randomly select colonies for assimilation

9: end if

10: end if

11: if x >1&x <Nim then

12: for x = 2 to Nim do

13: Each colony in the Empire x can learn from other randomly selected imperialist and performs assimilation strategy with the chosen imperialist

14: end for

15: The enhanced global search heuristic is used, that is

16: ⌊α× NC_x ⌋ good colonies improve by SA

17: ⌊β× NC_x ⌋ poor colonies improve by EDA

18: end if

19: end for

3.6 Enhanced global search heuristic

3.6.1 Simulated annealing algorithm

Simulated annealing (SA) algorithm as an intriguing technique for optimizing functions of various variables. The basic algorithm of SA may be described as follows: Beginning with a high temperature (T), the metal is slowly cooled, so that the system is in thermal equilibrium at every stage. At high temperatures, the metal is in liquid phase, and the atoms of the system are disordered and arranged randomly. By gradually cooling the metal, the system becomes more ordered, until it finally reaches a “frozen” ground state (ΔT), where the energy of the system has acquired the globally minimal value.

To overcome the problem of stagnating in local optima, SA utilizes a certain probability to accept a worse solution. The algorithm starts with a randomly generated solution (initial solution). In each iteration, the best neighborhood solution is generated according to the two randomly selected neighborhood structures in Section 3.7.

Annealing rate is another important module of the SA. Annealing rate has a significant relation with the acceptance probability of inferior solutions, which can directly affect the speed and accuracy of the SA. The SA algorithm terminates when the temperature recedes to the specified temperature. The annealing rate function is as follows: $T (λ) = δ \times T (λ - 1)$ (25) where δ ∈ (0, 1) is an annealing rate coefficient; T (λ) and T (λ - 1) are current annealing temperature and previous annealing temperature, respectively; λ is the iteration number. The main steps of SA are shown in Algorithm 3.

Algorithm 3 SA

Input: Good colonies

Output: The optimized solution

1: for y = 1 to the number of good colonies do

2: if T >ΔT then

3: Execute the neighborhood structure to create a new solution, as discussed in Section 3.7

4: if the fitness of the new solution < the current best solution then

5: Accept this new solution

6: else

7: Calculate the probability of accepting the new solution (rr) [18], accept the new solution with the probability of rr

8: end if

9: Update the current temperature by (24)

10: end if

11: end for

3.6.2 Estimation of distribution algorithm

Estimation of distribution algorithm (EDA) is a relatively new paradigm in the field of evolutionary computation, which employs explicit probability distributions in optimization.

In this paper, two probability matrices P1 and P2 are designed for the MRS and TSS parts. The element M_j,q,i (L) of the probability matrix P1 represents the probability of processing stage O_j,q is processed by medical resource i in generation L. m_j,q represents the array of available medical resources for the q^th stage of seeking medical treatment of patient j. The probability matrix P1 is initialized as follows: $M_{j, q, i} (0) = {\begin{matrix} \frac{1}{m_{j, q}} & if O_{j, q} can be processed by resource i \\ 0 & else \end{matrix}$ (26) element H_j,f (L) of the probability matrix P2 represents the probability that patient j will appear at position f in generation L, while Q represents the total number of stages in the TSS part. The probability matrix P2 is initialized as $H_{j, f} (0) = \frac{1}{Q}$ , which ensures that the entire solution space can be sampled uniformly. And then, the probability matrices P1 and P2 are updated according to the following equations: $M_{j, q, i} (L + 1) = (1 - θ) M_{j, q, i} (L)$ (27) $H_{j, f} (L + 1) = (1 - σ) H_{j . f} (L)$ (28) where θ, σ ∈ (0, 1) are the learning rates of P1 and P2 respectively. Sampling is performed through probabilistic models P1 and P2 to generate new individuals. The process of generating new solutions through the EDA is demonstrated in Algorithm 4.

Algorithm 4 EDA

Input: Poor colonies

Output: The optimized solution

1: while stopping criteria are not satisfied do

2: for y = 1 to the number of poor colonies do

3: A new solution is generated from random sampling of the probabilistic models P1 and P2

4: Compare the newly generated solution to the previous one

5: if the new solution is better then

6: Accept this new solution

7: end if

8: end for

9: end while

3.7 Neighborhood structures

The neighborhood structures N1, N2, N3, and N4 are described below. Neighborhood structure N1 is performed by replacing a randomly selected position of the MRS part. Neighborhood structure N2 acts on the TSS part, selecting two elements in a random manner and swapping them. Neighborhood structure N3 is performed by selecting two positions r1 and r2 at random, where r1 < r2, the element of r2 is inserted before r1 in the MRS part. Neighborhood structure N4 generates a new solution by performing one swap operator two times in the TSS part (Fig. 4).

Fig. 4

Examples of neighborhood structures.

3.8 Updating of empires

Through the iterations, colonies may obtain greater power than their imperialists. In this case, the colony with greatest power becomes the new imperialist, colonies under the old imperialist are assigned to the new imperialist, and the old imperialist becomes a colony of the new imperialist. Then, the worst empire is updated by EDA.

3.9 Empires invasion

With the development of the empire, great changes will occur in each empire. To gain more power, some empires may conduct empires invasion strategy, that is, powerful empires occupy several colonies of other weak empires. Provided that colonies under the rule of the imperialist no longer exist, and the empire perished. The main steps of empires invasion strategy are shown in Algorithm 5.

Algorithm 5 Empires Invasion strategy

1: Select the better empires which with the better fitness

2: for all the selected empires do

3: Occupy the colonies of poorer (unselected) empires randomly

4: if there is no colony in the worse empire then

5: Ascribe the imperialist of the empire to other empires

6: end if

7: end for

4 Simulation analysis

This section evaluates the effectiveness of the proposed HICA on the outpatient scheduling problem. The compared algorithms are coded in C++ on a Lenovo PC with a 3.3-GHz processor and 4-GB memory running Windows 7. Before the experiment, five different cases in a large third-class hospital were analyzed within one week. According to the research problem, through analysis, the data obtained are used in the experimental instances, and the experiment is carried out. After the experiment, the outpatient scheduling schedule is obtained, and the schedule established in advance is applied to outpatient scheduling.

4.1 Sensitivity analysis

To study the influence of some important parameters on the value of the objective function, four parameters, the country size (pop), the ratio of the imperialist to countries (Nim/pop), the ratio of good colonies improved through SA (α) and the ratio of poor colonies improved through EDA (β), are selected to conduct the sensitivity analysis, and the results are shown in Fig. 5.

Fig. 5

Sensitivity analysis on important parameters.

From Fig. 5, it can be found that the objective function has a downward trend at first and then an upward trend with the parameter pop. The objective function has a downward trend at first and then an upward trend with the parameter Nim/pop. For parameter α, the objective function first showed a downward trend and then an upward trend in the selection interval. For parameter β, at first the objective function has a descending trend then it arrives to a stable state.

4.2 Performance comparison with exact solver CPLEX

To verify the quality of the proposed algorithm for solving the outpatient scheduling problem, this section compared HICA and CPLEX. The settings for the exact solver are as follows. The maximum number of threads was 3, and the time limit was set to 3 h. For the HICA, due to its ability to obtain a satisfactory solution within an acceptable time, the CPU stop time was set to 30 s. Then, 15 small-scale instances of outpatient scheduling problem were randomly generated.

With an increase in the number of patients and stages, there is an exponential increase in time to solve the problem to optimality on CPLEX because of the NP-hard property. Thus, for some large-scale instances, the optimal solutions cannot be obtained on CPLEX within 3 h. Table 2 presents the comparison results between the proposed algorithm and the CPLEX solver. The first column lists the instance name (where jXmY represents X patients and Y stages), the second column displays the best fitness values for each instance. The fitness values for each instance are provided in the third and fourth columns, while the fifth and sixth columns provide the deviation of the objective value of each algorithm compared with the best value.

Table 2
Comparison results for the CPLEX solver and HICA

Instance Best Fitness Deviation

CPLEX HICA CPLEX HICA

j2m2 78.000 79.000 79.000 0.000 0.000

j2m3 105.000 105.000 105.000 0.000 0.000

j2m4 140.000 141.000 141.000 0.000 0.000

j3m2 119.000 121.000 119.000 0.017 0.000

j3m3 167.000 172.000 167.000 0.030 0.000

j3m4 182.000 182.000 182.000 0.000 0.000

j4m2 101.000 101.000 101.000 0.000 0.000

j4m3 162.000 162.000 162.000 0.000 0.000

j4m4 231.000 233.000 231.000 0.009 0.000

j5m2 147.000 147.000 147.000 0.000 0.000

j5m3 238.000 245.000 238.000 0.029 0.000

j5m4 309.000 - 309.000 - 0.000

j6m2 181.000 181.000 181.000 0.000 0.000

j6m3 276.000 - 276.000 - 0.000

j6m4 351.000 - 351.000 - 0.000

4.3 Efficiency of the mutation strategy

To verify the effectiveness of the proposed mutation strategy, we performed detailed comparisons of the two algorithms, namely, the algorithm with all of the components of the proposed HICA except for the proposed mutation strategy (hereafter called the HICA_NMS) and the proposed HICA with all of the components. Each calculation instance was executed 30 times independently, each for 30 s. To determine whether the resulting comparisons were significantly different, we performed a multifactor analysis of the variance (ANOVA). The confidence level was set to be 95%. When the p-value was less than 0.05, the difference between the algorithms was significant. Figure 6 shows the ANOVA results obtained by comparing the two algorithms. It can be concluded from Fig. 6 that the proposed mutation strategy can increase the probability of the algorithm to obtain a better solution.

Fig. 6

ANOVA of the mutation strategy.

4.4 Efficiency of the diversified assimilation strategy

To investigate the effectiveness of the diversified assimilation strategy, three variants of HICA were constructed: (1) HICA1 did not include the SA strategy, but the remainder of the content was consistent with the HICA; (2) the difference between HICA2 and HICA was that the EDA was eliminated from HICA; (3) and HICA3 with the canonical assimilation strategy as described in [19]. Each calculation instance was executed 30 times independently, each for 30 s, and the results were obtained. Figure 7 presents the ANOVA results obtained by comparing the four algorithms. It can be concluded from Fig. 7 that the proposed diversified assimilation strategy can obtain significantly better results.

Fig. 7

ANOVA results of HICA and its variants.

4.5 Efficiency of the empires invasion strategy

The empires invasion strategy discussed in Section 3.9 is another contribution to the proposed algorithm. To evaluate its performance, we compared the following two algorithms: HICA_NEI with all the components except the empires invasion strategy and HICA with all components discussed in Section 3. All other components of the two compared algorithms were identical. Figure 8 provides ANOVA comparisons of the two algorithms. The figure indicates that there are significant differences between the compared algorithms, and the proposed empires invasion strategy enhances the performance of the proposed algorithm.

Fig. 8

ANOVA of the empires invasion strategy.

4.6 Comparison with other algorithms

To further evaluate the performance of the proposed HICA, we selected the following algorithms for comparison: ICA (Karimi et al. [19]), improved GA (IGA) (Zhang et al. [20]), EDA (Zhao et al. [21]), and modified artificial immune algorithm (MAIA) (Zeng and Wang [22]). For fair comparison, all algorithms were run for 30 s in the same running environment. The average fitness values for each instance were collected for detailed comparison (Table 3).

Table 3
Comparison results of multiple algorithm

Instance best Fitness Deviation

HICA ICA IGA MAIA EDA HICA ICA IGA MAIA EDA

j3m3 87.000 87.000 87.000 87.000 87.000 137.500 0.000 0.000 0.003 0.000 0.580

j3m5 126.000 126.000 134.033 134.000 211.467 166.000 0.000 0.064 0.063 0.678 0.317

j3m6 141.000 141.000 168.500 169.233 261.167 249.000 0.000 0.195 0.200 0.852 0.766

j3m8 195.033 195.033 228.400 225.000 340.333 259.033 0.000 0.171 0.154 0.745 0.328

j3m10 248.400 248.400 305.300 309.267 401.433 358.300 0.000 0.229 0.245 0.616 0.442

j5m3 135.167 137.800 135.167 151.800 219.000 168.867 0.019 0.000 0.123 0.620 0.249

j5m5 152.033 152.033 181.600 185.067 294.600 219.167 0.000 0.194 0.217 0.938 0.442

j5m6 186.933 186.933 224.567 237.900 328.567 295.133 0.000 0.201 0.273 0.758 0.579

j5m8 255.667 255.667 288.300 284.133 455.467 328.633 0.000 0.128 0.111 0.781 0.285

j5m10 313.133 313.133 342.067 341.533 489.633 377.633 0.000 0.092 0.091 0.564 0.206

j10m3 115.367 117.000 115.367 150.300 188.900 141.300 0.014 0.000 0.303 0.637 0.225

j10m5 114.000 114.000 129.333 140.267 212.867 150.667 0.000 0.135 0.230 0.867 0.322

j10m6 187.000 187.000 212.433 221.100 346.033 242.500 0.000 0.136 0.182 0.850 0.297

j10m8 294.600 294.600 337.600 342.367 485.467 390.767 0.000 0.146 0.162 0.648 0.326

j10m10 331.800 331.800 363.133 364.000 507.633 400.067 0.000 0.094 0.097 0.530 0.206

j20m3 209.433 209.433 219.033 317.167 406.833 253.100 0.000 0.046 0.514 0.943 0.209

j20m5 240.433 240.433 265.400 299.833 411.800 303.667 0.000 0.104 0.247 0.713 0.263

j20m6 346.133 346.133 378.767 415.033 565.200 415.533 0.000 0.094 0.199 0.633 0.201

j20m8 430.900 430.900 478.433 513.167 699.267 523.700 0.000 0.110 0.191 0.623 0.215

j20m10 537.867 537.867 579.900 606.000 832.067 620.167 0.000 0.078 0.127 0.547 0.153

j30m3 279.333 279.333 290.633 426.400 521.867 329.900 0.000 0.040 0.526 0.868 0.181

j30m5 404.700 404.700 435.933 507.067 668.067 470.100 0.000 0.077 0.253 0.651 0.162

j30m6 550.667 550.667 594.867 679.367 846.067 637.533 0.000 0.080 0.234 0.536 0.158

j30m8 601.667 601.667 646.800 690.000 936.933 692.500 0.000 0.075 0.147 0.557 0.151

j30m10 769.500 769.500 814.400 860.500 1157.970 867.067 0.000 0.058 0.118 0.505 0.127

j50m3 533.233 533.233 543.200 776.300 864.967 550.267 0.000 0.019 0.456 0.622 0.032

j50m5 586.667 586.667 613.533 769.500 933.600 639.967 0.000 0.046 0.312 0.591 0.091

j50m6 867.467 867.467 910.833 1058.070 1244.800 953.233 0.000 0.050 0.220 0.435 0.099

j50m8 957.467 957.467 1004.970 1167.070 1356.070 1046.900 0.000 0.050 0.219 0.416 0.093

j50m10 979.533 979.533 1025.600 1124.400 1349.800 1060.270 0.000 0.047 0.148 0.378 0.082

j100m3 1105.100 1159.330 1110.770 1603.570 1691.770 1105.100 0.049 0.005 0.451 0.531 0.000

j100m5 1290.370 1290.370 1326.800 1645.070 1899.070 1366.930 0.000 0.028 0.275 0.472 0.059

j100m6 1657.600 1657.600 1709.670 1996.230 2188.500 1746.470 0.000 0.031 0.204 0.320 0.054

j100m8 1771.500 1771.500 1809.830 2037.200 2113.200 1827.170 0.000 0.022 0.150 0.193 0.031

j100m10 1819.330 1819.330 1869.430 2058.800 2153.770 1896.000 0.000 0.028 0.132 0.184 0.042

mean 537.772 539.444 568.046 654.113 790.605 605.433 0.002 0.082 0.216 0.470 0.126

Instance	best	Fitness	Deviation
j3m3	87.000	87.000	87.000	87.000	87.000	137.500	0.000	0.000	0.003	0.000	0.580
j3m5	126.000	126.000	134.033	134.000	211.467	166.000	0.000	0.064	0.063	0.678	0.317
j3m6	141.000	141.000	168.500	169.233	261.167	249.000	0.000	0.195	0.200	0.852	0.766
j3m8	195.033	195.033	228.400	225.000	340.333	259.033	0.000	0.171	0.154	0.745	0.328
j3m10	248.400	248.400	305.300	309.267	401.433	358.300	0.000	0.229	0.245	0.616	0.442
j5m3	135.167	137.800	135.167	151.800	219.000	168.867	0.019	0.000	0.123	0.620	0.249
j5m5	152.033	152.033	181.600	185.067	294.600	219.167	0.000	0.194	0.217	0.938	0.442
j5m6	186.933	186.933	224.567	237.900	328.567	295.133	0.000	0.201	0.273	0.758	0.579
j5m8	255.667	255.667	288.300	284.133	455.467	328.633	0.000	0.128	0.111	0.781	0.285
j5m10	313.133	313.133	342.067	341.533	489.633	377.633	0.000	0.092	0.091	0.564	0.206
j10m3	115.367	117.000	115.367	150.300	188.900	141.300	0.014	0.000	0.303	0.637	0.225
j10m5	114.000	114.000	129.333	140.267	212.867	150.667	0.000	0.135	0.230	0.867	0.322
j10m6	187.000	187.000	212.433	221.100	346.033	242.500	0.000	0.136	0.182	0.850	0.297
j10m8	294.600	294.600	337.600	342.367	485.467	390.767	0.000	0.146	0.162	0.648	0.326
j10m10	331.800	331.800	363.133	364.000	507.633	400.067	0.000	0.094	0.097	0.530	0.206
j20m3	209.433	209.433	219.033	317.167	406.833	253.100	0.000	0.046	0.514	0.943	0.209
j20m5	240.433	240.433	265.400	299.833	411.800	303.667	0.000	0.104	0.247	0.713	0.263
j20m6	346.133	346.133	378.767	415.033	565.200	415.533	0.000	0.094	0.199	0.633	0.201
j20m8	430.900	430.900	478.433	513.167	699.267	523.700	0.000	0.110	0.191	0.623	0.215
j20m10	537.867	537.867	579.900	606.000	832.067	620.167	0.000	0.078	0.127	0.547	0.153
j30m3	279.333	279.333	290.633	426.400	521.867	329.900	0.000	0.040	0.526	0.868	0.181
j30m5	404.700	404.700	435.933	507.067	668.067	470.100	0.000	0.077	0.253	0.651	0.162
j30m6	550.667	550.667	594.867	679.367	846.067	637.533	0.000	0.080	0.234	0.536	0.158
j30m8	601.667	601.667	646.800	690.000	936.933	692.500	0.000	0.075	0.147	0.557	0.151
j30m10	769.500	769.500	814.400	860.500	1157.970	867.067	0.000	0.058	0.118	0.505	0.127
j50m3	533.233	533.233	543.200	776.300	864.967	550.267	0.000	0.019	0.456	0.622	0.032
j50m5	586.667	586.667	613.533	769.500	933.600	639.967	0.000	0.046	0.312	0.591	0.091
j50m6	867.467	867.467	910.833	1058.070	1244.800	953.233	0.000	0.050	0.220	0.435	0.099
j50m8	957.467	957.467	1004.970	1167.070	1356.070	1046.900	0.000	0.050	0.219	0.416	0.093
j50m10	979.533	979.533	1025.600	1124.400	1349.800	1060.270	0.000	0.047	0.148	0.378	0.082
j100m3	1105.100	1159.330	1110.770	1603.570	1691.770	1105.100	0.049	0.005	0.451	0.531	0.000
j100m5	1290.370	1290.370	1326.800	1645.070	1899.070	1366.930	0.000	0.028	0.275	0.472	0.059
j100m6	1657.600	1657.600	1709.670	1996.230	2188.500	1746.470	0.000	0.031	0.204	0.320	0.054
j100m8	1771.500	1771.500	1809.830	2037.200	2113.200	1827.170	0.000	0.022	0.150	0.193	0.031
j100m10	1819.330	1819.330	1869.430	2058.800	2153.770	1896.000	0.000	0.028	0.132	0.184	0.042
mean	537.772	539.444	568.046	654.113	790.605	605.433	0.002	0.082	0.216	0.470	0.126

Figure 10 presents the ANOVA results of the average solutions of the five comparison algorithms, from which it can be concluded that the HICA has better performance in solving the studied problem. Furthermore, to demonstrate the convergence ability of the proposed algorithm, we conducted detailed comparisons between the HICA and other four algorithms, and the convergence curves for the four instances with different features are depicted in Fig. 9(a)-(d).

Fig. 10

Convergence comparison between multiple algorithms.

Fig. 9

ANOVA results for comparing multiple algorithms.

5 Conclusion

As the core department of the hospital, outpatient service is regarded as the facade of the hospital, which accounts for a large proportion of the expenditure and profit of the hospital. Due to the growing demand for outpatient appointments and a serious shortage of medical staff, outpatient scheduling has been highly valued in many countries. For many general hospitals, outpatients account for 3/4 of outpatients. Especially during the epidemic period of novel coronavirus, effective outpatient scheduling plays a more and more important role. Effective outpatient scheduling can promote the flow of hospital personnel, reduce potential risks and promote the effective use of resources.

This study addresses the outpatient scheduling problem with switching and preparation times. The problem is an extension of the FJSP. To solve the problem, the HICA is proposed. In the proposed algorithm, first, the mutation strategy with different mutation probabilities is utilized to generate feasible and efficient solutions. Then, the diversified assimilation strategy is developed. The enhanced global search heuristic, which includes the SA algorithm and EDA, is adopted in the assimilation strategy to improve the global search ability of the algorithm. Furthermore, four kinds of neighborhood search strategies are introduced to generate new promising solutions. Finally, the empires invasion strategy is proposed to increase the diversity of the population. In the experimental part, first, the influence of the important parameters of the algorithm on the objective value is obtained by sensitivity analysis. Then, the validity of the model and algorithm is verified by CPLEX. Furthermore, the effectiveness of the algorithm strategy is verified. Finally, the algorithm is compared with other algorithms to further verify the effectiveness of the developed algorithm.

In the course of study, the patient visit time, switching and preparation times, were set in advance. In real life, due to a variety of uncertain factors, these times may change, which will result in a time difference between the scheduled completion time and the real scheduled completion time. Therefore, the future work will focus on the following aspects: (1) using fuzzy numbers to express the time of each stage; (2) considering the insertion and handling of acute patients; and (3) improving the balance of the exploitation and exploration abilities of the proposed algorithm.

Footnotes

Acknowledgments

This research is partially supported by National Science Foundation of China under Grant 61803192, and 61773246, Shandong Province Higher Educational Science and Technology Program (J17K Z005), and major Program of Shandong Province Natural Science Foundation (ZR2018Z B0419).

References

Saremi

, Jula

, ElMekkawy

and Wang

G.G.

, Appointmentscheduling of outpatient surgical services in a multistage operatingroom department, Int J Prod Econ 141 (2013), 646–658.

J.Q.

, Du

, Gao

K.Z.

, Duan

P.Y.

, Gong

D.W.

, Pan

Q.K.

and Suganthan

P.N.

, A hybrid iterated greedy algorithm for a crane transportation flexible job shop problem, Ieee T Autom Sci Eng (2021). http://doi,org/10.1109/TASE.2021.3062979.

Chen

, Ihlow

and Lehmann

, A genetic algorithm for flexible job-shop scheduling, In: Proceedings 1999 IEEE International Conference on Robotics andAutomation, Ieee, pp 1120–1125.

Atashpaz-Gargari

and Lucas

, Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition, In: 2007 IEEE congress on evolutionary computation, Ieee, pp 4661–4667.

Boukef

, Benrejeb

and Borne

, Flexible job-shop schedulingproblems resolution inspired from particle swarm optimization, Stud Inform Control 17 (2008), 241–252.

Luo

, Zhang

and Fan

, Energy-efficient scheduling formulti-objective flexible job shops with variable processing speedsby grey wolf optimization, J Clean Prod 234 (2019), 1365–1384.

J.Q.

, Chen

X.L.

, Duan

P.Y.

, and Mou

J.H.

, KMOEA: A knowledge-based multi-objective algorithm for distributed hybrid flow shop in a prefabricated system, IEEE T Ind Inform (2021), http://doi.org/10.1109/TII.2021.3128405

, Li

J.Q.

, Luo

and Meng

L.L.

, A hybrid estimation ofdistribution algorithm for distributed flexible job shop schedulingwith crane transportations, Swarm Evol Comput 62 (2021), 100861.

Cao

, Lin

and Zhou

, A knowledge-based cuckoo search algorithm to schedule a flexible job shop with sequencing flexibility, Ieee T Autom Sci Eng (2019). https://doi.org/10.1109/TASE.2019.2945717.

10.

Zhu

, Hou

, Wang

and Zhou

, An efficient outpatientscheduling approach, Ieee T Autom Sci Eng 9 (2012), 701–709.

11.

Patrick

, A Markov decision model for determining optimaloutpatient scheduling, Health Care Management Science 15(2012), 91–102.

12.

Geng

and Xie

, Optimal dynamic outpatient scheduling for adiagnostic facility with two waiting time targets, Ieee TAutomat Contr 61 (2014), 3725–3739.

13.

Creps

and Lotfi

, A dynamic approach for outpatient scheduling, J Med Econ 20 (2017), 786–798.

14.

Deceuninck

, Fiems

and De Vuyst

, Outpatient scheduling withunpunctual patients and no-shows, Eur J Oper Res 265(2018), 195–207.

15.

Sun

, Raghavan

U.N.

, Vaze

, Hall

C.S.

, Doyle

, Richardand

S.S.

and Wald

, Stochastic programming for outpatient scheduling with flexible inpatient exam accommodation, Health Care Management Science (2021), 1–22.

16.

, Li

, Zhang

and Kong

, Integrated optimization ofappointment allocation and access prioritization in patient-centredoutpatient scheduling, Comput Ind Eng 154 (2021), 107125.

17.

Zhang

, Gao

and Shi

, An effective genetic algorithm for theflexible job-shop scheduling problem, Expert Syst Appl 38 (2011), 3563–3573.

18.

Peng Zhang

, Tang

, Feng

and Yin

, Research on flexible job-shop scheduling problem in green sustainable manufacturing based on learning effect, J Intell Manuf (2018), 1–10.

19.

Karimi

, Ardalan

, Naderi

and Mohammadi

, Schedulingflexible job-shops with transportation times:Mathematical models and a hybrid imperialist competitive algorithm, Appl Math Model 41 (2017), 667–682.

20.

Zhang

, Hu

, Sun

and Zhang

, An improved genetic algorithmfor the flexible job shop scheduling problem with multiple timeconstraints, Swarm Evol Comput 54 (2020), 100664.

21.

Zhao

, Shao

, Wang

and Zhang

, A hybrid differentialevolution and estimation of distribution algorithm based onneighbourhood search for job shop scheduling problems, Int JProd Econ 54 (2016), 1039–1060.

22.

Zeng

and Wang

, A chaotic simulated annealing and particleswarm improved artificial immune algorithm for flexible job shopscheduling problem, Euasip J Wirel Comm 2018 (2018), 1–10.