# A FJSSP Method Based on Dynamic Multi-Objective Squirrel Search Algorithm

Authors: Yanjiao Wang; Jieru Han
Journal: International Journal of Antennas and Propagation
 (2021)

---

## Abstract

This paper comprehensively analyzes the characteristics of flexible job shop scheduling problem (FJSSP), takes the dynamic factors in the actual scheduling process such as the arrival and departure of jobs, the breakdown and recovery of machines into account at the same time, and establishes a new dynamic multi-objective mathematical model. Take the Squirrel Search Algorithm (SSA) as the core evolution strategy, and combine the multi-objective framework and the dynamic processing technology to solve the established mathematical model. Experimental results show that the mathematical model proposed in this paper can solve the flexible job shop scheduling problem effectively. Compared with other mathematical models, the mathematical model established in this paper can keep better balance between the efficiency and stability.


---

## Body

## 1. Introduction to Flexible Job Shop Scheduling Problem

The purpose of flexible job shop scheduling problem (FJSSP) is to allocate machines rationally to all the processes that arrive at the workshop to be processed, so as to achieve one or more goals concerning operation efficiency and system stability [1]. FJSSP is a complex combinatorial optimization problem. The amount of computation increases exponentially with the increase in the numbers of machines and jobs. Intelligent evolutionary algorithms are not constrained by the constraints of search space and do not rely on other auxiliary knowledge, they only need to decide the optimization objective and corresponding fitness function of the search direction, and they are suitable for solving large-scale optimization problems, such as polarization estimation, estimation, and cooperative localization [2–6]. Many scholars have used swarm intelligence and evolutionary algorithms, including the traditional intelligent optimization algorithm, such as Genetic Algorithm [7], and new intelligent evolutionary algorithms, such as Shuffled Frog Leaping Algorithm, the Swarm Spider Optimization algorithm, and so on, to solve FJSSP large-scale combinatorial optimization problems. The completion time of scheduling scheme is minimum, which is the initial optimization goal of FJSSP, and it is the most common optimization objective [8–10]; however, the actual working environment is often dynamic, i.e., new events may occur at any time, such as the arrival of new jobs, the departure of completed jobs, and the sudden breakdown of machines. Obviously, the best scheduling scheme matching the original system state is unsuitable for the new working environment. Rescheduling the jobs in the new environment is necessary. For the scheduling scheme in the new environment, if the highest efficiency is the goal, the machine with the highest efficiency for the process to be chosen may cause the load imbalance of the system, and the new scheduling scheme may have a great difference from the historical scheduling scheme, which will affect the system stability. If the system stability is the optimization objective, the gap between new and old scheduling schemes can be reduced, but the processes needed may not be performed by the most efficient machines corresponding to them, resulting in low operation efficiency. In summary, flexible job shop scheduling should consider the efficiency and stability of the system at the same time to ensure the scheduling efficiency after changing the working environment, and a mutual exclusion relationship exists between the two. Scholars have proposed new flexible job shop scheduling methods after environmental change.For instance, Lei and Jensen, respectively, aimed at the shortest completion time and the best robustness, and solved the task-scheduling problem with machine failure [11, 12]. Chryssolouris and Zhang used the weighted sum of completion time and delay time as the optimization target for production-scheduling scheme [13, 14], although the operation efficiency and system stability were considered in the optimization process; when solving the problem, multiple targets could be transformed into single targets by using the weighted summation method, and the reasonable weight values could not be set in accordance with the actual situation of the environment; consequently, the most suitable scheduling scheme was difficult to generate, and the universality was weak. Huang Zhiqing et al. set up an energy consumption model for the FJSSP problem and improved the genetic algorithm with the idea of particle swarm optimization and simulated annealing algorithm. The completion time and energy consumption were regarded as optimization objectives, and the efficiency and stability were optimized simultaneously. Nevertheless, the model ignored the difference between the old and new scheduling schemes before and after machine failure, and the system stability at fault time was poor [15]. Shi et al. solved the FJSSP problem by using the discrete multi-population invasive weed optimization algorithm, adaptive mutation, and domain search strategy to improve the algorithm’s ability to search and use the concept of rolling window to schedule the system operation at a certain time. In essence, the static FJSSP problem is divided into several time periods, and it is not applied to the dynamic situation of the task sequence leaving at any time [16]. Chen et al., used delay and deviation as efficiency indicators and stability indicators, respectively. They used NSGA-II to optimize the two targets simultaneously. The deviation degree was evaluated by the rescheduling scheme at the time of failure. The stability of the system is improved to a certain extent before and after machine failure, but it is not applied to the dynamic environment where the operation is arriving at any time [17].To sum up, firstly, FJSSP has natural dynamics. When establishing flexible job shop scheduling model, work efficiency is usually measured by the completion time of the task to be processed, and the stability of the system is measured by the machine load state of the workshop. Although the existing mathematical model can cope with the change in some working environments, they still cannot deal with the random arrival of task sequence, the departure of completed tasks, sudden machine failure, and the repair of failed machines at the same time. Secondly, the efficiency and stability of flexible workshop systems are mutually exclusive; therefore, in the essence of mathematics, FJSSP is a dynamic multi-objective optimization problem [18]. Compared with the method of transforming multiple targets into a single objective through weighted summation, multi-objective evolutionary algorithm can simultaneously consider efficiency and stability, and it is the main method to solve flexible job shop scheduling. Thus, the performance of multi-objective algorithm is also the key to solve DJSSP. In order to get a scheduling scheme with both efficiency and stability in dynamic environment, it is necessary to establish a mathematical model conforming to the dynamic characteristics of DFJSSP and a dynamic multi-objective evolutionary algorithm with excellent performance.Based on the above analysis, this paper proposes a flexible shop scheduling method based on dynamic multi-objective squirrel algorithm. The main innovations are as follows: First, in consideration of the changes in an actual workshop environment, including the random arrival of task sequences, the departure of completed tasks, sudden machine failure, and the repair of failed machines, a new dynamic multi-objective flexible shop scheduling model is proposed, with the completion time, load balance (LB), and fault rescheduling deviation as the objective functions, to address working efficiency and system stability. Second, in order to effectively solve the above established mathematical model, an improved dynamic multi-objective squirrel search algorithm based on decomposition is proposed in this paper. It adopts operation and machine coding for individual coding and improves individual evolutionary strategy of SSA according to the characteristics of FJSSP. In addition, a new dynamic processing technology including the establishment and update of the external population and the initialization of the population at the time of rescheduling is proposed, which can respond quickly to changes by regenerating initial population at rescheduling time.The remaining sections are arranged as follows: Section2 introduces the establishment process of the mathematical model of dynamic multi-objective flexible shop scheduling problem; the third part introduces the principle of the flexible shop scheduling method based on dynamic multi-objective squirrel search algorithm; the fourth part gives the experimental results and analysis; and the fifth part summarizes the whole paper.


## 2. The Establishment of a Mathematical Model for Dynamic Multi-Objective Flexible Job Shop Scheduling Problem

### 2.1. Description of Flexible Job Shop Scheduling Problem

The flexible job shop scheduling problem can be described as: there aren jobs J = {J1, J2, …, Jn}, each operation Ji is composed of ni processes, and the number of multi-objective steps per operation is ni. The processing time tij of each process is subject to certain distribution. The purpose of the FJSSP is to assign the operation machine to each process, so that the process of arriving at the workshop is processed in a certain order, and after processing is finished, the operation machine leaves the workshop. A new mathematical model for flexible job shop scheduling problem is established to realize flexible job shop dynamic scheduling. Firstly, the variables involved in flexible job shop scheduling problem are introduced as follows:t1: rescheduling cycle, time t = ntl (n is a positive integer), update the state of the workshop, including new task, machine idle time, etc.tb: the time when the machine breaks down.tr: the time for recovering from machinery breakdowns.Mtbf: the average breakdown time.Mttr: the average recovery time.Ji: the task i-th that arrives at the workshop.Nl: the number of tasks arriving at the workshop before the time of ntl.ni: the number of Ji’s processes.O (i, j): the j-th process of task Ji.m: the total number of machines in workshop.M: the set of machines in workshop, M = {M1, M2,…, Mm}.M (i, j): a set of all machines that can handle O (i, j).F (i, j): the number of machines contained in the alternative machine set M (i, j) of O (i, j), flexible degree.t (i, j, k): the processing time of O (i, j) on machine Mk.Si: the beginning time of job i.Ci: the completion time of job i. S (i, j): the beginning time of process O (i, j).C (i, j): the completion time of process O (i, j).Ck_last: O (i, j) is processed by Mk, the completion time of the last procedure of Mk processing before O (i, j) starts.S (i, j)∗: the beginning time of Oij in rescheduling processes.C (i, j)∗: the completion time of Oij in rescheduling processes.Ik: the earliest available time of machine Mk;Lk: the total working time of machine Mk;Task scheduling requirements for Flexible Job Shop:(1)
At the initial time, all machines are available, i.e.,t = 0, Ik = 0.(2)
A process can only be processed by one machine at a time, that is,O (i, j) can only be processed by one machine in M (i, j) at a time.(3)
One machine can handle only one process at a time.(4)
There is no precedence constraint between different tasks.(5)
The process in the same task has no priority, that is,O (i, j-1) can only deal with O (i, j) after processing.(6)
All processes have no priority for the same machine, that is, the machine must deal with the current process before it can handle the next process.(7)
When the machine is not out of order, the operation system is scheduled at a fixed cycle according to the completion and arrival of the operation. When the machine breaks down, no matter whether the fault machine is executing the procedure or whether the procedure is to be executed soon, in the rescheduling plan, all the remaining procedures corresponding to the fault machine are arranged to be executed by the nonfault machine. After the fault is fixed, the repaired machine can continue to perform job scheduling.For the periodic rescheduling time ntl, the rescheduling time tb and the task to be processed at the recovery time of rescheduling tr, if the procedure O (i, j) is processed on machine Mk, then the beginning time S (i, j) and the ending time C (i, j) of O (i, j) are, respectively, shown in formulas (1) and (2). The beginning time Si and the ending time Ci of Ji are shown in formulas (3) and (4), respectively.(1)Sij=maxntl,Ik,j=1,maxCi,j−1,Ik,j>1.Among them:Ik=maxntl,tb,tr,Ck_last,(2)Ci,j=Si,j+ti,j,k,(3)Si=maxSi,1,…,Si,ni,(4)Ci=maxCi,1,…,Ci,ni.The scheduling example in [19] is illustrated to have an enhanced understanding of the rules of flexible job shop scheduling. As shown in Table 1, “/” means that the process cannot be executed on the corresponding machine. Figure 1 is a Gantt chart corresponding to a specific scheduling plan for the data in Table 1.Table 1
Six task scheduling examples.
Job numberProcess numberMachine number and corresponding processing time of each process12345611234———12—3—24—13145———213—5—2—2243——6—23——4—7113156————32—4—35—33——13—912419—79——42—6—4—5431—3——3Figure 1
Scheduling plan 1.As shown in Figure1, when t = 0, O31, O41, and O21 are treated using M1, M3, and M5, respectively. Given that O31, O41, and O21 are the first processes of J3, J4, and J2, respectively, all machines are idle when t = 0; thus, S31 = S41 = S21 = 0. O11 is selected to be treated using M1. Although O11 is the first step of J1, given no priority constraint among different tasks, M1 has started processing O31 when t = 0. O11 can start after O31 ends; therefore, S11 = I1 = C31 = S31 + t311 = 5. O12 is processed using M4. Given that the process in the same task has no priority, O12 can only start after O11 ends, and O11 ends at t = C11 = S11 + t111 = 7. However, when t = 7, M4 handles O32, and M4 is idle after O32 is finished, i.e., I4=C32 = S32 + t324 = 8; consequently, S12 = I4 = 8. O13 is processed using M2. Although M2 has been idle at t = 5 when O22 ends, O12 has not started yet when t = 5, and the process in the same task has no priority. Accordingly, S13 = C12 = S12 + t124 = 10.


