key: cord-0782547-pgb65ohe authors: Yu, Hui; Li, Jun-qing; Zhang, Lijing; Duan, Peng title: An imperialist competition algorithm using a global search strategy for physical examination scheduling date: 2020-11-23 journal: Appl Intell DOI: 10.1007/s10489-020-01975-y sha: 820d282a14ea83bb401bf8f644bb3c019e3b0603 doc_id: 782547 cord_uid: pgb65ohe The outbreak of the novel coronavirus clearly highlights the importance of the need of effective physical examination scheduling. As treatment times for patients are uncertain, this remains a strongly NP-hard problem. Therefore, we introduce a complex flexible job shop scheduling model. In the process of physical examination for suspected patients, the physical examiner is considered a job, and the physical examination item and equipment correspond to an operation and a machine, respectively. We incorporate the processing time of the patient during the physical examination, the transportation time between equipment, and the setup time of the patient. A unique scheduling algorithm, called imperialist competition algorithm with global search strategy (ICA_GS) is developed for solving the physical examination scheduling problem. A local search strategy is embedded into ICA_GS for enhancing the searching behaviors, and a global search strategy is investigated to prevent falling into local optimality. Finally, the proposed algorithm is tested by simulating the execution of the physical examination scheduling processes, which verify that the proposed algorithm can better solve the physical examination scheduling problem. The problem studied here is a result of the novel coronavirus outbreak that began in 2019, which first attacked Wuhan, China, and quickly spread to most regions of the country. Three months later, the virus had swept the world, and as of April 28, 2020, the novel coronavirus epidemic infected 3034801 people and killed 210511 (according to data released by Johns Hopkins University in the United States https://gisanddata.maps.arcgis.com/apps/opsdashboard/ index.html#/bda7594740fd40299423467b48e9ecf6). Facing so many patients within a short period became a critical challenge for hospitals with limited resources and Jun-qing Li lijunqing@lcu-cs.com 1 equipment [1, 2] . Using available resources with the best efficiency, improving patient flow, and optimizing treatment management are crucial for hospitals [3] . With the growth of the disease, many hospitals expanded capacity because the number of patients, even in Wuhan, far exceeded the standard carrying capacity. However, due to many obstacles, these expansion activities encountered many restrictions, which further reduced the available resources for meeting established needs efficiently. During the process of physical examinations of suspected patients with the novel coronavirus, the traditional extensive medical approach includes most physical examinations choosing the items with less waiting time. As the examinations increased in the queue at the physical examination center, more time was wasted with longer waits. To reduce this bottleneck, we introduce a scheduling system that determines the start time of each patient in different testing groups as well as the order in the scheduling cycle. Additional medical challenges can be solved by enhanced scheduling. Hsieh [4] proposed a viable and systematic approach to develop a scalable and sustain-able scheduling system based on multi-agent system (MAS) to shorten patient stay in a hospital. Quintana et al. [5] studied the Home Health Care Scheduling Problem which involves allocating professional caregivers to patients' places of residence to meet service demands. Azaiez and Al-Sharif [6] developed a computerized nurse scheduling model approximated by 0-1 goal programming for improving manual scheduling. Pham and Klinkert [7] researched a new surgical case scheduling method to ensure the quality of patient care and effectively use hospital resources. Zhu et al. [8] proposed an efficient outpatient scheduling method and created a qualification matrix to apply the group role assignment algorithm, making an automatic outpatient scheduling feasible. Cappanera et al. [9] studied the performance of three scheduling strategies. The goal of this plan is to maximize the number of scheduled surgeries and balance the workload across beds and operating rooms. Gartner and Kolisch [10] studied hospital patient flow planning to maximize the contribution margin by developing two mixed-integer programming (MIP) processes to be embedded into static and rolling horizontal programming methods under the condition of scarcity of medical resources. This approach considered the procedures of the clinical pathway (such as the types of diagnostic activities and surgery) as well as the sequence in which they must be applied to the patient. Ahmadi-Javid et al. [11] developed a method based on decentralized agents, in which patients and hospital resources are represented as agents with individual goals to solve challenges of patient scheduling and hospital resources. Erhard et al. [12] adopted a quantitative method of doctor scheduling in hospitals by describing the related characteristics of various doctor scheduling problems investigated. Jiang et al. [13] proposed the two simple scheduling strategies of weight accumulation and priority enhancement for improving waiting time management. These experimental results suggested that an effective scheduling strategy can significantly reduce patient waiting times without expensive capacity expansions. Scheduling is becoming more and more popular in recent years [14, 15] . The flexible job shop scheduling problem (FJSP) is an extension of job shop scheduling [16] . FJSP primarily considers two problems, the first of which sorts all operations of the job into a reasonable order, and the second assigns each sorted operation an appropriate and available machine. The makespan represents the maximum completion time of a job. The FJSP model plays an important role in the medical field and services with its application, enabling hospital resources to be effectively used in limited time. The FJSP provides a pre-analysis of the processing time and notifies employees in advance of upcoming activities so that patients can be prepared quickly. Yin et al. [17] represented surgery scheduling as an extended multi-resource, constrained FJSP that was solved by an improved ant colony algorithm. Su et al. [18] regarded the problem of determining the optimal operating room schedule as a FJSP and proposed a SOMO-based approach for solving the operating room scheduling problem. Lee et al. [19] studied the problem of completing multiple processes within one day as a flexible job shop model with fuzzy sets and proposed a scheduling strategy to determine the start time of multiple operating rooms. Behmanesh et al. [20] researched the surgical case scheduling problem in multioperating theater environment with uncertain service times in order to minimize makespan and structured the no-wait multiresources fuzzy fexible job shop scheduling in operating theater. Also, Behmanesh and Zandieh [21] studied the Surgical case scheduling problem with fuzzy surgery time and formulated the problem as a novel bi-objective nowait multi-resource FJSP. The surgical cases are optimally allocated to the existing resources and sequenced in the surgery list of these resources so as to minimize both objectives within their time window. Luscombe et al. [22] proposed a dynamic scheduling framework to provide real-time support for the management of scarce resources in emergency departments. Recently, many meta-heuristic algorithms have been applied to FJSP, such as the simulated annealing algorithm [23] based on local search heuristics, variable neighborhood search (VNS) [24] , the Tabu search algorithm [25] , and the iterative greedy (IG) algorithm [26] , as well as population-based methods, including the particle swarm optimization algorithm (PSO) [27] , a hybrid discrete artificial bee colony (ABC) algorithm [28] , An improved Jaya (IJaya) algorithm [29] , an improved artificial immune system (IAIS) algorithm [30] , and discrete imperialist competitive algorithm (DICA) [31] . The traditional open shop scheduling method is not flexible enough, and many types of medical equipment cannot be fully utilized during an emergency. The main contribution of this paper is that the physical examination scheduling is regarded as a FJSP, and an improved imperialist competition algorithm is applied to the improvement of hospital physical examination scheduling. The improved local search strategy is embedded in the algorithm to enrich the search behavior and avoid premature convergence. A global search strategy is studied to prevent falling into local optimization. The optimization idea of sorting and scheduling is fully combined to make effective use of limited resources and equipment. The remainder of this paper is organized as follows. The second section describes the scheduling environment and formally states the problem. The third section details the description of the algorithm, and the fourth section reviews the experiment to verify the algorithm. Finally, the fifth section provides a summary and suggests future research. For an example scheduling scenario, we first investigate the physical examination of the patient suspected to have the novel coronavirus. With a pre-analysis of the time required to perform the physical examination, the exam is then scheduled and completed as planned. Our goal is to identify a scheduling scheme that allows for the shortest completion times within this environment. The FJSP is defined as follows. A set of jobs J ={J 1 , ..., J n } must be performed on a set of machines M={M 1 , ..., M n } where each independent job J i consists of a sequence of operations O i . To apply FJSP, we consider the patient as a job, each physical examination item as an operation, and the physical equipment is considered machine. Considering the transportation time between the input warehouse and the first machine, a virtual machine with zero processing time is defined, machine 0. Within the processing time of the patient during physical examination, the transportation time between equipment and the setup time required for the patient are also incorporated. The FJSP approach is adopted because patients can be assigned to a variety of physical examination equipment. Figure 1 depicts the physical examination scheduling as a FJSP, because the transportation time and setup time are taken into account, therefore, patients will not proceed directly when it reaches equipment. In addition, some patients may have a physical examination on the same device, therefore patient 2 has a physical examination in equipment 1 twice, indicating that different physical examination items of patient 2 are carried out on the same physical examination equipment. During the process of physical examination scheduling, the following constraints exist: -All patients are ready at time zero. Fig. 1 The physical examination scheduling process -Each patient has a fixed number of physical examinations operations. -Transportation and setup times must be considered. -Once a patient is examined on equipment, the process is not interrupted until the entire routine is complete. -The time of the next operation is greater than or equal to the time of the previous operation. The parameters and indexes are listed in Table 1 . For a mathematical model of FJSP, a sequence-based mixed-integer linear programming model is established to minimize the physical examination times of patients. The objective is to to minimize the makespan of a patient's physical examination. Therefore, the objective function can be expressed as constraint (1), where C max represents the maximum completion time. MinC max (1) Constraint (2) and (3) guarantees that every physical examination item should be allocated to only one equipment. If the Y j,1,i,0 value of is 1 that represents the first operation of patient j is processed on machine i. During the physical examination that each physical examination item for each patient is allocated to a single piece of equipment, and that these must be selected from a series of available equipment, which can be expressed by constraints (4) and (5). According to the definition of variable Y j,q,i,k , O j,q−1 should be processed on equipment k, if is processed on O j,q equipment i. Therefore, constraints (6) and (7) The constraints (8)- (17) are sequencing constraints. Constraints (8) and (9) enforce that starts O j,q just after the completion of patient O j,q−1 and the transportation and setup time of patient j to equipment i. Constraints (10) to (17) ensure that equipment can only be applied to one patient at a time. The completion time of the whole physical examination scheduling is greater than or equal to the completion time of each physical examination scheduling, and each scheduling time is more than 0, which can be expressed by constraint (18) and (19) . Constraint (20) shows that those related variables are binary. To solve the physical examination scheduling problems, we apply a new intelligent optimization algorithm, called the imperialist competition algorithm that is inspired by the competitive behavior of the imperialist. In the ICA GS, individuals are represented as countries. First, the better countries with smaller makespan values are called imperialists, and others become colonies of these imperialists. Then, the imperialists who occupy the colonies attempt to assimilate them and apply a mutation before the assimilation. After the internal strengths of the imperialists change, the strategy of the imperial competition and updates is implemented. During this process, the most powerful colony replaces the weakest imperialist. When an imperialist no longer has colonies, it undergoes a demise strategy to re-assign it to the imperialist that is the most power over their colonies. The adoption of a strategy for an imperial development plan satisfies the fact that imperialists feature certain development strengths and ruling strategies in the real world. For the process of continuous development, there may appear similar countries, and similarity significantly reduces the performance of the algorithm. Therefore, we adopt a similarity replacement strategy. In addition, a local search strategy is embedded in the ICA GS for enhancing search behaviors and prevented the solution from falling into a local optimization that was introduced by the global search strategy. The framework for the ICA GS is described in Algorithm 1. Each solution uses a multi-layer coding rule that contains information about the equipment selection (EQS) and examination sequence (EXS) (Fig. 2) . The equipment selection randomly selects available physical examination equipment according to the physical examination items of the patient and stores the available physical examination equipment numbers into the EQS array. For the examination sequence, the patient number is stored in the EXS array according to a random order of the patient underwent a physical examination. The initial solution requires the corresponding processing of the EQS part, for which we adopt the LS strategy proposed by Zhang et al. [32] , and the EXS part, for which we use a random selection strategy. In the ICA GS, all populations (P op) include several imperialists (Nim) and their countries (Ncl). The imperialists have the smaller makespan, and the remainder are colonies of the imperialists, such that A roulette selection process is applied to calculate the power of each imperialist as The calculation of the number of colonies occupied by each imperialist (colonyNum) is performed according to Mutation is a strategy adopted by the imperialist to reduce repetition (Fig. 3 ). If the imperialist improves after a mutation, then the new imperialist replaces the previous imperialist. Otherwise, the imperialist remains unchanged. The operation of the mutation follows the process as: (1) For the EQS part, Step 1: Randomly select several positions. Step 2: Replace the elements of the selected positions with the available equipment numbers. (2) For the EXS part, Step 1: Randomly select two positions. Step 2: Swap the element of the two positions. The process by which colonies learn from empires is called assimilation. The steps for the assimilation strategies are as follows: (1) For the EQS part, we apply the two-point crossover strategy [33] (Fig. 4 ). Step 1: Choose an imperialist and one of its colonies, with EQS parts represented as Q1 and Q2, respectively. Step 2: Randomly select two positions from Q1. Step 3: Insert elements between the selected positions in Q1 into the EQS part (Qm1) of the new colony. Then, the remaining position inserts the element of the corresponding previous colony. (2) For the EXS part, we adopt the POX strategy [34] ( Fig. 5 ). Step 1: Choose an imperialist and one of its colonies, with their EXS parts represented by X1 and X2, respectively. Step 2: Randomly select several positions from X1. Step 3: Insert the elements of the selected positions from the imperialist into the EXS part (Xo1) of the new colony, and insert the other elements of X2 into Xo1 in order. A new colony is obtained after assimilation. If the new colony is improved over the previous version, then the previous colony is replaced. Otherwise, the previous colony remains. Through iteration, colonies may gain more power than the corresponding imperialist. In this scenario, the most powerful colony becomes the new imperialist. The colonies under the previous imperialist are then allocated to the new imperialist. The previous imperialist also becomes a colony of the new imperialist (Fig. 6 ). During the imperialist competition, the strongest and weakest imperialists are selected. Then, the colonies of the weakest imperialist transfer to belonging to the most powerful imperialist (Fig. 7) . When an imperialist does not have any colonies, then the imperialist performs the strategy of extinction. To improve the performance of ICA GS, we apply the development mechanism to make some changes to the imperialist. This process is also separated into two parts. Step 1: For the EQS part, a position is randomly selected and replaced with an available equipment number . Step 2: For the EXS part, two positions are randomly selected, and the elements of the first position are moved into the second position. The element between these two positions moves forward. During the process of continuous development of the empires, highly similar countries may appear; this reduces the performance of the algorithm. For addressing this issue, we adopt the following similarity replacement strategy. Step 1: Randomly select two colonies within the imperialist. Step 2: Compare the similarity between the elements in the two parts of the solution of the selected colonies. Step 3: After comparison, those pairs with the highest similarity are selected, and then initialize one of the countries to reduce similarity of the colonies. To further enhance the performance of the proposed algorithm, a local search strategy is next introduced. The number Otherwise, the previous solution is replaced with a lower probability. The outer loop uses the two-point crossover strategy and replaces the previous solution if it obtains a better one. Otherwise, the previous solution is replaced with a lower probability. The framework for this local search approach is described in Algorithm 2. A global search strategy is applied to improve the unimproved solution during the last several iterations and eliminate the state that exists in a local optimum. This final optimization enables the entire population to achieve a better solution. Step 1: Create a vector W 1 for storing the replaced solution from each evolution when the solution cannot be improved after a given iteration. Step 2: Create a vector W 2 for storing the local optimal solution. Step 3: Apply the following two methods of random selection to produce the optimal solution. The framework for the global search approach is described in Algorithm 3. We simulate the execution of the physical examination scheduling process by studying the operation of jobs on different machines and verifying the advantages of the algorithm. All numerical experiments are performed on a Lenovo PC with a 3.3-GHz processor and 4-GB memory We test the influence of the four parameters of P op, Nim, I terOS, and I terMS on the performance of the algorithm. First, the levels of each parameter are listed in Table 2 . With these values, the Taguchi method (Montgomery [35] 2005) was introduced with which an orthogonal array L 16 is constructed. For each parameter combination, the proposed algorithm independently ran 30 times, and the average fitness value of the algorithm was collected as the response variable. Finally, the factor level trend chart for the four parameters was drawn based on the obtained data. As seen in Fig. 8 , when P op is at level 3, Nim at level 4, I terOS at level 2, and I terMS at level 4, the proposed ICA GS algorithm achieves the best performance. For evaluating the performance of the proposed algorithm, the ICA [36] was selected for comparison because it adopts a new local search strategy that makes the algorithm converge well. Our algorithm is also formed by improving the local search strategy as well as adding a new strategy. The performance measure considered is the percentage deviation (dev) of the best value, calculated as where f b represents the best solution of all comparison algorithms and f c is the best solution to the tested algorithm. Each algorithm runs 30 times independently, each time for 30 s, the best solution, the worst solution, and the average solution from the algorithm are presented in Table 3 . The first column in Table 3 represents the instance name, The second columns provides scale size of the algorithm, in which two numbers represent the number of patients and the number of physical examination equipment, respectively. The best fitness values for each instance are included in the third column. The subsequent six columns describe the minimum value, average value, maximum value collected by the two algorithms, respectively, while the dev values obtained from the two compared algorithms are provided in the last two columns. From this information in Table 3 , ICA GS obtains a better value in the same running environment. To determine if the resulting comparisons are significantly different, we performed a multifactor analysis of variance (ANOVA) with results shown in Fig. 9 for the ICA and ICA GS. This comparison suggests that the improved To validate the value of the global search strategy, we conducted detailed comparisons between the algorithm (2) The last row in the table shows that, with a dev value of 0.00, the proposed ICA GS algorithm performs better than ICA NGS. A comparison of the two algorithms with ANOVA is presented in Fig. 11 , which suggests that the proposed global search strategy enhances the searching capabilities of the proposed algorithm. In order to verify the advantage of the proposed algorithm in solving the physical examination scheduling problem, An imperialist competition algorithm using... we compared the ICA GS with other current popular algorithms, including enhanced GA (EGA) [37] , AIA [38] , and modified IG (MIG) [39] . We coded these four algorithms and ran each in the same environment. The instances ran 30 iterations to thousands of iterations, and all comparison algorithms used the same stop criteria. The optimal values obtained from comparing the four algorithms are shown in Table 6 , with the instance name in the first column, followed by the best fitness values for each instance in the second column. The best solution of all the comparing algorithms are included in the third column, which is obtained by comparing the optimal values of all algorithms. The subsequent four columns describe the fitness values collected from the four algorithms, respectively. The dev values obtained by the four compared algorithms are listed in the last four columns, respectively. From Table 6 , we make the following observations. (1) For the 42 instances with different problem scales, we use bold to specify the optimal solution obtained, through which we can see that ICA GS obtained 38 better results, which is better than all others. (2) The last line in the table suggests that, on average, the proposed algorithm obtained a value of 0.18, which is better than the other algorithms. (3) Overall, ICA GS shows significantly better performance compared with the other four algorithms. Figure 12 illustrates the ANOVA results for the four compared algorithms suggesting that ICA GS can obtain the most optimal value. Figure 13 compares the convergence curves of four examples with different problem sizes, and the simulation results demonstrate that the algorithm features good convergence for the problems considered. The outbreak of the novel coronavirus, with its serious infectivity, caused a large number of patients to become sick within a short period. With the condition of limited public resources in hospitals, more patients must receive more efficient treatments within a limited time. Therefore, we introduced a complex flexible job shop scheduling model based on the ICA GS to solve the physical examination scheduling problem. Considering the processing time of the patient during the physical examination, the transportation time between equipment, and the setup time of the patient. In addition, the local search strategy was embedded into ICA GS to enrich the searching behaviors along with a global search procedure to enhance the exploration ability. The effectiveness of the algorithm for physical examination scheduling was verified through multiple simulation experiments. In future work, we will consider the following aspects. (1) In the real world, patients may have special circumstances in the process of physical examination, such as patients whose symptoms are close to the novel coronavirus. In order to minimize the spread of the virus, we need to examine such patients in a timely manner. At this time, it may be necessary to disturb the original scheduling order, which may lead to the reallocation of scheduling space. (2) Consider the obstruction limit and no waiting condition, time and occupation limit, robust buffer, fixed activity and sequence, release time and strict cut-off time during the actual physical examination. (3) Expand the research objectives [40] , what we are studying at present is to minimize the completion time of the whole physical examination process, but in the physical examination scheduling in the real world, just minimizing the completion time of the physical examination process can not meet the actual requirements at all. Patients expect to have a physical examination as soon as possible and minimize the completion time of the whole physical examination process. Hospitals expect to minimize the use of medical resources and minimize medical costs, which will be our future research objectives. (4) In the future research, our method will be compared with the current practice to see the applicability of our method and constantly improve our method, such as integrate the algorithm with other algorithms to improve the ability of exploration. An integrated approach for scheduling health care activities in a hospital Appointment scheduling in health care: challenges and opportunities An ant colony optimization approach for solving an operating room surgery scheduling problem A hybrid and scalable multi-agent approach for patient scheduling based on Petri net models Clustering technique for large-scale home care crew scheduling problems A 0-1 goal programming model for nurse scheduling Surgical case scheduling as a generalized job shop scheduling problem An efficient outpatient scheduling approach Comparing resource balancing criteria in master surgical scheduling: a combined optimisation-simulation approach Scheduling the hospital-wide flow of elective patients Outpatient appointment systems in healthcare: a review of optimization studies State of the art in physician scheduling Data-driven analytics to support scheduling of multi-priority multi-class patients with wait time targets Efficient multi-objective algorithm for the lot-streaming hybrid flowshop with variable sub-lots Meta-heuristic algorithm for solving vehicle routing problems with time windows and synchronized visit constraints in prefabricated systems An artificial immune algorithm for the flexible job-shop scheduling problem Ant colony algorithm for surgery scheduling problem A SOMObased approach to the operating room scheduling problem Reducing patient-flow delays in surgical suites through determining start-times of surgical cases The surgical case scheduling problem with fuzzy duration time: an ant system algorithm Surgical case scheduling problem with fuzzy surgery time: an advanced bi-objective ant system approach Dynamic resource allocation to improve emergency department efficiency in real time A simulated annealing algorithm approach to hybrid flow shop scheduling with sequence-dependent setup times A variable neighborhood search for job shop scheduling with set-up times to minimize makespan Flexible job shop scheduling with tabu search algorithms A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem A particle swarm optimization-based heuristic for scheduling workflowapplications in cloud computing environments A hybrid multi-objective artificial bee colony algorithm for flexible task scheduling problems in cloud computing system An improved Jaya algorithm for solving the flexible job shop scheduling problem with transportation and setup times. Knowledge-Based Syst Improved artificial immune system algorithm for Type-2 fuzzy flexible job shop scheduling problem Discrete imperialist competitive algorithm for the resource-constrained hybrid flowshop problem with energy consumption An effective genetic algorithm for the flexible job-shop scheduling problem A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem A genetic algorithm for general machine scheduling problems Design and analysis of experiments Scheduling flexible job-shops with transportation times: Mathematical models and a hybrid imperialist competitive algorithm Multi-objective optimization for energy-efficient flexible job shop scheduling problem with transportation constraints Minimizing makespan in a blocking flowshop using a revised artificial immune system algorithm A modified iterated greedy algorithm for flexible job shop scheduling problem A hybrid iterated greedy algorithm for a crane transportation flexible job shop problem