### 2.2. Characteristic Analysis of FJSSP

For the scheduling problem of flexible job workshops, even for exactly the same scheduling tasks, multiple scheduling schemes often exist. Figure2 is a Gantt chart corresponding to Table 1 and another scheduling scheme different from Figure 1.Figure 2
Scheduling plan 2.For FJSSP, the efficiency and stability of the system are usually considered. On this basis, we compare and analyze the scheduling schemes in Figures1 and 2 from these two perspectives. For the tasks in Table 1, the final completion time of the two scheduling schemes is 17, indicating that the efficiency of the two scheduling schemes is equivalent. However, in the scheduling scheme corresponding to Figure 1, all machines participate in the scheduling process, and the machine load is balanced. For the scheduling scheme in Figure 2, M6 is not involved in the scheduling process. All processes are completed using M1–M5, and the LB of the machine is poor. The unbalanced load of machines in the workshop may cause some machines to be idle and others to be in working state for a long time. The machines in working state for a long time are prone to failure, thus affecting the system stability. Therefore, compared with the scheduling scheme in Figure 2, the scheduling scheme in Figure 1 is better while ensuring efficiency and considering system stability.The machine failure mentioned above is also one of the important factors that affect the system stability, and the specific analysis is as follows. When a machine in the workshop breaks down, the process in the same task has no priority, except for the process that is being implemented or has not been implemented on the failed machine.O (i, j) can only be processed after O (i, j-1) is processed, and the processes arranged on no-fault machines in the original scheduling plan will also be affected. Figure 2 is regarded as an example, i.e., if M4 breaks down at t = 9. Process O (1, 2) being handled on M4 and process O (4, 2) that has not yet been handled on M4 need to be rescheduled. O (1, 3) and O (4, 3) cannot be executed in accordance with the original scheduling plan due to the changes in O (1, 2) and O (4, 2). Although O (2, 3) in the original scheduling scheme is unaffected by the failed machine, the machine failure changes the system state, and the scheduling of O (2, 3) will also have a new impact on the system state. Nonetheless, the workshop still maintains an efficient and stable operation at the time of failure. Except for the processes that have been started on no-fault machines and the process that has been completed on the fault machine, all the other processes need to be rescheduled. At the time of recovery, all the remaining untreated processes need to be rescheduled, except for the processes that have been completed and started. The smaller the deviation between the rescheduling scheme and the original scheduling scheme is, the smaller the system changes, and the better the stability will be. Conversely, the greater the difference between the new and old scheduling schemes is, the worse the system stability will be.To sum up, if we want to ensure the operation efficiency, the most efficient machines in all processes can lead to some machines being idle for a long time, while some machines are in a state of work for a long time, resulting in unbalanced load. If we want to ensure the LB of machines, some jobs may not be processed by the most efficient machines, resulting in low efficiency. Some processes do not match the most efficient machines, and the efficiency of the machines may still be reduced. If the work efficiency is to be guaranteed, the new scheduling scheme may be larger than the historical scheduling scheme, but the system stability will be worse.


### 2.3. Dynamic Multi-Objective Mathematical Model of FJSSP

Subsection2.2 indicates that operation efficiency and system stability are conflicted. To consider the efficiency and stability of the workshop at the same time, this paper regards the completion time, LB, and rescheduling deviation as the objective functions and establishes a multi-objective optimization mathematical model. The completion time is used to evaluate the workshop efficiency, while LB and fault rescheduling deviation are used to measure the system stability. The details are as follows:


#### 2.3.1. Work Efficiency

A short completion time means high work efficiency. To ensure the workshop work efficiency, this paper regards the shortest completion time as the optimization objective, and the objective function is shown in Formula (5).(5)minCT=maxCi,i=1,2,…,Nl.


#### 2.3.2. System Stability

This study measures the system stability from two aspects: the machine LB and rescheduling deviation. LB is measured using the variance of machine utilization shown in Formula (6); the smaller the variance is, the more balanced the machine load and the better the system stability will be. When machines break down or recover, the average deviation (AD) between the new and old scheduling schemes shown in Formula (8) indicates the rescheduling deviation. Small AD indicates a small difference between the rescheduling and original scheduling schemes, and improved stability.(6)minLB=1m∑k=1mLkmaxL1,…,Lm−1m∑k=1mLkmaxL1,…,Lm2.In (6),(7)Lk=∑i=1Nl∑j=1nixi,j,k∗ti,j,k,xi,j,k=1,Oi,jis handle usingMk,0,other.The smaller the LB is, the more balanced the system will be.(8)minAD=∑i=1Nl∑j=1niSi,j−S∗i,j+Ci,j−C∗i,jnres.In (8), nres is the total number of operations to be rescheduled; for the operations that have started or been completed on the working machines, Si,j=S∗i,j and Ci,j=C∗i,j.In summary, to consider the efficiency and stability of the system, a dynamic multi-objective mathematical model of FJSSP is established:(9)minCT=maxCi,i=1,2,…,Nl,minLB=1m∑k=1mLkmaxL1,…,Lm−1m∑m1LkmaxL1,…,Lm2,minAD=∑i=1Nl∑j=1niSi,j−S∗i,j+Ci,j−C∗i,jnres.In the mathematical model above, the first objective function guarantees the shortest completion time of all tasks arriving at timentl; the second objective function guarantees that all machines will be loaded as evenly as possible until ntl; the third objective function ensures that when machines break down or get back to work, the deviation between the rescheduling scheme and the original scheduling scheme is the smallest. When no machine breaks down or a machine is not recovered, only the objective functions one and two are considered, and the mathematical model is considered a two-objective optimization problem. If a machine breaks down or the faulty machine is recovered, the three objectives are all needed to be optimized, and the mathematical model is regarded as a three-objective optimization problem.Compared with existing mathematical models of FJSSP, the mathematical model established in this paper considers the dynamic characteristics of the departure of completed tasks, the arrival of new tasks, the failure of workshop machines, and the repair of machine faults. The mathematical model adjusts the optimization objective automatically in accordance with the machine state, which will shorten the working time and balance the load of the machine when no machine breaks down or a machine is not recovered. Meanwhile, the established mathematical model minimizes the deviation of the new and old scheduling schemes when a machine breaks down or the faulty machine is recovered, which gives consideration to the working efficiency and system stability in real time.


## 2.1. Description of Flexible Job Shop Scheduling Problem

The flexible job shop scheduling problem can be described as: there aren jobs J = {J1, J2, …, Jn}, each operation Ji is composed of ni processes, and the number of multi-objective steps per operation is ni. The processing time tij of each process is subject to certain distribution. The purpose of the FJSSP is to assign the operation machine to each process, so that the process of arriving at the workshop is processed in a certain order, and after processing is finished, the operation machine leaves the workshop. A new mathematical model for flexible job shop scheduling problem is established to realize flexible job shop dynamic scheduling. Firstly, the variables involved in flexible job shop scheduling problem are introduced as follows:t1: rescheduling cycle, time t = ntl (n is a positive integer), update the state of the workshop, including new task, machine idle time, etc.tb: the time when the machine breaks down.tr: the time for recovering from machinery breakdowns.Mtbf: the average breakdown time.Mttr: the average recovery time.Ji: the task i-th that arrives at the workshop.Nl: the number of tasks arriving at the workshop before the time of ntl.ni: the number of Ji’s processes.O (i, j): the j-th process of task Ji.m: the total number of machines in workshop.M: the set of machines in workshop, M = {M1, M2,…, Mm}.M (i, j): a set of all machines that can handle O (i, j).F (i, j): the number of machines contained in the alternative machine set M (i, j) of O (i, j), flexible degree.t (i, j, k): the processing time of O (i, j) on machine Mk.Si: the beginning time of job i.Ci: the completion time of job i. S (i, j): the beginning time of process O (i, j).C (i, j): the completion time of process O (i, j).Ck_last: O (i, j) is processed by Mk, the completion time of the last procedure of Mk processing before O (i, j) starts.S (i, j)∗: the beginning time of Oij in rescheduling processes.C (i, j)∗: the completion time of Oij in rescheduling processes.Ik: the earliest available time of machine Mk;Lk: the total working time of machine Mk;Task scheduling requirements for Flexible Job Shop:(1)
At the initial time, all machines are available, i.e.,t = 0, Ik = 0.(2)
A process can only be processed by one machine at a time, that is,O (i, j) can only be processed by one machine in M (i, j) at a time.(3)
One machine can handle only one process at a time.(4)
There is no precedence constraint between different tasks.(5)
The process in the same task has no priority, that is,O (i, j-1) can only deal with O (i, j) after processing.(6)
All processes have no priority for the same machine, that is, the machine must deal with the current process before it can handle the next process.(7)
When the machine is not out of order, the operation system is scheduled at a fixed cycle according to the completion and arrival of the operation. When the machine breaks down, no matter whether the fault machine is executing the procedure or whether the procedure is to be executed soon, in the rescheduling plan, all the remaining procedures corresponding to the fault machine are arranged to be executed by the nonfault machine. After the fault is fixed, the repaired machine can continue to perform job scheduling.For the periodic rescheduling time ntl, the rescheduling time tb and the task to be processed at the recovery time of rescheduling tr, if the procedure O (i, j) is processed on machine Mk, then the beginning time S (i, j) and the ending time C (i, j) of O (i, j) are, respectively, shown in formulas (1) and (2). The beginning time Si and the ending time Ci of Ji are shown in formulas (3) and (4), respectively.(1)Sij=maxntl,Ik,j=1,maxCi,j−1,Ik,j>1.Among them:Ik=maxntl,tb,tr,Ck_last,(2)Ci,j=Si,j+ti,j,k,(3)Si=maxSi,1,…,Si,ni,(4)Ci=maxCi,1,…,Ci,ni.The scheduling example in [19] is illustrated to have an enhanced understanding of the rules of flexible job shop scheduling. As shown in Table 1, “/” means that the process cannot be executed on the corresponding machine. Figure 1 is a Gantt chart corresponding to a specific scheduling plan for the data in Table 1.Table 1
Six task scheduling examples.
Job numberProcess numberMachine number and corresponding processing time of each process12345611234———12—3—24—13145———213—5—2—2243——6—23——4—7113156————32—4—35—33——13—912419—79——42—6—4—5431—3——3Figure 1
Scheduling plan 1.As shown in Figure1, when t = 0, O31, O41, and O21 are treated using M1, M3, and M5, respectively. Given that O31, O41, and O21 are the first processes of J3, J4, and J2, respectively, all machines are idle when t = 0; thus, S31 = S41 = S21 = 0. O11 is selected to be treated using M1. Although O11 is the first step of J1, given no priority constraint among different tasks, M1 has started processing O31 when t = 0. O11 can start after O31 ends; therefore, S11 = I1 = C31 = S31 + t311 = 5. O12 is processed using M4. Given that the process in the same task has no priority, O12 can only start after O11 ends, and O11 ends at t = C11 = S11 + t111 = 7. However, when t = 7, M4 handles O32, and M4 is idle after O32 is finished, i.e., I4=C32 = S32 + t324 = 8; consequently, S12 = I4 = 8. O13 is processed using M2. Although M2 has been idle at t = 5 when O22 ends, O12 has not started yet when t = 5, and the process in the same task has no priority. Accordingly, S13 = C12 = S12 + t124 = 10.


## 2.2. Characteristic Analysis of FJSSP

For the scheduling problem of flexible job workshops, even for exactly the same scheduling tasks, multiple scheduling schemes often exist. Figure2 is a Gantt chart corresponding to Table 1 and another scheduling scheme different from Figure 1.Figure 2
Scheduling plan 2.For FJSSP, the efficiency and stability of the system are usually considered. On this basis, we compare and analyze the scheduling schemes in Figures1 and 2 from these two perspectives. For the tasks in Table 1, the final completion time of the two scheduling schemes is 17, indicating that the efficiency of the two scheduling schemes is equivalent. However, in the scheduling scheme corresponding to Figure 1, all machines participate in the scheduling process, and the machine load is balanced. For the scheduling scheme in Figure 2, M6 is not involved in the scheduling process. All processes are completed using M1–M5, and the LB of the machine is poor. The unbalanced load of machines in the workshop may cause some machines to be idle and others to be in working state for a long time. The machines in working state for a long time are prone to failure, thus affecting the system stability. Therefore, compared with the scheduling scheme in Figure 2, the scheduling scheme in Figure 1 is better while ensuring efficiency and considering system stability.The machine failure mentioned above is also one of the important factors that affect the system stability, and the specific analysis is as follows. When a machine in the workshop breaks down, the process in the same task has no priority, except for the process that is being implemented or has not been implemented on the failed machine.O (i, j) can only be processed after O (i, j-1) is processed, and the processes arranged on no-fault machines in the original scheduling plan will also be affected. Figure 2 is regarded as an example, i.e., if M4 breaks down at t = 9. Process O (1, 2) being handled on M4 and process O (4, 2) that has not yet been handled on M4 need to be rescheduled. O (1, 3) and O (4, 3) cannot be executed in accordance with the original scheduling plan due to the changes in O (1, 2) and O (4, 2). Although O (2, 3) in the original scheduling scheme is unaffected by the failed machine, the machine failure changes the system state, and the scheduling of O (2, 3) will also have a new impact on the system state. Nonetheless, the workshop still maintains an efficient and stable operation at the time of failure. Except for the processes that have been started on no-fault machines and the process that has been completed on the fault machine, all the other processes need to be rescheduled. At the time of recovery, all the remaining untreated processes need to be rescheduled, except for the processes that have been completed and started. The smaller the deviation between the rescheduling scheme and the original scheduling scheme is, the smaller the system changes, and the better the stability will be. Conversely, the greater the difference between the new and old scheduling schemes is, the worse the system stability will be.To sum up, if we want to ensure the operation efficiency, the most efficient machines in all processes can lead to some machines being idle for a long time, while some machines are in a state of work for a long time, resulting in unbalanced load. If we want to ensure the LB of machines, some jobs may not be processed by the most efficient machines, resulting in low efficiency. Some processes do not match the most efficient machines, and the efficiency of the machines may still be reduced. If the work efficiency is to be guaranteed, the new scheduling scheme may be larger than the historical scheduling scheme, but the system stability will be worse.


## 2.3. Dynamic Multi-Objective Mathematical Model of FJSSP

Subsection2.2 indicates that operation efficiency and system stability are conflicted. To consider the efficiency and stability of the workshop at the same time, this paper regards the completion time, LB, and rescheduling deviation as the objective functions and establishes a multi-objective optimization mathematical model. The completion time is used to evaluate the workshop efficiency, while LB and fault rescheduling deviation are used to measure the system stability. The details are as follows:


### 2.3.1. Work Efficiency

A short completion time means high work efficiency. To ensure the workshop work efficiency, this paper regards the shortest completion time as the optimization objective, and the objective function is shown in Formula (5).(5)minCT=maxCi,i=1,2,…,Nl.


### 2.3.2. System Stability

This study measures the system stability from two aspects: the machine LB and rescheduling deviation. LB is measured using the variance of machine utilization shown in Formula (6); the smaller the variance is, the more balanced the machine load and the better the system stability will be. When machines break down or recover, the average deviation (AD) between the new and old scheduling schemes shown in Formula (8) indicates the rescheduling deviation. Small AD indicates a small difference between the rescheduling and original scheduling schemes, and improved stability.(6)minLB=1m∑k=1mLkmaxL1,…,Lm−1m∑k=1mLkmaxL1,…,Lm2.In (6),(7)Lk=∑i=1Nl∑j=1nixi,j,k∗ti,j,k,xi,j,k=1,Oi,jis handle usingMk,0,other.The smaller the LB is, the more balanced the system will be.(8)minAD=∑i=1Nl∑j=1niSi,j−S∗i,j+Ci,j−C∗i,jnres.In (8), nres is the total number of operations to be rescheduled; for the operations that have started or been completed on the working machines, Si,j=S∗i,j and Ci,j=C∗i,j.In summary, to consider the efficiency and stability of the system, a dynamic multi-objective mathematical model of FJSSP is established:(9)minCT=maxCi,i=1,2,…,Nl,minLB=1m∑k=1mLkmaxL1,…,Lm−1m∑m1LkmaxL1,…,Lm2,minAD=∑i=1Nl∑j=1niSi,j−S∗i,j+Ci,j−C∗i,jnres.In the mathematical model above, the first objective function guarantees the shortest completion time of all tasks arriving at timentl; the second objective function guarantees that all machines will be loaded as evenly as possible until ntl; the third objective function ensures that when machines break down or get back to work, the deviation between the rescheduling scheme and the original scheduling scheme is the smallest. When no machine breaks down or a machine is not recovered, only the objective functions one and two are considered, and the mathematical model is considered a two-objective optimization problem. If a machine breaks down or the faulty machine is recovered, the three objectives are all needed to be optimized, and the mathematical model is regarded as a three-objective optimization problem.Compared with existing mathematical models of FJSSP, the mathematical model established in this paper considers the dynamic characteristics of the departure of completed tasks, the arrival of new tasks, the failure of workshop machines, and the repair of machine faults. The mathematical model adjusts the optimization objective automatically in accordance with the machine state, which will shorten the working time and balance the load of the machine when no machine breaks down or a machine is not recovered. Meanwhile, the established mathematical model minimizes the deviation of the new and old scheduling schemes when a machine breaks down or the faulty machine is recovered, which gives consideration to the working efficiency and system stability in real time.


## 2.3.1. Work Efficiency

A short completion time means high work efficiency. To ensure the workshop work efficiency, this paper regards the shortest completion time as the optimization objective, and the objective function is shown in Formula (5).(5)minCT=maxCi,i=1,2,…,Nl.


## 2.3.2. System Stability

This study measures the system stability from two aspects: the machine LB and rescheduling deviation. LB is measured using the variance of machine utilization shown in Formula (6); the smaller the variance is, the more balanced the machine load and the better the system stability will be. When machines break down or recover, the average deviation (AD) between the new and old scheduling schemes shown in Formula (8) indicates the rescheduling deviation. Small AD indicates a small difference between the rescheduling and original scheduling schemes, and improved stability.(6)minLB=1m∑k=1mLkmaxL1,…,Lm−1m∑k=1mLkmaxL1,…,Lm2.In (6),(7)Lk=∑i=1Nl∑j=1nixi,j,k∗ti,j,k,xi,j,k=1,Oi,jis handle usingMk,0,other.The smaller the LB is, the more balanced the system will be.(8)minAD=∑i=1Nl∑j=1niSi,j−S∗i,j+Ci,j−C∗i,jnres.In (8), nres is the total number of operations to be rescheduled; for the operations that have started or been completed on the working machines, Si,j=S∗i,j and Ci,j=C∗i,j.In summary, to consider the efficiency and stability of the system, a dynamic multi-objective mathematical model of FJSSP is established:(9)minCT=maxCi,i=1,2,…,Nl,minLB=1m∑k=1mLkmaxL1,…,Lm−1m∑m1LkmaxL1,…,Lm2,minAD=∑i=1Nl∑j=1niSi,j−S∗i,j+Ci,j−C∗i,jnres.In the mathematical model above, the first objective function guarantees the shortest completion time of all tasks arriving at timentl; the second objective function guarantees that all machines will be loaded as evenly as possible until ntl; the third objective function ensures that when machines break down or get back to work, the deviation between the rescheduling scheme and the original scheduling scheme is the smallest. When no machine breaks down or a machine is not recovered, only the objective functions one and two are considered, and the mathematical model is considered a two-objective optimization problem. If a machine breaks down or the faulty machine is recovered, the three objectives are all needed to be optimized, and the mathematical model is regarded as a three-objective optimization problem.Compared with existing mathematical models of FJSSP, the mathematical model established in this paper considers the dynamic characteristics of the departure of completed tasks, the arrival of new tasks, the failure of workshop machines, and the repair of machine faults. The mathematical model adjusts the optimization objective automatically in accordance with the machine state, which will shorten the working time and balance the load of the machine when no machine breaks down or a machine is not recovered. Meanwhile, the established mathematical model minimizes the deviation of the new and old scheduling schemes when a machine breaks down or the faulty machine is recovered, which gives consideration to the working efficiency and system stability in real time.


## 3. Dynamic Multi-Objective SSA For Solving FJSSP

When solving a dynamic multi-objective optimization problem, the dynamic environment is divided into several transient environments; a dynamic processing technology is used to deal with environmental changes, and a multi-objective algorithm is used to solve static multi-objective optimization problems in a transient environment. Squirrel Search Algorithm (SSA) is a new swarm intelligence evolutionary algorithm [20]. Compared with traditional evolutionary algorithms, SSA has higher convergence speed and accuracy. Wang et al. propose an Improved Squirrel Search Algorithm for global function optimization (ISSA), which improves the convergence of SSA. Besides, Zhang et al. proposed MOEA/D, which can solve the multi-objective optimization problem in a transient environment and has high solving speed and efficiency [21]. Therefore, to expand the application of SSA in the engineering field, this paper regards ISSA as the core evolutionary strategy, considers the multi-objective framework of MOEA/D, and integrates a dynamic processing technology to solve FJSSP. Figure 3 is the flowchart of the dynamic multi-objective SSA for solving FJSSP.Figure 3
Flowchart for solving FJSSP.Figure3 illustrates that at the end of each transient environment, the final scheduling scheme under the current environment in the nondominated solution set should be selected, and the scheduling under the new environment is based on the selected scheduling scheme. In this study, the TOPSIS method [22] is used to determine the final scheduling scheme for each transient environment. In addition, considering that FJSSP is a discrete optimization problem, this study adopts the individual coding method [23]. In accordance with the characteristics of FJSSP, the dynamic processing technology and evolution strategy for FJSSP are designed as follows.


### 3.1. Individual Coding Method

The individual coding method includes two parts: operation and machine coding. The operation coding is determined using the job number to be processed at the rescheduling time. OperationO (i, j) is represented by its task number Ji. The first occurrence of Ji corresponds to operation O (i, 1), the second occurrence of Ji corresponds to operation O (i, 2), and so on. The j-th occurrence of Ji corresponds to operation O (i, j); therefore, the frequency of occurrence of Ji is the same as the total operation number of Ji. Each operation code corresponds to one machine code. A machine is selected from the candidate machine set of O (i, j) randomly, and the number of the selected machine is the machine code corresponding to O (i, j).The task data in Table1 are regarded as an example. The complete code corresponding to the scheduling scheme shown in Figure 1 is 342133221144/135145264243, i.e., O31⟶M1, O41⟶M3, O21⟶M5, O11⟶M1, O32⟶M4, O33⟶M5, O22⟶M2, O23⟶M6, O12⟶M4, O13⟶M2, O42⟶M4, O43⟶M3.


### 3.2. Dynamic Processing Technology

#### 3.2.1. Establishment and Renewal of External Population

The solution principle of MOEA/D indicates that when offspring individualy′cannot replace any individual in the neighbourhood, y′ is abandoned directly. Thus, this study establishes an external population Ey for each individual to make the abandoned y′participate in the evolution. The specific way is as follows. An external population with the same size is set as the neighbourhood T. num_alt is used to record the number of individuals in the neighbourhood replaced with y′. y′, whose num_alt is equal to 0, enters the external population.When the scale ofEy is smaller than the upper limit T, if num_alt = 0, the corresponding y′ enters Ey; if 0 < num_alt ≤T/2, Ey remains unchanged; if num_alt > T/2, Ey is emptied because the current subproblem and its neighbour subproblems are far from the optimal solution.When the scale ofEy is up to the upper limit T, if num_alt = 0, the population has evolved to a certain extent, and the current individual is close to its neighbour individual. To maintain the population diversity, the individual with the smallest Euclidean distance to the current individual in Ey is deleted, and y′ enters Ey.


#### 3.2.2. Generation of Initial Population at Rescheduling Time

Two cases needing to reschedule tasks are considered in this paper. The first one is related to workshop working time, which is called periodic rescheduling. The second one is related to machine state, including fault and fault recovery rescheduling. In consideration of the two situations above, two different dynamic processing technologies are designed, and the details are as follows.At the time of periodic reschedulingntl, the new tasks are recorded, the machine state is updated, and the initial population under the new period is generated in accordance with the coding method in Subsection 3.1.If a machine breaks down or operates again, i.e.,t = tb or t = tr, the new population of tb or tr is generated in accordance with the implementation of the original scheduling scheme. The details are as follows. If t = tb, in the current scheduling scheme, operations to be rescheduled contain all the unfinished operations arranged on the broken machine and all the operations that have not started until tb. If t = tr, in the current scheduling scheme, operations to be rescheduled contain all the operations that have not started until tr. The set of all operations to be rescheduled is named Ore. When t = tb or t = tr, for each individual in the original population, if Ey = ∅, all operations in Ore should be reinitialized as the new individual in the new environment in accordance with the coding method above; if Ey ≠ ∅, for each scheduling scheme in Ey, the set of operations that need to be rescheduled is recorded and named Oey; if memory individuals with exactly the same Oey and Ore exist, one is selected randomly, the scheduling order of all operations is kept in Oey, and the corresponding machine code is mutated and regarded as the initial individual in the new environment. Given the high similarity between the scheduling scheme in memory population and the currently executing scheduling scheme, the new individuals generated using memory individuals are more suitable for the current working state, which is conducive to the system stability.


### 3.3. Core Evolutionary Strategy

In the scheduling process of each transient environment, the core evolutionary strategy SSA is used to update the population. An individual contains operation and machine codes, but the machine code is determined by the operation code. Therefore, the updating strategy of the population is aimed only at the operation code, rather than the machine code. The specific updating process is described below.


#### 3.3.1. Related Variables

Fd: Learning target in accordance with the standard SSA; the details have been introduced in Reference [20].n_same: When the operation codes of FSi and Fd are matched one by one, n_same is the total number of the same operation codes.n_jl: Total number of new jobs at tl.Fr1, Fr2: If Ey = ∅, Fr1 and Fr2 are two individuals different from Fd and FSi randomly selected in their neighbor; if Ey ≠ ∅, Fr1 is any individual in its neighborhood different from FSi, and Fr2 is randomly selected in Ey.Scgand Smin are calculated according to Reference [20], and the winter search strategy is selected whenScg>Smin.(1)
Winter search strategy①
No predators exist whenr>Pdp.The jump search method is selected whenn_same > n_jl/2, and the progressive search method is decided when n_same ≤ n_jl/2.The jump search method:FSi and Fd have high similarity when n_same > n_jl/2, and the individual is updated using Formula (10).(10)FSig+1=FSig+dg×Gc×Fdt−FSit.In the formula above, “[.]” means to carry out rounding operation, which ensures that the individual code of each dimension is a positive integer.dg and Gc have been introduced in Reference [20].The progressive search method:FSi and Fd have low similarity when n_same ≤ n_jl/2. To maintain population diversity, rds dimensions are selected randomly in accordance with Formula (11) and then rearranged also randomly.(11)rds=r×n_jl−n_same.In the formula above,r is a random number between 0 and 1; the lower the similarity between FSi and Fd is, the more dimensions can be rearranged, and the search space can be developed more sufficiently.②
A predator occurs whenr≤Pdp.FSi is considered dead, and the offspring is generated via Fr1 and Fr2 in accordance with the POX introduced in Reference [24].(2)
Summer search strategy①
No predators exist whenr>Pdp.The jump search method is selected whenn_same > n_jl/2, and the progressive search method is chosen when n_same ≤ n_jl/2.The jump search method:FSi and Fd have high similarity when n_same > n_jl/2, and the individual is updated using Formula (12).(12)FSit+1=Fdt+dg×Gc×FSit−Fdt.Formula (12) regards Fd as the basic vector, improves the convergence speed at the beginning of environmental change, and deeply develops the search space after the population evolves to a certain extent.The progressive search method is the same as that in the winter search method. Ifn_same ≤ n_jl/2, rds dimensions are selected randomly in accordance with Formula (10) and then rearranged also randomly.②
A predator occurs whenr≤Pdp.FSi is considered dead, and the offspring is generated using Fr1 and Fr2 in accordance with the POX introduced in Reference [24].FJSSP requires that the value of each dimension is the job number corresponding to the operation, and the total occurrence time of each job number should be the same as its total operations. Therefore, the operation code of the offspring obtained using the updating strategy above should be modified. The task in Table1 is regarded as an example to introduce the modification process, and the details are as follows.The redundant job numbers are determined and recorded in vector “more.” If numberi of job Ji occurs ni + c times, then i occurs in “more” c times. Figure 4 is considered an example. For the problem in Table 1, the operation code of the offspring is 134312214131, more = {1, 1}.Figure 4
Modification of the operation code.The missing job numbers are identified and recorded in vector “less.” If number i of job Ji occurs ni-c times, then i occurs in “less” c times. Figure 4 is regarded as an example. For the problem in Table 1, the operation code of the offspring is 134312214131, less = {2, 4}.The redundant job numbers occurring in “more” in the offspring are selected randomly to replace the missing job numbers in “less.” All elements in “less” are arranged randomly, and the modification is completed. Figure4 is regarded as an example, the 5-th dimension of the offspring operation code changes from 1 to 4, and the 10th dimension changes from 1 to 2.An operation machine is selected randomly in the alternative machine set after the operation code of each offspring is determined, and the operation code constitutes a complete offspring scheduling scheme.


## 3.1. Individual Coding Method

The individual coding method includes two parts: operation and machine coding. The operation coding is determined using the job number to be processed at the rescheduling time. OperationO (i, j) is represented by its task number Ji. The first occurrence of Ji corresponds to operation O (i, 1), the second occurrence of Ji corresponds to operation O (i, 2), and so on. The j-th occurrence of Ji corresponds to operation O (i, j); therefore, the frequency of occurrence of Ji is the same as the total operation number of Ji. Each operation code corresponds to one machine code. A machine is selected from the candidate machine set of O (i, j) randomly, and the number of the selected machine is the machine code corresponding to O (i, j).The task data in Table1 are regarded as an example. The complete code corresponding to the scheduling scheme shown in Figure 1 is 342133221144/135145264243, i.e., O31⟶M1, O41⟶M3, O21⟶M5, O11⟶M1, O32⟶M4, O33⟶M5, O22⟶M2, O23⟶M6, O12⟶M4, O13⟶M2, O42⟶M4, O43⟶M3.


## 3.2. Dynamic Processing Technology

### 3.2.1. Establishment and Renewal of External Population

The solution principle of MOEA/D indicates that when offspring individualy′cannot replace any individual in the neighbourhood, y′ is abandoned directly. Thus, this study establishes an external population Ey for each individual to make the abandoned y′participate in the evolution. The specific way is as follows. An external population with the same size is set as the neighbourhood T. num_alt is used to record the number of individuals in the neighbourhood replaced with y′. y′, whose num_alt is equal to 0, enters the external population.When the scale ofEy is smaller than the upper limit T, if num_alt = 0, the corresponding y′ enters Ey; if 0 < num_alt ≤T/2, Ey remains unchanged; if num_alt > T/2, Ey is emptied because the current subproblem and its neighbour subproblems are far from the optimal solution.When the scale ofEy is up to the upper limit T, if num_alt = 0, the population has evolved to a certain extent, and the current individual is close to its neighbour individual. To maintain the population diversity, the individual with the smallest Euclidean distance to the current individual in Ey is deleted, and y′ enters Ey.


### 3.2.2. Generation of Initial Population at Rescheduling Time

Two cases needing to reschedule tasks are considered in this paper. The first one is related to workshop working time, which is called periodic rescheduling. The second one is related to machine state, including fault and fault recovery rescheduling. In consideration of the two situations above, two different dynamic processing technologies are designed, and the details are as follows.At the time of periodic reschedulingntl, the new tasks are recorded, the machine state is updated, and the initial population under the new period is generated in accordance with the coding method in Subsection 3.1.If a machine breaks down or operates again, i.e.,t = tb or t = tr, the new population of tb or tr is generated in accordance with the implementation of the original scheduling scheme. The details are as follows. If t = tb, in the current scheduling scheme, operations to be rescheduled contain all the unfinished operations arranged on the broken machine and all the operations that have not started until tb. If t = tr, in the current scheduling scheme, operations to be rescheduled contain all the operations that have not started until tr. The set of all operations to be rescheduled is named Ore. When t = tb or t = tr, for each individual in the original population, if Ey = ∅, all operations in Ore should be reinitialized as the new individual in the new environment in accordance with the coding method above; if Ey ≠ ∅, for each scheduling scheme in Ey, the set of operations that need to be rescheduled is recorded and named Oey; if memory individuals with exactly the same Oey and Ore exist, one is selected randomly, the scheduling order of all operations is kept in Oey, and the corresponding machine code is mutated and regarded as the initial individual in the new environment. Given the high similarity between the scheduling scheme in memory population and the currently executing scheduling scheme, the new individuals generated using memory individuals are more suitable for the current working state, which is conducive to the system stability.


## 3.2.1. Establishment and Renewal of External Population

The solution principle of MOEA/D indicates that when offspring individualy′cannot replace any individual in the neighbourhood, y′ is abandoned directly. Thus, this study establishes an external population Ey for each individual to make the abandoned y′participate in the evolution. The specific way is as follows. An external population with the same size is set as the neighbourhood T. num_alt is used to record the number of individuals in the neighbourhood replaced with y′. y′, whose num_alt is equal to 0, enters the external population.When the scale ofEy is smaller than the upper limit T, if num_alt = 0, the corresponding y′ enters Ey; if 0 < num_alt ≤T/2, Ey remains unchanged; if num_alt > T/2, Ey is emptied because the current subproblem and its neighbour subproblems are far from the optimal solution.When the scale ofEy is up to the upper limit T, if num_alt = 0, the population has evolved to a certain extent, and the current individual is close to its neighbour individual. To maintain the population diversity, the individual with the smallest Euclidean distance to the current individual in Ey is deleted, and y′ enters Ey.


## 3.2.2. Generation of Initial Population at Rescheduling Time

Two cases needing to reschedule tasks are considered in this paper. The first one is related to workshop working time, which is called periodic rescheduling. The second one is related to machine state, including fault and fault recovery rescheduling. In consideration of the two situations above, two different dynamic processing technologies are designed, and the details are as follows.At the time of periodic reschedulingntl, the new tasks are recorded, the machine state is updated, and the initial population under the new period is generated in accordance with the coding method in Subsection 3.1.If a machine breaks down or operates again, i.e.,t = tb or t = tr, the new population of tb or tr is generated in accordance with the implementation of the original scheduling scheme. The details are as follows. If t = tb, in the current scheduling scheme, operations to be rescheduled contain all the unfinished operations arranged on the broken machine and all the operations that have not started until tb. If t = tr, in the current scheduling scheme, operations to be rescheduled contain all the operations that have not started until tr. The set of all operations to be rescheduled is named Ore. When t = tb or t = tr, for each individual in the original population, if Ey = ∅, all operations in Ore should be reinitialized as the new individual in the new environment in accordance with the coding method above; if Ey ≠ ∅, for each scheduling scheme in Ey, the set of operations that need to be rescheduled is recorded and named Oey; if memory individuals with exactly the same Oey and Ore exist, one is selected randomly, the scheduling order of all operations is kept in Oey, and the corresponding machine code is mutated and regarded as the initial individual in the new environment. Given the high similarity between the scheduling scheme in memory population and the currently executing scheduling scheme, the new individuals generated using memory individuals are more suitable for the current working state, which is conducive to the system stability.


## 3.3. Core Evolutionary Strategy

In the scheduling process of each transient environment, the core evolutionary strategy SSA is used to update the population. An individual contains operation and machine codes, but the machine code is determined by the operation code. Therefore, the updating strategy of the population is aimed only at the operation code, rather than the machine code. The specific updating process is described below.


### 3.3.1. Related Variables

Fd: Learning target in accordance with the standard SSA; the details have been introduced in Reference [20].n_same: When the operation codes of FSi and Fd are matched one by one, n_same is the total number of the same operation codes.n_jl: Total number of new jobs at tl.Fr1, Fr2: If Ey = ∅, Fr1 and Fr2 are two individuals different from Fd and FSi randomly selected in their neighbor; if Ey ≠ ∅, Fr1 is any individual in its neighborhood different from FSi, and Fr2 is randomly selected in Ey.Scgand Smin are calculated according to Reference [20], and the winter search strategy is selected whenScg>Smin.(1)
Winter search strategy①
No predators exist whenr>Pdp.The jump search method is selected whenn_same > n_jl/2, and the progressive search method is decided when n_same ≤ n_jl/2.The jump search method:FSi and Fd have high similarity when n_same > n_jl/2, and the individual is updated using Formula (10).(10)FSig+1=FSig+dg×Gc×Fdt−FSit.In the formula above, “[.]” means to carry out rounding operation, which ensures that the individual code of each dimension is a positive integer.dg and Gc have been introduced in Reference [20].The progressive search method:FSi and Fd have low similarity when n_same ≤ n_jl/2. To maintain population diversity, rds dimensions are selected randomly in accordance with Formula (11) and then rearranged also randomly.(11)rds=r×n_jl−n_same.In the formula above,r is a random number between 0 and 1; the lower the similarity between FSi and Fd is, the more dimensions can be rearranged, and the search space can be developed more sufficiently.②
A predator occurs whenr≤Pdp.FSi is considered dead, and the offspring is generated via Fr1 and Fr2 in accordance with the POX introduced in Reference [24].(2)
Summer search strategy①
No predators exist whenr>Pdp.The jump search method is selected whenn_same > n_jl/2, and the progressive search method is chosen when n_same ≤ n_jl/2.The jump search method:FSi and Fd have high similarity when n_same > n_jl/2, and the individual is updated using Formula (12).(12)FSit+1=Fdt+dg×Gc×FSit−Fdt.Formula (12) regards Fd as the basic vector, improves the convergence speed at the beginning of environmental change, and deeply develops the search space after the population evolves to a certain extent.The progressive search method is the same as that in the winter search method. Ifn_same ≤ n_jl/2, rds dimensions are selected randomly in accordance with Formula (10) and then rearranged also randomly.②
A predator occurs whenr≤Pdp.FSi is considered dead, and the offspring is generated using Fr1 and Fr2 in accordance with the POX introduced in Reference [24].FJSSP requires that the value of each dimension is the job number corresponding to the operation, and the total occurrence time of each job number should be the same as its total operations. Therefore, the operation code of the offspring obtained using the updating strategy above should be modified. The task in Table1 is regarded as an example to introduce the modification process, and the details are as follows.The redundant job numbers are determined and recorded in vector “more.” If numberi of job Ji occurs ni + c times, then i occurs in “more” c times. Figure 4 is considered an example. For the problem in Table 1, the operation code of the offspring is 134312214131, more = {1, 1}.Figure 4
Modification of the operation code.The missing job numbers are identified and recorded in vector “less.” If number i of job Ji occurs ni-c times, then i occurs in “less” c times. Figure 4 is regarded as an example. For the problem in Table 1, the operation code of the offspring is 134312214131, less = {2, 4}.The redundant job numbers occurring in “more” in the offspring are selected randomly to replace the missing job numbers in “less.” All elements in “less” are arranged randomly, and the modification is completed. Figure4 is regarded as an example, the 5-th dimension of the offspring operation code changes from 1 to 4, and the 10th dimension changes from 1 to 2.An operation machine is selected randomly in the alternative machine set after the operation code of each offspring is determined, and the operation code constitutes a complete offspring scheduling scheme.


## 3.3.1. Related Variables

Fd: Learning target in accordance with the standard SSA; the details have been introduced in Reference [20].n_same: When the operation codes of FSi and Fd are matched one by one, n_same is the total number of the same operation codes.n_jl: Total number of new jobs at tl.Fr1, Fr2: If Ey = ∅, Fr1 and Fr2 are two individuals different from Fd and FSi randomly selected in their neighbor; if Ey ≠ ∅, Fr1 is any individual in its neighborhood different from FSi, and Fr2 is randomly selected in Ey.Scgand Smin are calculated according to Reference [20], and the winter search strategy is selected whenScg>Smin.(1)
Winter search strategy①
No predators exist whenr>Pdp.The jump search method is selected whenn_same > n_jl/2, and the progressive search method is decided when n_same ≤ n_jl/2.The jump search method:FSi and Fd have high similarity when n_same > n_jl/2, and the individual is updated using Formula (10).(10)FSig+1=FSig+dg×Gc×Fdt−FSit.In the formula above, “[.]” means to carry out rounding operation, which ensures that the individual code of each dimension is a positive integer.dg and Gc have been introduced in Reference [20].The progressive search method:FSi and Fd have low similarity when n_same ≤ n_jl/2. To maintain population diversity, rds dimensions are selected randomly in accordance with Formula (11) and then rearranged also randomly.(11)rds=r×n_jl−n_same.In the formula above,r is a random number between 0 and 1; the lower the similarity between FSi and Fd is, the more dimensions can be rearranged, and the search space can be developed more sufficiently.②
A predator occurs whenr≤Pdp.FSi is considered dead, and the offspring is generated via Fr1 and Fr2 in accordance with the POX introduced in Reference [24].(2)
Summer search strategy①
No predators exist whenr>Pdp.The jump search method is selected whenn_same > n_jl/2, and the progressive search method is chosen when n_same ≤ n_jl/2.The jump search method:FSi and Fd have high similarity when n_same > n_jl/2, and the individual is updated using Formula (12).(12)FSit+1=Fdt+dg×Gc×FSit−Fdt.Formula (12) regards Fd as the basic vector, improves the convergence speed at the beginning of environmental change, and deeply develops the search space after the population evolves to a certain extent.The progressive search method is the same as that in the winter search method. Ifn_same ≤ n_jl/2, rds dimensions are selected randomly in accordance with Formula (10) and then rearranged also randomly.②
A predator occurs whenr≤Pdp.FSi is considered dead, and the offspring is generated using Fr1 and Fr2 in accordance with the POX introduced in Reference [24].FJSSP requires that the value of each dimension is the job number corresponding to the operation, and the total occurrence time of each job number should be the same as its total operations. Therefore, the operation code of the offspring obtained using the updating strategy above should be modified. The task in Table1 is regarded as an example to introduce the modification process, and the details are as follows.The redundant job numbers are determined and recorded in vector “more.” If numberi of job Ji occurs ni + c times, then i occurs in “more” c times. Figure 4 is considered an example. For the problem in Table 1, the operation code of the offspring is 134312214131, more = {1, 1}.Figure 4
Modification of the operation code.The missing job numbers are identified and recorded in vector “less.” If number i of job Ji occurs ni-c times, then i occurs in “less” c times. Figure 4 is regarded as an example. For the problem in Table 1, the operation code of the offspring is 134312214131, less = {2, 4}.The redundant job numbers occurring in “more” in the offspring are selected randomly to replace the missing job numbers in “less.” All elements in “less” are arranged randomly, and the modification is completed. Figure4 is regarded as an example, the 5-th dimension of the offspring operation code changes from 1 to 4, and the 10th dimension changes from 1 to 2.An operation machine is selected randomly in the alternative machine set after the operation code of each offspring is determined, and the operation code constitutes a complete offspring scheduling scheme.


## 4. Experimental Simulation and Result Analysis

To verify the effectiveness of the dynamic multi-objective SSA for solving the FJSSP mathematical model established in this paper, the FJSSP model and the dynamic multi-objective SSA are applied to solve an actual FJSSP. All the tests are implemented on a computer CPU: Intel (R) Core (TM) i5-7200U, 4 G memory, and 2.70 GHz main frequency. The program is implemented in MATLAB R2016a. The experiment includes two parts: effectiveness validation and advanced verification.


### 4.1. Effectiveness Validation

To investigate the FJSSP mathematical model established in this paper and the effect of the designed scheduling method, the following FJSSPs are tested: the number of machines ism = 6; the rescheduling cycle is tl = 1; the time intervals between two adjacent tasks arrive at an exponential distribution of mean 0.5; the number of jobs per task nj obeys the uniform distribution between [m/2, m]; the flexibility of each process is subject to a uniform distribution between [m/2, m]; the processing time of each process obeys the exponential distribution with a mean value of 1; MTBF obeys the exponential distribution of mean mtb, and mtb obeys the uniform distribution between [20, 40]; MTTR obeys the exponential distribution of mean MTR, and MTR obeys the uniform distribution of [5, 10] and randomly selects a fault machine. The task to be processed at the initial time is shown in Table 2. The algorithm parameters are set as follows: SSA’s Nfs = 2; population size N = 300; the upper limit of neighbourhood size and positive memory population size is 20; the maximum iteration number of each transient environment is gmax=100; POX cross mode cross probability pc = 1; mutation probability pm = 1; when Nl = 100, the total number of scheduling tasks is terminated.Table 2
Tasks to be processed att = 0.
Job numberProcess numberMachine number and corresponding processing time of each process123456111.52780.59011.16140.72460.48110.4691120.39560.45391.08101.06750.64250.5351130.51290.64460.3990—0.3562—210.36680.18663.77280.50681.43201.0902221.24460.6315—0.2521—0.2403230.41780.6454—0.51300.47970.1741311.03320.46891.05380.53620.53071.0737321.47660.67080.62580.59903.4804—33—0.50510.50740.48740.44361.9361340.50113.04180.3736—0.52991.4914350.50341.08310.47770.3409——41——0.63242.49310.64100.4427420.49820.53260.58440.09771.77821.0170431.04070.34322.21312.3234—0.3157440.44820.52092.52506.4491—0.6933510.4508—0.49020.78670.4561—52——0.3664—0.62460.543553—0.43290.3010—0.7159—610.42040.55771.03482.8571—0.7716621.75871.55300.6008—0.7694—630.51880.3955—0.66302.49611.07434641.50501.69410.6725—0.76140.5686712.51873.74620.28720.4990—0.5650723.7646—1.7037—0.79523.1828731.06880.37200.6191——0.2297810.60370.4592—1.06780.74540.4188820.48840.49960.4361—1.84870.4254830.49960.4550——0.10783.6344840.32470.5305—0.6690—0.3700910.50650.52340.7427—2.35890.3925920.46060.52010.25770.69510.56491.4906931.1232—0.51041.32931.08290.360094———1.84752.49100.70871011.0394—0.52910.49440.3455—1020.5875—0.49250.5101—0.7072103——0.38223.94090.38740.50021040.61640.25210.6785———1052.96080.45500.63860.49712.34372.04661060.4888—0.45682.42331.74400.6625Table3 is a part of the nondominated solutions obtained from the fault free time t = 5, the first failure time t = 15.7633, and the first fault repair time t = 23.7424 or the rescheduling task optimization. Figures 5–7 are, respectively, the nondominated graphs obtained from the task to be processed or the rescheduling task optimization of t = 52.1802 at the time of failure free t = 30, the second failure time t = 43.6123, and the second fault repair time.Table 3
Nondominated solutions retained at different times.
t = 5t = 15.7633t = 24.7424CTLBADCTLBADCTLBAD9.71850.0547020.33010.04957.219427.15860.05391.587110.56800.0529020.51330.04017.219427.38020.05390.974510.79690.0511021.52580.03677.219427.31300.05371.447411.24630.0453022.48420.05414.822427.32630.05480.996311.46120.0435025.02910.05034.822427.69190.05370.996312.16500.0398026.61290.04114.762827.72700.05281.197413.29020.0307027.88530.02705.737527.48320.05590.932814.81530.0243029.85000.02323.717127.58860.05311.0079Figure 5
Nondominated graph for the optimization of tasks to be processed att = 30.Figure 6
Nondominated graph optimization for rescheduling tasks att = 43.6123.Figure 7
Nondominated graph optimization for rescheduling tasks att = 52.1802.From the above chart, the mathematical model proposed in this paper is a two-objective optimization problem when all the machines in the workshop are free of failure. The nondominated solution is distributed in the same plane. When the fault occurs or restores, the mathematical model is a three-objective optimization problem, and the nondominated solution is dispersed in a three-dimensional space.Figures8 and 9 are the Gantt charts of the shop scheduling plan during t = 10–30 and t = –55, respectively. Ji is the task number. Purple, yellow, blue, orange, cyan, and gray represent the 1–6 processes of each task, respectively. Red represents the rescheduling process after a machine fails, and green represents the rescheduling process after the machine fails to recover. When machine M2 breaks down at t = 15.7633–23.7424, the fault machine does not perform any operation. When machine M breaks down at t = 43.6123–52.1802, the fault machine does not perform any operation. After the machine breaks down, the fault machine is in working state again.Figure 8
Gantt chart oft = 10–30 scheduling scheme.Figure 9
Gantt chart oft = 35–55 scheduling scheme.In order to further verify the FJSSP mathematical model established in this paper and the effect of the designed scheduling method, we carry out the following experiments. Set the number of machines to 8, and the rescheduling periodtl = 15; the time interval between two adjacent tasks follows an exponential distribution with a mean of 0.625. The parameter settings and algorithm settings of other scheduling environments are consistent with those mentioned above. The tasks to be processed at the initial time are shown in Table 4. Figures 10 and 11 are the Gantt charts of the shop scheduling plan during t = 15–25 and t = 30–40, respectively.Table 4
Tasks to be processed att = 0.
Job numberProcess numberMachine number and corresponding processing time of each process1234567811—0.63821.26811.0710—1.30420.8963—120.50190.84001.38801.01600.39890.85410.47080.3358131.6475—0.8298—1.21520.27171.57941.5971142.89281.4613—1.10140.99682.1039——151.18641.36961.25590.1734————161.21200.65450.6413—1.25811.0654—0.7189210.68150.81640.9751—1.05292.3129—0.2768220.4422—0.4240—1.51431.50952.01990.8215232.74162.6740—1.73881.32540.05002.16850.342524—0.98912.08802.20060.41740.52541.95150.4033252.36760.33230.75491.82170.13190.53491.82950.3132312.03710.79171.52490.51021.70241.46740.58180.5744322.1183—0.54710.98590.57681.03520.67401.9032330.96380.63471.10810.92931.10821.46230.86590.438034——1.41760.2305———2.2456412.04911.6558—1.07071.55610.31661.38020.7998420.37040.75751.2038——0.5326——43—1.2657——0.85110.87442.92201.4142441.35121.40500.47432.67912.85021.11822.97560.3806450.9679—1.32291.26261.89650.41821.35830.531246—0.32251.9250—1.60300.97022.5834—510.46912.18520.71400.99371.27772.73753.03240.4996522.9772—1.8705————1.117553—1.85620.13731.00240.7281——0.8232541.34020.66340.09990.60040.2650———550.98941.91702.18502.9171—0.30450.59290.3364560.65170.7840—0.28390.99460.2948—0.4172611.1747————0.26490.79741.7007621.01990.68060.41071.6766—0.72311.28382.324263———1.65110.5025——1.3843640.2826——1.8508——0.5031—710.85620.44081.2425——0.90391.76112.9910720.56520.83301.29360.6021—0.94801.98912.916473—0.58421.4921—0.5617—0.6148—74——0.7785—0.67161.60411.99490.098275—0.52351.4898—1.31410.0204——81—0.5735——0.1725—1.33130.4930820.3275———0.9262——0.619483—2.20660.82220.96650.61310.22831.18731.7934840.54930.63850.5536—0.63740.56011.1408—850.9098———1.49460.6431—0.7129861.60853.30163.15810.35361.18930.45410.3692—911.56290.34631.09891.6513————920.28410.70692.40571.30181.14070.49201.95122.9612930.0736—1.78151.38330.13681.57202.14340.493694—1.68473.0446——3.02260.5515—950.49571.7989—1.28700.44842.8027—0.05361010.46312.9016—0.88570.1663———1020.1600—1.0278—0.4837———103—2.09671.3427——0.35340.16321.30101040.58641.30442.04120.63251.86610.4146——1051.85940.58630.60370.21860.61270.12253.1598—1062.28981.4587—0.17520.43260.38041.90460.9512Figure 10
Gantt chart oft = 15∼t = 25 scheduling scheme.Figure 11
Gantt chart oft = 30∼t = 40 scheduling scheme.It can be seen from Figures10 and 11, when machine M1 breaks down at t = 15.5810–t = 17.7670, the fault machine does not perform any operation. When machine M2 breaks down at t = 33.9251–t = 39.2939, the fault machine does not perform any operation. After the machine breaks down, the fault machine is in working state again.To sum up, the FJSSP mathematical model and the scheduling method established in this paper can effectively cope with the changes in an actual workshop environment, including the task of reaching or leaving at any time and the occurrence of faults. This condition can effectively solve FJSSP.


### 4.2. Advanced Verification

The dynamic multi-objective SSA is used to optimize the mathematical models established in this paper and Reference [23] to solve FJSSP by satisfying the following conditions: the number of machines is m = 6; rescheduling cycle tl = 30; the time intervals between two adjacent tasks arrive at an exponential distribution of mean 3; the number of jobs per task nj obeys the uniform distribution between [m/2, m]; the degree of flexibility of each process obeys the uniform distribution between [m/2, m]; the processing time of each process obeys the exponential distribution of mean 5; MTBF obeys the exponential distribution of mean mtb, and mtb obeys the uniform distribution of [100, 200]; MTTR obeys the exponential distribution of mean mtr, and mtr obeys the uniform distribution of [30, 60] and randomly selects a fault machine at the time of failure. The rest of the parameter settings are consistent with the previous ones. The task to be processed at the initial time is shown in Table 5.Table 5
Tasks to be processed att = 0.
Job numberProcess numberMachine number and corresponding processing time of each process12345611——9.82385.60662.3884—12—8.76140.1616—4.51113.6049132.2260—1.05555.9327——146.84265.3029——0.31792.492421——8.76053.21390.89772.2408221.875327.44686.70445.2220—0.1501231.03210.43540.40333.86290.24320.7356244.13493.6649—4.29660.30850.7078255.1805—6.70700.02186.37981.4679317.4515—8.711211.44230.50150.4604323.4696—0.14013.4382—0.8415330.8281—12.58230.9464—14.4992345.4673—3.5510—3.71514.329735—2.3391—2.37926.57050.4136411.00623.98730.28616.32712.96920.7711423.15580.37063.3700—4.15280.55814315.15226.1692—5.34640.2628—511.35012.31516.95866.31533.93880.566852—7.84090.4757—7.168511.6505531.58641.66472.40721.1779—0.3065541.68644.8608—2.6172—4.6677616.3858—9.56758.1202—1.09116210.08664.2997—14.22982.1821—63—3.90330–.64448.54183.8565—640.9869—0.70952.510511.343421.0465652.1080—5.27432.06111.24166.9164711.21922.05004.6593——2.32037213.40360.30656.48454.50840.14030.71977312.02717.52832.32528.66302.10884.8157743.47072.7486—6.78132.552510.20108110.99519.72862.70848.0656—4.2686826.54683.49211.69324.25822.33769.5210831.27717.0129——0.03179.75308410.16900.30124.48653.82013.85403.993891—0.84264.9192—16.156018.1553923.95871.8530——0.8106—930.6760——2.2566—7.2321940.346811.82840.25632.6967——1010.67872.95361.58284.19070.80611.934110211.28610.96123.34804.2695—5.6762103—3.30685.34678.9140—1.16001041.9494——3.02540.2133—1059.77720.25041.45233.722511.89490.93771064.86331.215610.12772.18414.65200.2748For a dynamic scheduling environment, the scheduling scheme is different, and the workshop state at the end of each transient environment is diverse. That is, the initial state of the workshop at the beginning of the next new environment is different. Comparing the optimization capability of different mathematical models for FJSSP requires the same initial workshop state and the same task to be optimized. The following parts are tested in this study.(1)
The mathematical model in Reference [23] is used to optimize the dynamic environment continuously. The workshop state at the beginning of each new scheduling cycle is recorded. Several different initial states and transient scheduling cycles are obtained. The new task to be processed in each scheduling cycle is recorded, and the mathematical model built in this paper is used to optimize the corresponding workshop initial state. The completion time and maximum machine load of two scheduling indexes in Reference [23] are compared. Figure 12 is a comparison chart of the maximum scheduling time obtained from the optimization of the two models. Figure 13 is a comparison diagram of the maximum machine load obtained from the two models.(2)
Figure12 shows that when the mathematical model in Reference [23] is used to optimize FJSSP continuously, the completion time increases with the increase in the number of tasks to be processed. At the initial time, the mathematical model in Reference [23] achieves shorter completion time at the fourth scheduling cycle, but a minimal difference exists between the two mathematical models at the ninth scheduling cycle. In the rest of the scheduling cycles, the mathematical models in this paper achieve shorter completion time. Therefore, compared with the mathematical model in Reference [23], the mathematical model in this paper is more efficient in solving FJSSP. In Figure 13, the maximum machine load increases with the increase in the number of tasks to be processed. The first scheduling cycle and the seventh scheduling period in the literature yield a smaller maximum machine load. The optimization results of the two mathematical models at the fifth scheduling cycle are similar to each other. In the rest of the scheduling cycles, the mathematical models proposed in this paper achieve a smaller maximum machine load. Hence, compared with the mathematical model in Reference [23], the mathematical model in this paper has better stability when solving FJSSP.(3)
The mathematical model established in this paper is used to optimize the above dynamic environment continuously. The workshop state at the beginning of each new scheduling cycle is recorded. Several different initial states and transient scheduling cycles are obtained. The new task to be processed in each scheduling cycle is recorded, and the mathematical model in Reference [23] is optimized in the initial state of the corresponding workshop. The completion time, LB, and deviation degree of the three scheduling indexes optimized in this paper are compared. Figure 14 shows a comparison of the maximum scheduling time obtained from the optimization of the two models, and Figure 15 depicts a comparison of the LB obtained from the optimization of the two models. Figure 14 shows the two models at the time of failure or recovery (M2 breaks down at t = 85.7705, 108.0616; M5 breaks down at t = 137.4366 and recovers at t = 196.8504; M6 breaks down at t = 253.2210 and recovers at t = 261.4715). Figure 16 is a Gantt chart of the final scheduling scheme obtained by optimizing the mathematical model established in this paper.Figure 12
Comparison of the maximum completion time of each scheduling cycle.Figure 13
Comparison of the maximum load of machines in each scheduling cycle.Figure 14
Comparison of the maximum completion time of each scheduling cycle.Figure 15
Comparison of LB for each scheduling cycle.Figure 16
Final scheduling scheme in this paper. (a)t = 0–3tl. (b) t = 4tl–6tl. (c) t = 7tl–9tl.
(a)(b)(c)Figure14 demonstrates that when the mathematical model established in this paper continuously optimizes FJSSP, the completion time increases with the number of tasks to be processed. Except at the fourth scheduling cycle, the mathematical model in this paper achieves a smaller completion time in the rest of the scheduling cycles. Thus, compared with the mathematical model in Reference [23], the mathematical model in this paper is more efficient in solving FJSSP. In Figure 15, with the progress of the scheduling process, the stability of the workshop is enhanced. Except at the sixth scheduling cycle, the mathematical model in this paper achieves a smaller LB in the rest of the scheduling cycles. Accordingly, compared with the mathematical model in Reference [23], the current model achieves better system stability when solving FJSSP. Figure 14 illustrates that at the time of failure and the time of recovery, the mathematical model established in this paper can achieve smaller deviations of the old and new schemes. Therefore, the mathematical model proposed in this paper can maintain better stability in the rescheduling process after the workshop machine failure or machine failure recovery. A comprehensive observation of Figures 14–17 shows that machine M5 fails at the fourth scheduling cycle. Although the final scheduling scheme optimized by the mathematical model established in this paper is longer, it maintains better system stability, especially when the machine fault rescheduling achieves a smaller deviation; M5 is recovered at the sixth scheduling cycle. Although the LB of the final scheduling scheme optimized using the mathematical model established in this paper is poor, the completion time is shorter, and a smaller deviation degree is achieved during machine fault rescheduling.Figure 17
Comparison of deviations between old and new scheduling schemes during machine failure and failure recovery. (a) M2 failure. (b) M5 failure. (c) M6 failure.
(a)(b)(c)In summary, the mathematical model established in this paper has higher efficiency and better system stability when solving FJSSP. Moreover, in the workshop machine failure or failure recovery, it can pay attention to efficiency and stability at the same time. It has certain advantages for FJSSP optimization.


## 4.1. Effectiveness Validation

To investigate the FJSSP mathematical model established in this paper and the effect of the designed scheduling method, the following FJSSPs are tested: the number of machines ism = 6; the rescheduling cycle is tl = 1; the time intervals between two adjacent tasks arrive at an exponential distribution of mean 0.5; the number of jobs per task nj obeys the uniform distribution between [m/2, m]; the flexibility of each process is subject to a uniform distribution between [m/2, m]; the processing time of each process obeys the exponential distribution with a mean value of 1; MTBF obeys the exponential distribution of mean mtb, and mtb obeys the uniform distribution between [20, 40]; MTTR obeys the exponential distribution of mean MTR, and MTR obeys the uniform distribution of [5, 10] and randomly selects a fault machine. The task to be processed at the initial time is shown in Table 2. The algorithm parameters are set as follows: SSA’s Nfs = 2; population size N = 300; the upper limit of neighbourhood size and positive memory population size is 20; the maximum iteration number of each transient environment is gmax=100; POX cross mode cross probability pc = 1; mutation probability pm = 1; when Nl = 100, the total number of scheduling tasks is terminated.Table 2
Tasks to be processed att = 0.
Job numberProcess numberMachine number and corresponding processing time of each process123456111.52780.59011.16140.72460.48110.4691120.39560.45391.08101.06750.64250.5351130.51290.64460.3990—0.3562—210.36680.18663.77280.50681.43201.0902221.24460.6315—0.2521—0.2403230.41780.6454—0.51300.47970.1741311.03320.46891.05380.53620.53071.0737321.47660.67080.62580.59903.4804—33—0.50510.50740.48740.44361.9361340.50113.04180.3736—0.52991.4914350.50341.08310.47770.3409——41——0.63242.49310.64100.4427420.49820.53260.58440.09771.77821.0170431.04070.34322.21312.3234—0.3157440.44820.52092.52506.4491—0.6933510.4508—0.49020.78670.4561—52——0.3664—0.62460.543553—0.43290.3010—0.7159—610.42040.55771.03482.8571—0.7716621.75871.55300.6008—0.7694—630.51880.3955—0.66302.49611.07434641.50501.69410.6725—0.76140.5686712.51873.74620.28720.4990—0.5650723.7646—1.7037—0.79523.1828731.06880.37200.6191——0.2297810.60370.4592—1.06780.74540.4188820.48840.49960.4361—1.84870.4254830.49960.4550——0.10783.6344840.32470.5305—0.6690—0.3700910.50650.52340.7427—2.35890.3925920.46060.52010.25770.69510.56491.4906931.1232—0.51041.32931.08290.360094———1.84752.49100.70871011.0394—0.52910.49440.3455—1020.5875—0.49250.5101—0.7072103——0.38223.94090.38740.50021040.61640.25210.6785———1052.96080.45500.63860.49712.34372.04661060.4888—0.45682.42331.74400.6625Table3 is a part of the nondominated solutions obtained from the fault free time t = 5, the first failure time t = 15.7633, and the first fault repair time t = 23.7424 or the rescheduling task optimization. Figures 5–7 are, respectively, the nondominated graphs obtained from the task to be processed or the rescheduling task optimization of t = 52.1802 at the time of failure free t = 30, the second failure time t = 43.6123, and the second fault repair time.Table 3
Nondominated solutions retained at different times.
t = 5t = 15.7633t = 24.7424CTLBADCTLBADCTLBAD9.71850.0547020.33010.04957.219427.15860.05391.587110.56800.0529020.51330.04017.219427.38020.05390.974510.79690.0511021.52580.03677.219427.31300.05371.447411.24630.0453022.48420.05414.822427.32630.05480.996311.46120.0435025.02910.05034.822427.69190.05370.996312.16500.0398026.61290.04114.762827.72700.05281.197413.29020.0307027.88530.02705.737527.48320.05590.932814.81530.0243029.85000.02323.717127.58860.05311.0079Figure 5
Nondominated graph for the optimization of tasks to be processed att = 30.Figure 6
Nondominated graph optimization for rescheduling tasks att = 43.6123.Figure 7
Nondominated graph optimization for rescheduling tasks att = 52.1802.From the above chart, the mathematical model proposed in this paper is a two-objective optimization problem when all the machines in the workshop are free of failure. The nondominated solution is distributed in the same plane. When the fault occurs or restores, the mathematical model is a three-objective optimization problem, and the nondominated solution is dispersed in a three-dimensional space.Figures8 and 9 are the Gantt charts of the shop scheduling plan during t = 10–30 and t = –55, respectively. Ji is the task number. Purple, yellow, blue, orange, cyan, and gray represent the 1–6 processes of each task, respectively. Red represents the rescheduling process after a machine fails, and green represents the rescheduling process after the machine fails to recover. When machine M2 breaks down at t = 15.7633–23.7424, the fault machine does not perform any operation. When machine M breaks down at t = 43.6123–52.1802, the fault machine does not perform any operation. After the machine breaks down, the fault machine is in working state again.Figure 8
Gantt chart oft = 10–30 scheduling scheme.Figure 9
Gantt chart oft = 35–55 scheduling scheme.In order to further verify the FJSSP mathematical model established in this paper and the effect of the designed scheduling method, we carry out the following experiments. Set the number of machines to 8, and the rescheduling periodtl = 15; the time interval between two adjacent tasks follows an exponential distribution with a mean of 0.625. The parameter settings and algorithm settings of other scheduling environments are consistent with those mentioned above. The tasks to be processed at the initial time are shown in Table 4. Figures 10 and 11 are the Gantt charts of the shop scheduling plan during t = 15–25 and t = 30–40, respectively.Table 4
Tasks to be processed att = 0.
Job numberProcess numberMachine number and corresponding processing time of each process1234567811—0.63821.26811.0710—1.30420.8963—120.50190.84001.38801.01600.39890.85410.47080.3358131.6475—0.8298—1.21520.27171.57941.5971142.89281.4613—1.10140.99682.1039——151.18641.36961.25590.1734————161.21200.65450.6413—1.25811.0654—0.7189210.68150.81640.9751—1.05292.3129—0.2768220.4422—0.4240—1.51431.50952.01990.8215232.74162.6740—1.73881.32540.05002.16850.342524—0.98912.08802.20060.41740.52541.95150.4033252.36760.33230.75491.82170.13190.53491.82950.3132312.03710.79171.52490.51021.70241.46740.58180.5744322.1183—0.54710.98590.57681.03520.67401.9032330.96380.63471.10810.92931.10821.46230.86590.438034——1.41760.2305———2.2456412.04911.6558—1.07071.55610.31661.38020.7998420.37040.75751.2038——0.5326——43—1.2657——0.85110.87442.92201.4142441.35121.40500.47432.67912.85021.11822.97560.3806450.9679—1.32291.26261.89650.41821.35830.531246—0.32251.9250—1.60300.97022.5834—510.46912.18520.71400.99371.27772.73753.03240.4996522.9772—1.8705————1.117553—1.85620.13731.00240.7281——0.8232541.34020.66340.09990.60040.2650———550.98941.91702.18502.9171—0.30450.59290.3364560.65170.7840—0.28390.99460.2948—0.4172611.1747————0.26490.79741.7007621.01990.68060.41071.6766—0.72311.28382.324263———1.65110.5025——1.3843640.2826——1.8508——0.5031—710.85620.44081.2425——0.90391.76112.9910720.56520.83301.29360.6021—0.94801.98912.916473—0.58421.4921—0.5617—0.6148—74——0.7785—0.67161.60411.99490.098275—0.52351.4898—1.31410.0204——81—0.5735——0.1725—1.33130.4930820.3275———0.9262——0.619483—2.20660.82220.96650.61310.22831.18731.7934840.54930.63850.5536—0.63740.56011.1408—850.9098———1.49460.6431—0.7129861.60853.30163.15810.35361.18930.45410.3692—911.56290.34631.09891.6513————920.28410.70692.40571.30181.14070.49201.95122.9612930.0736—1.78151.38330.13681.57202.14340.493694—1.68473.0446——3.02260.5515—950.49571.7989—1.28700.44842.8027—0.05361010.46312.9016—0.88570.1663———1020.1600—1.0278—0.4837———103—2.09671.3427——0.35340.16321.30101040.58641.30442.04120.63251.86610.4146——1051.85940.58630.60370.21860.61270.12253.1598—1062.28981.4587—0.17520.43260.38041.90460.9512Figure 10
Gantt chart oft = 15∼t = 25 scheduling scheme.Figure 11
Gantt chart oft = 30∼t = 40 scheduling scheme.It can be seen from Figures10 and 11, when machine M1 breaks down at t = 15.5810–t = 17.7670, the fault machine does not perform any operation. When machine M2 breaks down at t = 33.9251–t = 39.2939, the fault machine does not perform any operation. After the machine breaks down, the fault machine is in working state again.To sum up, the FJSSP mathematical model and the scheduling method established in this paper can effectively cope with the changes in an actual workshop environment, including the task of reaching or leaving at any time and the occurrence of faults. This condition can effectively solve FJSSP.


## 4.2. Advanced Verification

The dynamic multi-objective SSA is used to optimize the mathematical models established in this paper and Reference [23] to solve FJSSP by satisfying the following conditions: the number of machines is m = 6; rescheduling cycle tl = 30; the time intervals between two adjacent tasks arrive at an exponential distribution of mean 3; the number of jobs per task nj obeys the uniform distribution between [m/2, m]; the degree of flexibility of each process obeys the uniform distribution between [m/2, m]; the processing time of each process obeys the exponential distribution of mean 5; MTBF obeys the exponential distribution of mean mtb, and mtb obeys the uniform distribution of [100, 200]; MTTR obeys the exponential distribution of mean mtr, and mtr obeys the uniform distribution of [30, 60] and randomly selects a fault machine at the time of failure. The rest of the parameter settings are consistent with the previous ones. The task to be processed at the initial time is shown in Table 5.Table 5
Tasks to be processed att = 0.
Job numberProcess numberMachine number and corresponding processing time of each process12345611——9.82385.60662.3884—12—8.76140.1616—4.51113.6049132.2260—1.05555.9327——146.84265.3029——0.31792.492421——8.76053.21390.89772.2408221.875327.44686.70445.2220—0.1501231.03210.43540.40333.86290.24320.7356244.13493.6649—4.29660.30850.7078255.1805—6.70700.02186.37981.4679317.4515—8.711211.44230.50150.4604323.4696—0.14013.4382—0.8415330.8281—12.58230.9464—14.4992345.4673—3.5510—3.71514.329735—2.3391—2.37926.57050.4136411.00623.98730.28616.32712.96920.7711423.15580.37063.3700—4.15280.55814315.15226.1692—5.34640.2628—511.35012.31516.95866.31533.93880.566852—7.84090.4757—7.168511.6505531.58641.66472.40721.1779—0.3065541.68644.8608—2.6172—4.6677616.3858—9.56758.1202—1.09116210.08664.2997—14.22982.1821—63—3.90330–.64448.54183.8565—640.9869—0.70952.510511.343421.0465652.1080—5.27432.06111.24166.9164711.21922.05004.6593——2.32037213.40360.30656.48454.50840.14030.71977312.02717.52832.32528.66302.10884.8157743.47072.7486—6.78132.552510.20108110.99519.72862.70848.0656—4.2686826.54683.49211.69324.25822.33769.5210831.27717.0129——0.03179.75308410.16900.30124.48653.82013.85403.993891—0.84264.9192—16.156018.1553923.95871.8530——0.8106—930.6760——2.2566—7.2321940.346811.82840.25632.6967——1010.67872.95361.58284.19070.80611.934110211.28610.96123.34804.2695—5.6762103—3.30685.34678.9140—1.16001041.9494——3.02540.2133—1059.77720.25041.45233.722511.89490.93771064.86331.215610.12772.18414.65200.2748For a dynamic scheduling environment, the scheduling scheme is different, and the workshop state at the end of each transient environment is diverse. That is, the initial state of the workshop at the beginning of the next new environment is different. Comparing the optimization capability of different mathematical models for FJSSP requires the same initial workshop state and the same task to be optimized. The following parts are tested in this study.(1)
The mathematical model in Reference [23] is used to optimize the dynamic environment continuously. The workshop state at the beginning of each new scheduling cycle is recorded. Several different initial states and transient scheduling cycles are obtained. The new task to be processed in each scheduling cycle is recorded, and the mathematical model built in this paper is used to optimize the corresponding workshop initial state. The completion time and maximum machine load of two scheduling indexes in Reference [23] are compared. Figure 12 is a comparison chart of the maximum scheduling time obtained from the optimization of the two models. Figure 13 is a comparison diagram of the maximum machine load obtained from the two models.(2)
Figure12 shows that when the mathematical model in Reference [23] is used to optimize FJSSP continuously, the completion time increases with the increase in the number of tasks to be processed. At the initial time, the mathematical model in Reference [23] achieves shorter completion time at the fourth scheduling cycle, but a minimal difference exists between the two mathematical models at the ninth scheduling cycle. In the rest of the scheduling cycles, the mathematical models in this paper achieve shorter completion time. Therefore, compared with the mathematical model in Reference [23], the mathematical model in this paper is more efficient in solving FJSSP. In Figure 13, the maximum machine load increases with the increase in the number of tasks to be processed. The first scheduling cycle and the seventh scheduling period in the literature yield a smaller maximum machine load. The optimization results of the two mathematical models at the fifth scheduling cycle are similar to each other. In the rest of the scheduling cycles, the mathematical models proposed in this paper achieve a smaller maximum machine load. Hence, compared with the mathematical model in Reference [23], the mathematical model in this paper has better stability when solving FJSSP.(3)
The mathematical model established in this paper is used to optimize the above dynamic environment continuously. The workshop state at the beginning of each new scheduling cycle is recorded. Several different initial states and transient scheduling cycles are obtained. The new task to be processed in each scheduling cycle is recorded, and the mathematical model in Reference [23] is optimized in the initial state of the corresponding workshop. The completion time, LB, and deviation degree of the three scheduling indexes optimized in this paper are compared. Figure 14 shows a comparison of the maximum scheduling time obtained from the optimization of the two models, and Figure 15 depicts a comparison of the LB obtained from the optimization of the two models. Figure 14 shows the two models at the time of failure or recovery (M2 breaks down at t = 85.7705, 108.0616; M5 breaks down at t = 137.4366 and recovers at t = 196.8504; M6 breaks down at t = 253.2210 and recovers at t = 261.4715). Figure 16 is a Gantt chart of the final scheduling scheme obtained by optimizing the mathematical model established in this paper.Figure 12
Comparison of the maximum completion time of each scheduling cycle.Figure 13
Comparison of the maximum load of machines in each scheduling cycle.Figure 14
Comparison of the maximum completion time of each scheduling cycle.Figure 15
Comparison of LB for each scheduling cycle.Figure 16
Final scheduling scheme in this paper. (a)t = 0–3tl. (b) t = 4tl–6tl. (c) t = 7tl–9tl.
(a)(b)(c)Figure14 demonstrates that when the mathematical model established in this paper continuously optimizes FJSSP, the completion time increases with the number of tasks to be processed. Except at the fourth scheduling cycle, the mathematical model in this paper achieves a smaller completion time in the rest of the scheduling cycles. Thus, compared with the mathematical model in Reference [23], the mathematical model in this paper is more efficient in solving FJSSP. In Figure 15, with the progress of the scheduling process, the stability of the workshop is enhanced. Except at the sixth scheduling cycle, the mathematical model in this paper achieves a smaller LB in the rest of the scheduling cycles. Accordingly, compared with the mathematical model in Reference [23], the current model achieves better system stability when solving FJSSP. Figure 14 illustrates that at the time of failure and the time of recovery, the mathematical model established in this paper can achieve smaller deviations of the old and new schemes. Therefore, the mathematical model proposed in this paper can maintain better stability in the rescheduling process after the workshop machine failure or machine failure recovery. A comprehensive observation of Figures 14–17 shows that machine M5 fails at the fourth scheduling cycle. Although the final scheduling scheme optimized by the mathematical model established in this paper is longer, it maintains better system stability, especially when the machine fault rescheduling achieves a smaller deviation; M5 is recovered at the sixth scheduling cycle. Although the LB of the final scheduling scheme optimized using the mathematical model established in this paper is poor, the completion time is shorter, and a smaller deviation degree is achieved during machine fault rescheduling.Figure 17
Comparison of deviations between old and new scheduling schemes during machine failure and failure recovery. (a) M2 failure. (b) M5 failure. (c) M6 failure.
(a)(b)(c)In summary, the mathematical model established in this paper has higher efficiency and better system stability when solving FJSSP. Moreover, in the workshop machine failure or failure recovery, it can pay attention to efficiency and stability at the same time. It has certain advantages for FJSSP optimization.


## 5. Conclusions

In this study, the characteristics and current research status of FJSSP are comprehensively analysed. A new mathematical model is established on the basis of three objectives: completion time, LB, and AD between new and old scheduling schemes. A dynamic multi-objective SSA is used to optimize the established model. The experimental results show that the dynamic multi-objective SSA can be used to solve FJSSP. The mathematical model established in this paper has improved efficiency and stability in solving dynamic multi-objective FJSSP. Especially when a workshop machine breaks down or gets back to work, the established model can keep enhanced balance between efficiency and stability. In the future, convergence rate of flexible job shop scheduling algorithms should be improved.



---

*Source: 6062689-2021-10-15.xml*