# An Enhanced Differential Evolution Algorithm with Fast Evaluating Strategies for TWT-NFSP with SSTs and RTs

Authors: Rong Hu; Xing Wu; Bin Qian; Jian L. Mao; Huai P. Jin
Journal: Complexity
 (2020)

---

## Abstract

The no-wait flow-shop scheduling problem with sequence-dependent setup times and release times (i.e., the NFSP with SSTs and RTs) is a typical NP-hard problem. This paper proposes an enhanced differential evolution algorithm with several fast evaluating strategies, namely, DE_FES, to minimize the total weighted tardiness objective (TWT) for the NFSP with SSTs and RTs. In the proposed DE_FES, the DE-based search is adopted to perform global search for obtaining the promising regions or solutions in solution space, and a fast local search combined with three presented strategies is designed to execute exploitation from these obtained regions. Test results and comparisons with two effective meta-heuristics show the effectiveness and robustness of DE_FES.


---

## Body

## 1. Introduction

The no-wait flow-shop scheduling problem (NFSP) has been widely studied for more than 30 years [1, 2]. Nevertheless, literature reviews on production scheduling with no-wait or setup constraints in [1, 3] manifest that the NFSP with sequence-dependent setup times (SSTs) and release times (RTs) has not received the attention it needs. In fact, SSTs and RTs are two kinds of constraints widely existing in the real-life NFSPs. These constraints can be found in pharmaceutical processing, metal processing, and chemical processing [4–8]. Moreover, in the current increasingly fierce global competition, many enterprises are trying to reduce the tardy jobs in order to maintain customer satisfaction and avoid the loss of customer orders. Hence, it is important to design an effective algorithm to minimize the total weighted tardiness objective (TWT) for the NFSP with SSTs and RTs (i.e., Fm/no−wait,STsd,rj/∑wjTj).Optimization algorithms have been successfully used to deal with a variety of important engineering problems [9–14]. In recent years, evolutionary algorithms have become an important class of optimization algorithms for addressing production scheduling problems [15–19]. Differential evolution (DE) is a very competitive evolutionary algorithm for solving continuous optimization problem [20–22]. It iteratively executes three key operators, i.e., mutation, crossover, and selection. Due to its easy implementation, simple mechanism, and quick convergence, DE has been applied to addressing various optimization problems in academia and industry. Nevertheless, due to its continuous nature, the studies on DE for combinatorial optimization problems are restricted. Tasgetiren et al. [23] developed a novel DE via introducing the interchange-based local search and the smallest position value (SPV) rule for the flow-shop scheduling problems (FSPs), whose criterion is to minimize makespan. Onwubolu et al. [24] presented a new approach based on DE for the FSPs. They considered three criteria, i.e., mean flowtime, makespan, and total tardiness. Pan et al. [25] designed a discrete DE to address the FSPs effectively. Qian et al. [26] proposed a hybrid DE (HDE) for the NFSP with makespan criterion. By reasonably utilizing the corresponding problem’s properties, HDE is of excellent search ability. Wang et al. [27] designed an effective discrete DE for the blocking FSPs. Hu et al. [28] designed an effective DE, namely, DE_NTJ, for the NFSP with SSTs and RTs. The criterion is to minimize the number of tardy jobs. Qian et al. [29] developed a DE with two speed-up methods (DE_TSM) to minimize the total completion time for the NFSP with SSTs and RTs. Tang et al. [30] presented an improved DE (IDE) to deal with a dynamic scheduling problem in steelmaking-continuous casting production. IDE can obtain better performance than the compared algorithms. Santucci et al. [31] proposed an algebraic DE for the FSPs with total flowtime criterion. Wu and Che [32] developed a memetic DE (MDE) to solve the biobjective unrelated parallel machine scheduling problem. In their tests, MDE outperforms two famous multiobjective algorithms. However, according to the existing literatures, there are no studies on Fm/no−wait,STsd,rj/∑wjTj. Therefore, it is imperative to develop an efficient algorithm for the TWT-NFSP with SSTs and RTs. The developed algorithm can be easily extended for other kinds of flow-shop scheduling problems with no-wait constraint.This paper proposes an efficient DE-based algorithm with fast evaluating strategies (DE_FES) to minimize the total weighted tardiness for the NFSP with SSTs and RTs. Compared with the existing research, the main contributions of this work are summarized as follows:(1)
The permutation-based model for the TWT-NFSP with SSTs and RTs is formulated for the first time. Moreover, the NP-hardness of this problem is proved via a reduction chain starting from a known NP-hard problem.(2)
Three kinds of properties of the TWT-NFSP with SSTs and RTs are analyzed in detail and are utilized to speed up the search process. It is the first time to analyze the low-bound property (see Subsection3.4) of the neighbors in the interchange-based neighbourhood for the NFSP with RTs.(3)
To improve the exploitation ability of DE_FES, a fast local search combing three property-based strategies is presented to perform the efficient search in the promising regions obtained by the DE-based global search.The remaining part of this paper is organized as follows. In Section2, the TWT-NFSP with SSTs and STs is formulated. In Section 3, three fast solution evaluating strategies and some theoretical analyses are presented. In Section 4, DE_FES is proposed after introducing its main components. In Section 5, the test results are provided. Finally, conclusions and future research are given in Section 6.


## 2. TWT-NFSP with SSTs and RTs

The NFSP with SSTs and RTs is described as follows. There aren jobs to be processed on m machines in the same order. Each machine can only process one job at a time. Each job must be processed without waiting time between consecutive operations. Setup times depend on the sequence of the jobs. If the job has not been released, the machine remains idle until it is released.


### 2.1. NFSP with SSTs and RTs

Denoteπ=j1,j2,…,jn is the permutation or schedule to be processed, pji,l is the processing time of job ji on machine l, spji is the total processing time of job ji on m machines, MLji,l is the minimum delay time between ji−1and ji on the machine l, Lji−1,ji is the minimum delay time between ji−1 and ji on the first machine, sji−1,ji,l is the sequence-dependent setup time between ji−1 and ji on machine l, rji is the arrival time of ji, Stji is the start processing time of ji on the first machine, and Cji is the completion time of ji on the last machine. Let pj0,l=0 for l=1,…,m. Then, MLji,l can be calculated as follows:(1)MLji,l=maxsji−1,ji,1+pji,1−pji−1,2,sji−1,ji,2+pji,2,l=2,maxMLji,l−1−pji−1,l,sji−1,ji,l+pji,l,l=3,…,m.By using (1), Lji−1,ji can be calculated with the following formula:(2)Lji−1,ji=MLji,m+spji−1−spji.Obviously,Stji can be written as follows:(3)Stji=maxMLji,m−spji,rji,i=1,Stji−1+maxLji−1,ji,rji−Stji−1=maxStji−1+Lji−1,ji,rji,i=2,…,n.Thus,Cji can be calculated as follows:(4)Cji=Stji+spji,i=1,…,n.Figure1(a) gives an example of the NFSP with SSTs when n = 4 and m = 2. It can be seen that MLji,l and Lji−1,ji are determined by the model of the NFSP with SSTs. Figure 1(b) gives an example of the NFSP with SSTs and RTs when n = 4 and m = 2. It can be seen that Stji and Cji are determined by the model of the NFSP with SSTs and RTs.Figure 1
Two examples whenn = 4 and m = 2. (a) NFSSP with SDSTs when n = 4 and m = 2. (b) NFSSP with SDSTs and RDs when n = 4 and m = 2.
(a)(b)


### 2.2. TWT-NFSP with SSTs and RTs

Denotedji is the due date of ji, wji is the weighted value of ji, and Π is the set of all permutations. Then, TWTπ can be calculated as follows:(5)Tji=maxCji−dji,0=maxStji+spji−dji,0,i=1,…,n,(6)TWTπ=∑i=1nwjiTji=∑i=1nwjimaxCji−dji,0=∑i=1nwjimaxStji+spji−dji,0.The TWT-NFSP with SSTs and RTs is to find an optimal permutationπ∗ in Π such that(7)π∗=argTWTπ⟶min,∀π∈Π.


### 2.3. Problem Complexity

The TWT-NFSP with SSTs and RTs can be described by a tripletFm/no−wait,STsd,rj/∑wjTj. The NP-hardness of this problem can be determined by using a reduction chain starting from a known NP-hard problem, i.e., Fm/no−wait,STsd/∑Cj [3, 8]. Problem A reduces to problem B (denoted A∝B) means A is just a special case of B, and B is at least as difficult to solve as A [2].Theorem 1.
Fm/no−wait,STsd,rj/∑wjTjis NP-hard.Proof.
Obviously,Fm/no−wait,STsd/∑Cj reduces to Fm/no−wait,STsd/∑Cj by setting rj=0 for all j, and Fm/no−wait,STsd/∑Cj reduces to Fm/no−wait,STsd/∑Cj by setting wj=0 and dj=0 for all j. Since each of the above reductions is completed in a polynomial time, a polynomial Turing reduction chain can be established as follows:(8)Fm/no−wait,STsd/∑Cj∝Fm/no−wait,STsd/∑Cj∝Fm/no−wait,STsd/∑Cj,rj/∑wjTj.
By using (8), it can be concluded that Fm/no−wait,STsd,rj/∑wjTj is NP-hard because Fm/no−wait,STsd/∑Cj is NP-hard [3, 8]. Theorem 1 holds.
The reductions between objective functions are given in Figure2. It can be seen from Figure 2 that ∑​wjTj is one of the most difficult criteria. Based on the reduction concept in [2], all the other types of no-wait flow-shop scheduling problems reduce to the NFSP with SSTs and RTs and almost all the other objective functions reduce to TWT (see Figure 2), which means the TWT-NFSP with SSTs and RTs is a most difficult one and can be utilized to represent a wide range of real-life scheduling problems. Thus, the study on the TWT-NFSP with SSTs and RTs has general and theoretical meanings.Figure 2
Basic reductions between objective functions in [2].


## 2.1. NFSP with SSTs and RTs

Denoteπ=j1,j2,…,jn is the permutation or schedule to be processed, pji,l is the processing time of job ji on machine l, spji is the total processing time of job ji on m machines, MLji,l is the minimum delay time between ji−1and ji on the machine l, Lji−1,ji is the minimum delay time between ji−1 and ji on the first machine, sji−1,ji,l is the sequence-dependent setup time between ji−1 and ji on machine l, rji is the arrival time of ji, Stji is the start processing time of ji on the first machine, and Cji is the completion time of ji on the last machine. Let pj0,l=0 for l=1,…,m. Then, MLji,l can be calculated as follows:(1)MLji,l=maxsji−1,ji,1+pji,1−pji−1,2,sji−1,ji,2+pji,2,l=2,maxMLji,l−1−pji−1,l,sji−1,ji,l+pji,l,l=3,…,m.By using (1), Lji−1,ji can be calculated with the following formula:(2)Lji−1,ji=MLji,m+spji−1−spji.Obviously,Stji can be written as follows:(3)Stji=maxMLji,m−spji,rji,i=1,Stji−1+maxLji−1,ji,rji−Stji−1=maxStji−1+Lji−1,ji,rji,i=2,…,n.Thus,Cji can be calculated as follows:(4)Cji=Stji+spji,i=1,…,n.Figure1(a) gives an example of the NFSP with SSTs when n = 4 and m = 2. It can be seen that MLji,l and Lji−1,ji are determined by the model of the NFSP with SSTs. Figure 1(b) gives an example of the NFSP with SSTs and RTs when n = 4 and m = 2. It can be seen that Stji and Cji are determined by the model of the NFSP with SSTs and RTs.Figure 1
Two examples whenn = 4 and m = 2. (a) NFSSP with SDSTs when n = 4 and m = 2. (b) NFSSP with SDSTs and RDs when n = 4 and m = 2.
(a)(b)


## 2.2. TWT-NFSP with SSTs and RTs

Denotedji is the due date of ji, wji is the weighted value of ji, and Π is the set of all permutations. Then, TWTπ can be calculated as follows:(5)Tji=maxCji−dji,0=maxStji+spji−dji,0,i=1,…,n,(6)TWTπ=∑i=1nwjiTji=∑i=1nwjimaxCji−dji,0=∑i=1nwjimaxStji+spji−dji,0.The TWT-NFSP with SSTs and RTs is to find an optimal permutationπ∗ in Π such that(7)π∗=argTWTπ⟶min,∀π∈Π.


## 2.3. Problem Complexity

The TWT-NFSP with SSTs and RTs can be described by a tripletFm/no−wait,STsd,rj/∑wjTj. The NP-hardness of this problem can be determined by using a reduction chain starting from a known NP-hard problem, i.e., Fm/no−wait,STsd/∑Cj [3, 8]. Problem A reduces to problem B (denoted A∝B) means A is just a special case of B, and B is at least as difficult to solve as A [2].Theorem 1.
Fm/no−wait,STsd,rj/∑wjTjis NP-hard.Proof.
Obviously,Fm/no−wait,STsd/∑Cj reduces to Fm/no−wait,STsd/∑Cj by setting rj=0 for all j, and Fm/no−wait,STsd/∑Cj reduces to Fm/no−wait,STsd/∑Cj by setting wj=0 and dj=0 for all j. Since each of the above reductions is completed in a polynomial time, a polynomial Turing reduction chain can be established as follows:(8)Fm/no−wait,STsd/∑Cj∝Fm/no−wait,STsd/∑Cj∝Fm/no−wait,STsd/∑Cj,rj/∑wjTj.
By using (8), it can be concluded that Fm/no−wait,STsd,rj/∑wjTj is NP-hard because Fm/no−wait,STsd/∑Cj is NP-hard [3, 8]. Theorem 1 holds.
The reductions between objective functions are given in Figure2. It can be seen from Figure 2 that ∑​wjTj is one of the most difficult criteria. Based on the reduction concept in [2], all the other types of no-wait flow-shop scheduling problems reduce to the NFSP with SSTs and RTs and almost all the other objective functions reduce to TWT (see Figure 2), which means the TWT-NFSP with SSTs and RTs is a most difficult one and can be utilized to represent a wide range of real-life scheduling problems. Thus, the study on the TWT-NFSP with SSTs and RTs has general and theoretical meanings.Figure 2
Basic reductions between objective functions in [2].


## 3. Three Fast Evaluating Strategies

The reasonable utilization of problem-dependent properties is very useful for designing effective algorithms [33]. So, this section analyses the properties of the considered problem and presents three fast evaluating strategies. Strategy one is based on the general property of the NFSP. Strategies two and three are deduced from the special properties of interchange’s neighbourhood under the NFSP with SSTs and RTs. Strategy one is used to compute the fitness of each individual in DE_FES, and strategies one to three are utilized to design an efficient neighbourhood-based search.


### 3.1. Strategy One: Fast Computing Strategy

In the model of the NFSP with SSTs and RTs,Lji−1,ji is only decided by ji−1 and ji. By utilizing this property, the computing complexity (CC) of TWTπ can be reduced. That is, Lji−1,ji, spji, and ∑i=1nspji are calculated and recorded at DE_FES’s initial stage, and then they are treated as constant values at DE_FES’s evolution stage. This strategy reduces the CC of TWTπ from Onm to On.


### 3.2. The Interchange-Based Neighbourhood

According to [34], the diameter of interchange is n−1. That is to say, one solution π can transit to any other solution by utilizing interchange at most n−1 times. The diameter of interchange is one of the shortest among those most-used neighbourhoods. That is, the neighbors or solutions generated by interchange are closer to each other. So, this subsection chooses to analyze and utilize the properties of interchange’s neighbourhood.Theinterchange-based neighbourhood of π can be given as(9)Ninterchangeπ=πinterchangen,u,v=interchangeπ,u,v|1≤u<v≤n,where interchangeπ,u,v denotes the interchange of ju and jv. The size of Ninterchangeπ is nn−1/2. Figure 3 shows a small example of πinterchangen,u,v when n=10, u=4, and v=7.Figure 3
A small example ofπinterchangen,u,v when n=10, u=4, and v=7.


### 3.3. Strategy Two: Fast Scanning Strategy forNinterchangeπ

A speed-up neighbourhood scanning strategy is presented in this subsection. This strategy is necessary for devising a fast local search.DenoteFind BestNinterchangeπ is the method of obtaining the best neighbor with TWT criterion in Ninterchangeπ (i.e., the Ninterchangeπ-based neighbourhood scanning method). When u = 1,…,n − 1 and i = 1,…,u − 1, it has ji=ji′, wju−1Tju−1=wju−1′Tju−1′, and ∑i=1u−1wji′Tji′=∑i=1u−1wjiTji. Then, according to (5) and (6), it has(10)TWTπinterchangen,u,v=∑i=1u−1wji′Tji′+∑i=unwji′Tji′=∑i=1u−1wjiTji+∑i=unwji′Tji′.It is clear from (10) that in Find BestNinterchangeπ, Stji and ∑ll=1iwjllTjlli=1,…,n−1 can be computed and recorded before evaluating or scanning each neighbor in Ninterchangeπ, and then they can be treated as constant values when evaluating TWTπinterchangen,u,v. Specifically, if u>1, Stju−1′ and ∑i=1u−1wji′Tji′ can be directly replaced by Stju−1 and ∑i=1u−1wjiTji, respectively, and Stju′ can be calculated from Stju−1. When scanning each neighbor in Ninterchangeπ, only ∑i=unwji′Tji′ needs to be calculated. So, by using strategies one and two, the CC of Find BestNinterchangeπ can be decreased to some extent.


### 3.4. Strategy Three: Fast Nonimproving Neighbor Identification Strategy forNinterchangeπ

According to theNinterchangeπ-based neighbourhood properties, two lemmas are stated and then are used in the proof of Theorem 2. By utilizing Theorem 2, the nonimproving neighbors in Ninterchangeπ can be identified with lower CC, which means the CC of Find BestNinterchangeπ can be further reduced.DenoteΔStjyy=1,2,…,n−1 and ΔStjy≥0) is a start processing time delay of jy on the first machine, Stjy′ is the start processing time of jy on the first machine when ΔStjy is added to Stjy (i.e., Stjy′=Stjy+ΔStjy≥Stjy), Stjy+ll′ll=1,…,n−y is the start processing time of job jy+ll on the first machine when Stjy is set to Stjy′, and Tjy+ll′ll=1,…,n−y is the tardiness of job jy+ll on the first machine when Stjy is set to Stjy′.Lemma 1.
For a fixed job permutationπ=j1,j2,…,jn of an NFSP with SSTs and RTs, if Stjy is set to Stjy′, Stjy′≥Stjy, then it has Stjy+ll′≥Stjy+ll for ll=1,…,n−y.Proof.
LetΔy+ll=Stjy+ll′−Stjy+llll=1,…,n−y denote the start processing time delay of jy+ll. Lemma 1 can be proved by using mathematical induction.
Firstly, whenll=1, with (3), it has(11)Stjy+1′=Stjy′+maxLjy,jy+1,rjy+1−Stjy′=maxStjy′+Ljy,jy+1,rjy+1=maxStjy+ΔStjy+Ljy,jy+1,rjy+1.
Obviously, whenΔStjy=0, it has Stjy+1′=Stjy+1.
WhenΔStjy>0, based on the value of rjy+1, three cases are discussed as follows:Case 1.rjy+1≤Stjy+Ljy,jy+1.Under this case, with (11) and (3), it has(12)Stjy+1′=Stjy+ΔStjy+Ljy,jy+1=Stjy+1+ΔStjy>Stjy+1.Case 2.Stjy+Ljy,jy+1<rjy+1<Stjy+ΔStjy+Ljy,jy+1.Under this case, with (11) and (3), it has(13)Stjy+1′=Stjy+ΔStjy+Ljy,jy+1>rjy+1=maxStjy+Ljy,jy+1,rjy+1=Stjy+1.Case 3.rjy+1≥Stjy+ΔStjy+Ljy,jy+1.
Under this case, with (11) and (3), it has(14)Stjy+1′=rjy+1=maxStjy+Ljy,jy+1,rjy+1=Stjy+1,and with (12)–(14), it has Stjy+1′≥Stjy+1.
Secondly, suppose Stjy+ll′≥Stjy+ll holds when 1≤ll≤k. Thus, Δy+k=Stjy+k′−Stjy+k≥0. With (3) and (11), it has(15)Stjy+k+1′=maxStjy+k′+Ljy+k,jy+k+1,rjy+k+1=maxStjy+k+Δy+k+Ljy+k,jy+k+1,rjy+k+1.
Similar to the analysis whenll=1, it has Stjy+k+1′≥Stjy+k+1.
Thus, based on mathematical induction,Stjy+ll′≥Stjy+ll holds when 1≤ll≤n−y.Lemma 2.
For a fixed job permutationπ=j1,j2,…,jn of an NFSP with SSTs and RTs, if Stjy is set to Stjy′Stjy′≥Stjy, then it has Tjy+ll′≥Tjy+ll for ll=1,…,n−y.Proof.
According to Lemma1, when Stjy′≥Stjy, it has Stjy+ll′≥Stjy+ll for ll=1,…,n−y. Then, with (5), it has(16)Tjy+ll′=maxStjy+ll′+spjy+ll−djy+ll,0,(17)Tjy+ll=maxStjy+ll+spjy+ll−djy+ll,0.
Obviously, ifStjy′=Stjy, it has Tjy+ll′=Tjy+ll for ll=1,…,n−y.
IfStjy′>Stjy, according to the value of djy+ll, three cases are discussed as follows:Case 1.djy+ll≤Stjy+ll+spjy+ll.Under this case, with (16) and (17), it has(18)Tjy+ll′=Stjy+ll′+spjy+ll−djy+ll>Stjy+ll+spjy+ll−djy+ll=maxStjy+ll+spjy+ll−djy+ll,0=Tjy+ll.Case 2.Stjy+ll+spjy+ll<djy+ll<Stjy+ll′+spjy+ll.Under this case, with (16) and (17), it has(19)Tjy+ll′=Stjy+ll′+spjy+ll−djy+ll>0=maxStjy+ll+spjy+ll−djy+ll,0=Tjy+ll.Case 3.djy+ll≥Stjy+ll′+spjy+ll.
Under this case, with (16) and (17), it has(20)Tjy+ll′=0=maxStjy+ll+spjy+ll−djy+ll,0=Tjy+ll.
Based on the above analysis, Lemma2 holds.Theorem 2.
Ifv<n and ∑i=uvwji′Tji′≥∑i=uvwjiTji and Stjv+1′≥Stjv+1, then TWTπn,u,v≥TWTπ.Proof.
According to the values ofu, two cases are discussed as follows:Case 1.u>1.From (6) and (10), it has(21)TWTπ=∑i=1u−1wjiTji+∑i=uvwjiTji+∑i=v+1nwjiTji,(22)TWTπn,u,v=∑i=1u−1wji′Tji′+∑i=uvwji′Tji′+∑i=v+1nwji′Tji′.Sinceji′=ji for i=1,…,u−1, it has(23)∑i=1u−1wji′Tji′=∑i=1u−1wjiTji.Asji′=ji for i=v+1,…,n and Stjv+1′≥Stjv+1, according to Lemma 2, it has Tji′≥Tji for i=v+1,…,n. Then, it follows that(24)∑i=v+1nwji′Tji′≥∑i=v+1nwjiTji.Finally, because∑i=uvwji′Tji′≥∑i=uvwjiTji, from (21)–(24), it has(25)TWTπn,u,v−TWTπ=∑i=uvwji′Tji′−∑i=uvwjiTji+∑i=v+1nwji′Tji′−∑i=v+1nwjiTji≥0.Case 2.u=1.
Under this case, from (6) and (10), it has(26)TWTπ=∑i=uvwjiTji+∑i=v+1nwjiTji,(27)TWTπn,u,v=∑i=uvwji′Tji′+∑i=v+1nwji′Tji′.
Since∑i=uvwji′Tji′≥∑i=uvwjiTji, with (24), (26), and (27), it has TWTπn,u,v−TWTπ≥0.
Based on the above analysis, Theorem2 holds.
By utilizing Theorem2, after ∑i=uvwji′Tji′ and Stjv+1′ have been computed, the nonimproving neighbors can be detected without calculating ∑i=v+1nwji′Tji′ if the conditions in Theorem 2 are satisfied. So, Theorem 2 is helpful in reducing the CC of Find BestNinterchangeπ. Let S123_Find BestNinterchangeπ denote Find BestNinterchangeπ with the above three strategies. Note that S123_Find BestNinterchangeπ is a key component in the local search of our proposed DE_FES.


## 3.1. Strategy One: Fast Computing Strategy

In the model of the NFSP with SSTs and RTs,Lji−1,ji is only decided by ji−1 and ji. By utilizing this property, the computing complexity (CC) of TWTπ can be reduced. That is, Lji−1,ji, spji, and ∑i=1nspji are calculated and recorded at DE_FES’s initial stage, and then they are treated as constant values at DE_FES’s evolution stage. This strategy reduces the CC of TWTπ from Onm to On.


## 3.2. The Interchange-Based Neighbourhood

According to [34], the diameter of interchange is n−1. That is to say, one solution π can transit to any other solution by utilizing interchange at most n−1 times. The diameter of interchange is one of the shortest among those most-used neighbourhoods. That is, the neighbors or solutions generated by interchange are closer to each other. So, this subsection chooses to analyze and utilize the properties of interchange’s neighbourhood.Theinterchange-based neighbourhood of π can be given as(9)Ninterchangeπ=πinterchangen,u,v=interchangeπ,u,v|1≤u<v≤n,where interchangeπ,u,v denotes the interchange of ju and jv. The size of Ninterchangeπ is nn−1/2. Figure 3 shows a small example of πinterchangen,u,v when n=10, u=4, and v=7.Figure 3
A small example ofπinterchangen,u,v when n=10, u=4, and v=7.


## 3.3. Strategy Two: Fast Scanning Strategy forNinterchangeπ

A speed-up neighbourhood scanning strategy is presented in this subsection. This strategy is necessary for devising a fast local search.DenoteFind BestNinterchangeπ is the method of obtaining the best neighbor with TWT criterion in Ninterchangeπ (i.e., the Ninterchangeπ-based neighbourhood scanning method). When u = 1,…,n − 1 and i = 1,…,u − 1, it has ji=ji′, wju−1Tju−1=wju−1′Tju−1′, and ∑i=1u−1wji′Tji′=∑i=1u−1wjiTji. Then, according to (5) and (6), it has(10)TWTπinterchangen,u,v=∑i=1u−1wji′Tji′+∑i=unwji′Tji′=∑i=1u−1wjiTji+∑i=unwji′Tji′.It is clear from (10) that in Find BestNinterchangeπ, Stji and ∑ll=1iwjllTjlli=1,…,n−1 can be computed and recorded before evaluating or scanning each neighbor in Ninterchangeπ, and then they can be treated as constant values when evaluating TWTπinterchangen,u,v. Specifically, if u>1, Stju−1′ and ∑i=1u−1wji′Tji′ can be directly replaced by Stju−1 and ∑i=1u−1wjiTji, respectively, and Stju′ can be calculated from Stju−1. When scanning each neighbor in Ninterchangeπ, only ∑i=unwji′Tji′ needs to be calculated. So, by using strategies one and two, the CC of Find BestNinterchangeπ can be decreased to some extent.


## 3.4. Strategy Three: Fast Nonimproving Neighbor Identification Strategy forNinterchangeπ

According to theNinterchangeπ-based neighbourhood properties, two lemmas are stated and then are used in the proof of Theorem 2. By utilizing Theorem 2, the nonimproving neighbors in Ninterchangeπ can be identified with lower CC, which means the CC of Find BestNinterchangeπ can be further reduced.DenoteΔStjyy=1,2,…,n−1 and ΔStjy≥0) is a start processing time delay of jy on the first machine, Stjy′ is the start processing time of jy on the first machine when ΔStjy is added to Stjy (i.e., Stjy′=Stjy+ΔStjy≥Stjy), Stjy+ll′ll=1,…,n−y is the start processing time of job jy+ll on the first machine when Stjy is set to Stjy′, and Tjy+ll′ll=1,…,n−y is the tardiness of job jy+ll on the first machine when Stjy is set to Stjy′.Lemma 1.
For a fixed job permutationπ=j1,j2,…,jn of an NFSP with SSTs and RTs, if Stjy is set to Stjy′, Stjy′≥Stjy, then it has Stjy+ll′≥Stjy+ll for ll=1,…,n−y.Proof.
LetΔy+ll=Stjy+ll′−Stjy+llll=1,…,n−y denote the start processing time delay of jy+ll. Lemma 1 can be proved by using mathematical induction.
Firstly, whenll=1, with (3), it has(11)Stjy+1′=Stjy′+maxLjy,jy+1,rjy+1−Stjy′=maxStjy′+Ljy,jy+1,rjy+1=maxStjy+ΔStjy+Ljy,jy+1,rjy+1.
Obviously, whenΔStjy=0, it has Stjy+1′=Stjy+1.
WhenΔStjy>0, based on the value of rjy+1, three cases are discussed as follows:Case 1.rjy+1≤Stjy+Ljy,jy+1.Under this case, with (11) and (3), it has(12)Stjy+1′=Stjy+ΔStjy+Ljy,jy+1=Stjy+1+ΔStjy>Stjy+1.Case 2.Stjy+Ljy,jy+1<rjy+1<Stjy+ΔStjy+Ljy,jy+1.Under this case, with (11) and (3), it has(13)Stjy+1′=Stjy+ΔStjy+Ljy,jy+1>rjy+1=maxStjy+Ljy,jy+1,rjy+1=Stjy+1.Case 3.rjy+1≥Stjy+ΔStjy+Ljy,jy+1.
Under this case, with (11) and (3), it has(14)Stjy+1′=rjy+1=maxStjy+Ljy,jy+1,rjy+1=Stjy+1,and with (12)–(14), it has Stjy+1′≥Stjy+1.
Secondly, suppose Stjy+ll′≥Stjy+ll holds when 1≤ll≤k. Thus, Δy+k=Stjy+k′−Stjy+k≥0. With (3) and (11), it has(15)Stjy+k+1′=maxStjy+k′+Ljy+k,jy+k+1,rjy+k+1=maxStjy+k+Δy+k+Ljy+k,jy+k+1,rjy+k+1.
Similar to the analysis whenll=1, it has Stjy+k+1′≥Stjy+k+1.
Thus, based on mathematical induction,Stjy+ll′≥Stjy+ll holds when 1≤ll≤n−y.Lemma 2.
For a fixed job permutationπ=j1,j2,…,jn of an NFSP with SSTs and RTs, if Stjy is set to Stjy′Stjy′≥Stjy, then it has Tjy+ll′≥Tjy+ll for ll=1,…,n−y.Proof.
According to Lemma1, when Stjy′≥Stjy, it has Stjy+ll′≥Stjy+ll for ll=1,…,n−y. Then, with (5), it has(16)Tjy+ll′=maxStjy+ll′+spjy+ll−djy+ll,0,(17)Tjy+ll=maxStjy+ll+spjy+ll−djy+ll,0.
Obviously, ifStjy′=Stjy, it has Tjy+ll′=Tjy+ll for ll=1,…,n−y.
IfStjy′>Stjy, according to the value of djy+ll, three cases are discussed as follows:Case 1.djy+ll≤Stjy+ll+spjy+ll.Under this case, with (16) and (17), it has(18)Tjy+ll′=Stjy+ll′+spjy+ll−djy+ll>Stjy+ll+spjy+ll−djy+ll=maxStjy+ll+spjy+ll−djy+ll,0=Tjy+ll.Case 2.Stjy+ll+spjy+ll<djy+ll<Stjy+ll′+spjy+ll.Under this case, with (16) and (17), it has(19)Tjy+ll′=Stjy+ll′+spjy+ll−djy+ll>0=maxStjy+ll+spjy+ll−djy+ll,0=Tjy+ll.Case 3.djy+ll≥Stjy+ll′+spjy+ll.
Under this case, with (16) and (17), it has(20)Tjy+ll′=0=maxStjy+ll+spjy+ll−djy+ll,0=Tjy+ll.
Based on the above analysis, Lemma2 holds.Theorem 2.
Ifv<n and ∑i=uvwji′Tji′≥∑i=uvwjiTji and Stjv+1′≥Stjv+1, then TWTπn,u,v≥TWTπ.Proof.
According to the values ofu, two cases are discussed as follows:Case 1.u>1.From (6) and (10), it has(21)TWTπ=∑i=1u−1wjiTji+∑i=uvwjiTji+∑i=v+1nwjiTji,(22)TWTπn,u,v=∑i=1u−1wji′Tji′+∑i=uvwji′Tji′+∑i=v+1nwji′Tji′.Sinceji′=ji for i=1,…,u−1, it has(23)∑i=1u−1wji′Tji′=∑i=1u−1wjiTji.Asji′=ji for i=v+1,…,n and Stjv+1′≥Stjv+1, according to Lemma 2, it has Tji′≥Tji for i=v+1,…,n. Then, it follows that(24)∑i=v+1nwji′Tji′≥∑i=v+1nwjiTji.Finally, because∑i=uvwji′Tji′≥∑i=uvwjiTji, from (21)–(24), it has(25)TWTπn,u,v−TWTπ=∑i=uvwji′Tji′−∑i=uvwjiTji+∑i=v+1nwji′Tji′−∑i=v+1nwjiTji≥0.Case 2.u=1.
Under this case, from (6) and (10), it has(26)TWTπ=∑i=uvwjiTji+∑i=v+1nwjiTji,(27)TWTπn,u,v=∑i=uvwji′Tji′+∑i=v+1nwji′Tji′.
Since∑i=uvwji′Tji′≥∑i=uvwjiTji, with (24), (26), and (27), it has TWTπn,u,v−TWTπ≥0.
Based on the above analysis, Theorem2 holds.
By utilizing Theorem2, after ∑i=uvwji′Tji′ and Stjv+1′ have been computed, the nonimproving neighbors can be detected without calculating ∑i=v+1nwji′Tji′ if the conditions in Theorem 2 are satisfied. So, Theorem 2 is helpful in reducing the CC of Find BestNinterchangeπ. Let S123_Find BestNinterchangeπ denote Find BestNinterchangeπ with the above three strategies. Note that S123_Find BestNinterchangeπ is a key component in the local search of our proposed DE_FES.


## 4. DE_FES for TWT-NFSP with SSTs and RTs

In this section, DE_FES’s main components designed for addressing the TWT-NFSP with SSTs and RTs are explained as follows.


### 4.1. Solution Representation

As mentioned inSection 1, the original DE cannot be directly used to solve the TWT-NFSP with SSTs and RTs. Hence, a largest-order-value (LOV) rule in [35] is adopted to transform the ith individual Xi=xi,1,xi,2,…,xi,n of DE to the job permutation vector πi=ji,1,ji,2,…,ji,n. Based on LOV rule, Xi=xi,1,xi,2,…,xi,n are firstly ranked by descending order to obtain the temporary sequence φi=φi,1,φi,2,…,φi,n. Then, πi can be obtained by using the following formula:(28)ji,φi,k=k.It is worth mentioning that the LOV rule achieved better results than the famous random key rule in our previous tests.


### 4.2. DE-Based Global Search

Since DE exhibited strong global search ability in many previous studies, DE_FES’s global search is devised according to theDE/rand-to-best/1/exp scheme [28, 29, 35, 36], in which the base vector is set to the best of all individuals. This means the valuable information of the best individual can be shared among all individuals during the evolution process.


### 4.3. Fast Local Search

Denoteinsertπ,u,v is the operator of inserting ju in the vth dimension of π. The pseudocode of our fast local search is provided as follows (Algorithm 1).Algorithm 1: Fast local search.
Step 1: transform individualXit to πi_0 via the LOV rule.Step 2: perturbation phase.Setπi_t=πi_0.Fortt=1 to KKRandomly selectu and v, where u−v>n/3;πi=insertπi_t,u,v;πi_t=πi;End.Step 3: exploitation phase.Setll = 0;Doπi_1=S123_Find BestNinterchangeπi;Iffπi_1<fπi, thenπi=πi_1;elsell++;end;Whilell < 1.Step 4: iffπi≤fπi_0, then πi_0=πi.Step 5: transformπi_0 back to Xit.In Algorithm1, Step 2 is utilized to avoid plunging into local optima and it leads the search to a quite different region. In Step 3, three proposed strategies in Section 3 are adopted in S123_Find BestNinterchangeπ, which can help the local search reach more regions in the same running time. Hence, Step 3 performs a deep and efficient exploitation from the region found by Step 2. It is worth noting that S123_Find BestNinterchangeπ, designed according to the properties of the problem, is the key part that distinguishes the above local search from the local searches in the existing hybrid DE-based algorithms. This is the first time to analyze the low-bound property of the neighbors in Ninterchangeπ (see Theorem 2 in Subsection 3.4) and utilize this property to reduce the CC of local search. By utilizing the low-bound property (corresponding to strategy three) to further reduce the CC of neighbor evaluation, all neighbors in Ninterchangeπ can be evaluated in a very short time. Obviously, searching the whole neighbourhood with low CC is an efficient and ideal search mode. Therefore, S123_Find BestNinterchangeπ adopts the “comprehensive neighbourhood search scheme” similar to that in [29], instead of the “first-improvement-move neighbourhood search scheme” in [28] and the “random variable neighbourhood search scheme” in [35]. Meanwhile, due to the use of the low-bound property, the CC of S123_Find BestNinterchangeπ is smaller than that of the neighbourhood search in [29], which allows DE_FES to have a more efficient local search engine.


### 4.4. DE_FES

Based on Subsections4.1–4.3, the pseudocode of DE_FES is given as follows (Algorithm 2).Algorithm 2: Pseudocode of DE_FES.
Step 0: denoteCR is the crossover probability, random (0, 1) is the random value in the interval (0, 1), t_max is the maximum generation, t is a generation, Popt is the population with size Np at t, Xit is the ith individual with dimension NN=n inPopt, xi,lt is the lth variable of individual Xit, and tmpl is the lth variable of tmp. Each Xit is evaluated or calculated via strategy one.Step 1: inputN, Np≥3, CR∈0,1, and let bounds be lowerxi,l=0 and upperxi,l=4, l=1,…,N.Step 2: calculate and recordspji, ∑i=1nspji and Lji−1,jiji−1,ji∈1,…,n. //prepare for//utilizing strategy oneStep 3: population initialization.xi,l0=lowerxi,l+random0,1∗upperxi,l−lowerxi,l,1/2, l=1,…,Nfori=1,…,Np.Step 4: sett = 1 and select an individual Xbest0 with the minimum objective value from Pop0 as best.Step 5: evolution stage (Step 5 to Step 11). Seti=1.Step 6: setthe trial vectortmp=Xit−1 and L′=0. Randomly select r1,r2∈1,…,Npr1≠r2≠i and randomly select l∈1,…,N.Step 7: executeDE’s Mutation and Crossover.Step 7.1: lettmpl=tmpl+F∗bestl−tmpl+F∗xr1,lt−1−xr2,lt−1.Iftmpl<lowerxi,l, then let tmpl=2∗lowerxi,l−tmpl.Iftmpl>upperxi,l, then let tmpl=2∗upperxi,l−tmpl.Step 7.2: setl=lmodN+1 and L′=L′+1.Step 7.3: ifrandom0,1<CR and L′<N, go to Step 7.1.Step 8: executeDE’s Selection.Ifftmp≤fXit−1, then set Xit=tmp;else setXit=Xit−1.Step 9: ifftmp<fbest, then set best=tmp.Step 10: seti = i+1. If i≤Np, then go to Step 6.Step 11: executefast local search on best.Step 12: sett=t+1. If t≤t_max, then go to Step 5.Step 13: output the current best with its objective value.It can be seen from Algorithm2 that DE_FES remains the basic characteristic of the original DE. In DE_FES, DE’s standard crossover and mutation are utilized to generate candidate individuals, and DE’s competition scheme is still used to get new individuals. Meanwhile, DE_FES also adopts the LOV rule, fast computing strategy, and fast local search with three proposed strategies to make DE suitable for addressing the considered problem efficiently. Not only does DE_FES adopt DE’s parallel searching scheme to find promising regions, but it also utilizes an efficient local search based on three problem-dependent strategies to execute deep exploitation in these promising regions. Because the global and local searches are well balanced, DE_FES is expected to acquire satisfactory solutions in a reasonable time.


## 4.1. Solution Representation

As mentioned inSection 1, the original DE cannot be directly used to solve the TWT-NFSP with SSTs and RTs. Hence, a largest-order-value (LOV) rule in [35] is adopted to transform the ith individual Xi=xi,1,xi,2,…,xi,n of DE to the job permutation vector πi=ji,1,ji,2,…,ji,n. Based on LOV rule, Xi=xi,1,xi,2,…,xi,n are firstly ranked by descending order to obtain the temporary sequence φi=φi,1,φi,2,…,φi,n. Then, πi can be obtained by using the following formula:(28)ji,φi,k=k.It is worth mentioning that the LOV rule achieved better results than the famous random key rule in our previous tests.


## 4.2. DE-Based Global Search

Since DE exhibited strong global search ability in many previous studies, DE_FES’s global search is devised according to theDE/rand-to-best/1/exp scheme [28, 29, 35, 36], in which the base vector is set to the best of all individuals. This means the valuable information of the best individual can be shared among all individuals during the evolution process.


## 4.3. Fast Local Search

Denoteinsertπ,u,v is the operator of inserting ju in the vth dimension of π. The pseudocode of our fast local search is provided as follows (Algorithm 1).Algorithm 1: Fast local search.
Step 1: transform individualXit to πi_0 via the LOV rule.Step 2: perturbation phase.Setπi_t=πi_0.Fortt=1 to KKRandomly selectu and v, where u−v>n/3;πi=insertπi_t,u,v;πi_t=πi;End.Step 3: exploitation phase.Setll = 0;Doπi_1=S123_Find BestNinterchangeπi;Iffπi_1<fπi, thenπi=πi_1;elsell++;end;Whilell < 1.Step 4: iffπi≤fπi_0, then πi_0=πi.Step 5: transformπi_0 back to Xit.In Algorithm1, Step 2 is utilized to avoid plunging into local optima and it leads the search to a quite different region. In Step 3, three proposed strategies in Section 3 are adopted in S123_Find BestNinterchangeπ, which can help the local search reach more regions in the same running time. Hence, Step 3 performs a deep and efficient exploitation from the region found by Step 2. It is worth noting that S123_Find BestNinterchangeπ, designed according to the properties of the problem, is the key part that distinguishes the above local search from the local searches in the existing hybrid DE-based algorithms. This is the first time to analyze the low-bound property of the neighbors in Ninterchangeπ (see Theorem 2 in Subsection 3.4) and utilize this property to reduce the CC of local search. By utilizing the low-bound property (corresponding to strategy three) to further reduce the CC of neighbor evaluation, all neighbors in Ninterchangeπ can be evaluated in a very short time. Obviously, searching the whole neighbourhood with low CC is an efficient and ideal search mode. Therefore, S123_Find BestNinterchangeπ adopts the “comprehensive neighbourhood search scheme” similar to that in [29], instead of the “first-improvement-move neighbourhood search scheme” in [28] and the “random variable neighbourhood search scheme” in [35]. Meanwhile, due to the use of the low-bound property, the CC of S123_Find BestNinterchangeπ is smaller than that of the neighbourhood search in [29], which allows DE_FES to have a more efficient local search engine.


## 4.4. DE_FES

Based on Subsections4.1–4.3, the pseudocode of DE_FES is given as follows (Algorithm 2).Algorithm 2: Pseudocode of DE_FES.
Step 0: denoteCR is the crossover probability, random (0, 1) is the random value in the interval (0, 1), t_max is the maximum generation, t is a generation, Popt is the population with size Np at t, Xit is the ith individual with dimension NN=n inPopt, xi,lt is the lth variable of individual Xit, and tmpl is the lth variable of tmp. Each Xit is evaluated or calculated via strategy one.Step 1: inputN, Np≥3, CR∈0,1, and let bounds be lowerxi,l=0 and upperxi,l=4, l=1,…,N.Step 2: calculate and recordspji, ∑i=1nspji and Lji−1,jiji−1,ji∈1,…,n. //prepare for//utilizing strategy oneStep 3: population initialization.xi,l0=lowerxi,l+random0,1∗upperxi,l−lowerxi,l,1/2, l=1,…,Nfori=1,…,Np.Step 4: sett = 1 and select an individual Xbest0 with the minimum objective value from Pop0 as best.Step 5: evolution stage (Step 5 to Step 11). Seti=1.Step 6: setthe trial vectortmp=Xit−1 and L′=0. Randomly select r1,r2∈1,…,Npr1≠r2≠i and randomly select l∈1,…,N.Step 7: executeDE’s Mutation and Crossover.Step 7.1: lettmpl=tmpl+F∗bestl−tmpl+F∗xr1,lt−1−xr2,lt−1.Iftmpl<lowerxi,l, then let tmpl=2∗lowerxi,l−tmpl.Iftmpl>upperxi,l, then let tmpl=2∗upperxi,l−tmpl.Step 7.2: setl=lmodN+1 and L′=L′+1.Step 7.3: ifrandom0,1<CR and L′<N, go to Step 7.1.Step 8: executeDE’s Selection.Ifftmp≤fXit−1, then set Xit=tmp;else setXit=Xit−1.Step 9: ifftmp<fbest, then set best=tmp.Step 10: seti = i+1. If i≤Np, then go to Step 6.Step 11: executefast local search on best.Step 12: sett=t+1. If t≤t_max, then go to Step 5.Step 13: output the current best with its objective value.It can be seen from Algorithm2 that DE_FES remains the basic characteristic of the original DE. In DE_FES, DE’s standard crossover and mutation are utilized to generate candidate individuals, and DE’s competition scheme is still used to get new individuals. Meanwhile, DE_FES also adopts the LOV rule, fast computing strategy, and fast local search with three proposed strategies to make DE suitable for addressing the considered problem efficiently. Not only does DE_FES adopt DE’s parallel searching scheme to find promising regions, but it also utilizes an efficient local search based on three problem-dependent strategies to execute deep exploitation in these promising regions. Because the global and local searches are well balanced, DE_FES is expected to acquire satisfactory solutions in a reasonable time.


## 5. Simulation Results and Comparisons

### 5.1. Experimental Setup

To test the performance of DE_FES, numerical tests are carried out by using a series of randomly generated instances. Then×m combinations are set as {20, 30, 50, 70} × {5, 10, 20}. Both the setup time sji−1,ji,l and the processing time pji,l are generated from a uniform distribution [1, 100]. The release time rjiis randomly generated from 0,150nα, in which α is a control parameter. Obviously, the value of rji increases with the value of α. If rji≥Stji−1+Lji−1,ji and rji≥dji for i=1,…,n, the optimal solution can be obtained when each job ji is processed at its release time. This means that a larger value of α may reduce the difficulty of solving the problem. Hence, the values of α are set to 0, 0.2, 0.4, 0.6, 0.8, 1, and 1.5, respectively. The weight value wji is randomly generated in (0, 1). Let dp,ji be the due date of the job ji on the instance p, Cp,ji the completion time of the job ji on the instance p, and random−Cp,ji,0 a random value in −Cp,ji,0. Then, dp,ji is set as follows:Step 1: randomly generate a sequencej1,j2,…,jn for each instance p.Step 2: calculateCji for i=1,…,n.Step 3: specifydp,ji by(29)dp,ji=Cp,ji+random−Cp,ji,0.Obviously, the due datedp,ji is relatively tight, which helps maintain the company’s competitiveness. The total number of test instance is 4×3×7=84. These instances can be downloaded from https://pan.baidu.com/s/1mCdtt3MisBGf16W19xP2aA (password: cmka).DE_FES’s three main parameters are set as follows: the scaling factorF=0.7, the crossover parameter CR=0.1, and the population size popsize=30. Furthermore, KK in DE_FES’s local search is set to 3. In order to make a fair comparison, the maximum generation of a modified simulated annealing algorithm with first move strategy (MSA_FMS) [37] is set to 15×n2, and the other algorithms run the same time as MSA_FMS. Each algorithm runs 20 times independently on each instance. All procedures are implemented with Delphi 2010 and the comparisons are executed on a 2.33 GHz CPU with 3 GB memory.


### 5.2. Comparisons of DE_FES and Two Effective Algorithms

Letπiniα be the permutation or schedule in which all jobs are arranged in ascending order of release time at α, πα the permutation π at α, TWTπα the value of TWT when π=πα, avg_TWTπα the average value of TWTπα, best_TWTπα the best value of TWTπα, worst_TWTπα the worst value of TWTπα, AIPπα=TWTπiniα−avg_TWTπα/TWTπiniα×100% the relative improvement percentage of avg_TWTπα to TWTπiniα, BIPπα=TWTπiniα−best_TWTπα/TWTπiniα×100% the relative improvement percentage of best_TWTπα to TWTπiniα, CTα the calculation or evaluation times of TWTπiniα, SDα the standard deviation of TWTπα at α, Sα the set of all values of α, and Sα the number of different values in Sα. Then, four following performance measures are defined to evaluate the performances of the compared algorithms. These performance measures are AIP=∑α∈SαAIPα/Sα, BIP=∑α∈SαBIPα/Sα, CT=∑α∈SαCTα/Sα, and SD=∑α∈SαSDα/Sα.To demonstrate the effectiveness of DE_FES for the TWT-NFSP with SSTs and RTs, DE_FES is tested against two effective scheduling algorithms, i.e., a modified simulated annealing algorithm with first move strategy (MSA_FMS) [37] and an iterated greedy algorithm (IGA) [38]. MSA_FMS outperforms a well-known simulated annealing algorithm presented by Osman and Potts [37, 39]. Based on our previous tests, MSA_FMS also performs better than a hybrid genetic algorithm [40]. IGA is one of the best algorithms for solving the FSPs with SSTs [38, 41]. In addition, to show the effectiveness of the proposed strategies two and three, DE_FES is also compared with its variant DE_FES_V1, which removes these two strategies from DE_FES.The test results are given in Tables1 and 2. Table 1 shows the values of BIP, AIP, SD, and CT of each compared algorithm. Table 2 provides the details of each compared algorithm for addressing the instances 20×10, 30×10, and 70×10 under different α.Table 1
Comparison results of four algorithms.
Instance (N × m)IGAMSA_FMSDE_FES_V1DE_FESBIPAIPSDCTBIPAIPSDCTBIPAIPSDCTBIPAIPSDCT20 × 545.86345.3700.439657543.29139.3232.619600545.57143.0842.128690045.88845.5710.2914523820 × 1042.69041.6960.665631640.46736.8842.720600542.45839.7042.665701842.82242.4250.3534558920 × 2042.66542.1080.536640240.08335.4053.005600542.61940.6082.031784142.75542.6010.2285597430 × 544.29743.2720.8371507542.21239.7391.5191350743.08536.8794.0371753744.30843.8000.35618940030 × 1047.47146.2361.0161493045.65342.5791.7821350745.16440.4833.4031919747.86247.1990.47522055230 × 2055.06454.4230.5831499953.14850.1771.6921350854.17849.0513.2732162355.57955.0180.50425178050 × 557.28956.5670.5424109156.74755.7480.6233751354.86850.1243.5126741257.30556.9140.27679313250 × 1051.36350.5790.6054140650.44449.3330.6253751147.59843.2753.2056922651.35750.8080.38793064150 × 2056.07654.7990.9594050455.21653.9390.8773751153.29548.7213.1397876056.31055.7390.374119414670 × 550.05448.9620.6488075049.82349.0320.4667351645.30238.7403.86720504549.96049.3740.496173078570 × 1056.83755.8920.5658159356.72955.8480.5447351551.30644.6054.05520054357.00256.4590.367214371870 × 2060.33059.4220.5528076760.06459.2340.4657351755.58950.5373.47020520260.51859.9340.3642798744Average50.83349.9440.6623586749.49047.2701.4113263548.42043.8173.2327552550.97250.4870.373866642Table 2
Comparison results of four algorithms on 21 instances with differentα.
Instance (N, m)IGAMSA_FMSDE_FES_V1DE_FESBIPAIPSDCTBIPAIPSDCTBIPAIPSDCTBIPAIPSDCTα20 × 10049.16548.9090.314714647.35744.1462.328600448.75146.8111.133766149.07648.7000.405454760.259.23858.2150.976611656.76552.9362.179600358.34057.3300.922691559.23958.4800.604408320.462.25359.1441.544625560.11957.3942.148600662.05660.2162.909681262.27561.9910.298449660.665.59764.9080.273636762.23557.4184.363600565.15661.1013.838717065.60065.1550.336506470.826.98525.3041.098625523.70219.1292.779600427.13523.3344.309695327.13526.7330.390496081.025.08325.0660.053596722.58418.0833.553600525.25918.6845.355689725.91825.4080.435513691.510.50810.3240.395610610.5099.0831.691600610.50910.4500.186671710.50910.5090.0003622730 × 10066.16264.7221.5061545963.18559.2591.7661350763.98662.0551.0981816466.07164.4050.9732004280.270.86670.1370.5501494768.84266.7001.7751350870.63768.8351.0451917970.89670.3150.3752156440.464.58362.5662.0421484963.19859.1341.6791350764.40858.9463.8901862965.43464.4320.6862151380.648.55647.6421.0431504046.79544.2151.5971350746.24742.3062.8741958948.55548.0690.5252257170.842.16040.3941.0491480041.49338.1762.5931350638.88231.5394.9422065743.57043.3380.1952324611.031.32229.7880.7771456927.70324.5641.5231351023.54615.4986.4191889331.85631.1940.5572255531.58.6478.4050.144148478.3556.0081.540135078.4414.2033.552192698.6488.6420.01822892470 × 10075.65975.1320.3818267776.68875.2160.7237351674.36472.6041.12415462376.23575.3420.54820924560.278.68777.4390.9258786378.23177.1900.7697351275.78673.4271.74517660078.55677.9030.38421303060.482.86482.0090.5418450082.61281.7880.7547351679.44075.0923.02319700683.27582.8000.35621306500.660.42558.1810.8368343559.47257.7830.8587351751.74337.8137.99118469059.86759.1580.60022079430.852.21151.3700.7597745752.53352.1000.2387351546.68138.0424.13820219852.76252.2610.30521597771.041.86041.0840.4317749841.45240.8490.3807351532.75222.8876.61521994942.19141.7150.28021696241.56.1506.0310.084777226.1156.0110.08273515−1.620−7.6313.7512687326.1306.0350.0932115272Average48.99947.9410.7493428047.61645.1041.6823100946.30941.5973.3747558649.22848.6950.398803287It is clear from Tables1 and 2 that, in most instances, the values of AIP and BIP obtained by DE_FES are larger than those obtained by IGA and MSA_FMS and, in all instances, are larger than those obtained by DE_FES_V1. This confirms the superiority of DE_FES and clarifies the effect of utilizing the proposed strategies in DE. In addition, it can be seen that the CT values of DE_FES are obviously larger than those of IGA and MSA_FMS, and it increases quickly as the problem’s scale increases. This means that the proposed speed-up strategies can significantly reduce the CC of evaluating solutions and neighbors. More precisely, with the help of the proposed strategies, DE_FES can search more regions or solutions under the same running time. This greatly increases its probability of obtaining high-quality solutions. Besides, the SD values of DE_FES are relatively small, which indicates the robustness of DE_FES. In summary, DE_FES has powerful search ability to solve the considered problem.


## 5.1. Experimental Setup

To test the performance of DE_FES, numerical tests are carried out by using a series of randomly generated instances. Then×m combinations are set as {20, 30, 50, 70} × {5, 10, 20}. Both the setup time sji−1,ji,l and the processing time pji,l are generated from a uniform distribution [1, 100]. The release time rjiis randomly generated from 0,150nα, in which α is a control parameter. Obviously, the value of rji increases with the value of α. If rji≥Stji−1+Lji−1,ji and rji≥dji for i=1,…,n, the optimal solution can be obtained when each job ji is processed at its release time. This means that a larger value of α may reduce the difficulty of solving the problem. Hence, the values of α are set to 0, 0.2, 0.4, 0.6, 0.8, 1, and 1.5, respectively. The weight value wji is randomly generated in (0, 1). Let dp,ji be the due date of the job ji on the instance p, Cp,ji the completion time of the job ji on the instance p, and random−Cp,ji,0 a random value in −Cp,ji,0. Then, dp,ji is set as follows:Step 1: randomly generate a sequencej1,j2,…,jn for each instance p.Step 2: calculateCji for i=1,…,n.Step 3: specifydp,ji by(29)dp,ji=Cp,ji+random−Cp,ji,0.Obviously, the due datedp,ji is relatively tight, which helps maintain the company’s competitiveness. The total number of test instance is 4×3×7=84. These instances can be downloaded from https://pan.baidu.com/s/1mCdtt3MisBGf16W19xP2aA (password: cmka).DE_FES’s three main parameters are set as follows: the scaling factorF=0.7, the crossover parameter CR=0.1, and the population size popsize=30. Furthermore, KK in DE_FES’s local search is set to 3. In order to make a fair comparison, the maximum generation of a modified simulated annealing algorithm with first move strategy (MSA_FMS) [37] is set to 15×n2, and the other algorithms run the same time as MSA_FMS. Each algorithm runs 20 times independently on each instance. All procedures are implemented with Delphi 2010 and the comparisons are executed on a 2.33 GHz CPU with 3 GB memory.


## 5.2. Comparisons of DE_FES and Two Effective Algorithms

Letπiniα be the permutation or schedule in which all jobs are arranged in ascending order of release time at α, πα the permutation π at α, TWTπα the value of TWT when π=πα, avg_TWTπα the average value of TWTπα, best_TWTπα the best value of TWTπα, worst_TWTπα the worst value of TWTπα, AIPπα=TWTπiniα−avg_TWTπα/TWTπiniα×100% the relative improvement percentage of avg_TWTπα to TWTπiniα, BIPπα=TWTπiniα−best_TWTπα/TWTπiniα×100% the relative improvement percentage of best_TWTπα to TWTπiniα, CTα the calculation or evaluation times of TWTπiniα, SDα the standard deviation of TWTπα at α, Sα the set of all values of α, and Sα the number of different values in Sα. Then, four following performance measures are defined to evaluate the performances of the compared algorithms. These performance measures are AIP=∑α∈SαAIPα/Sα, BIP=∑α∈SαBIPα/Sα, CT=∑α∈SαCTα/Sα, and SD=∑α∈SαSDα/Sα.To demonstrate the effectiveness of DE_FES for the TWT-NFSP with SSTs and RTs, DE_FES is tested against two effective scheduling algorithms, i.e., a modified simulated annealing algorithm with first move strategy (MSA_FMS) [37] and an iterated greedy algorithm (IGA) [38]. MSA_FMS outperforms a well-known simulated annealing algorithm presented by Osman and Potts [37, 39]. Based on our previous tests, MSA_FMS also performs better than a hybrid genetic algorithm [40]. IGA is one of the best algorithms for solving the FSPs with SSTs [38, 41]. In addition, to show the effectiveness of the proposed strategies two and three, DE_FES is also compared with its variant DE_FES_V1, which removes these two strategies from DE_FES.The test results are given in Tables1 and 2. Table 1 shows the values of BIP, AIP, SD, and CT of each compared algorithm. Table 2 provides the details of each compared algorithm for addressing the instances 20×10, 30×10, and 70×10 under different α.Table 1
Comparison results of four algorithms.
Instance (N × m)IGAMSA_FMSDE_FES_V1DE_FESBIPAIPSDCTBIPAIPSDCTBIPAIPSDCTBIPAIPSDCT20 × 545.86345.3700.439657543.29139.3232.619600545.57143.0842.128690045.88845.5710.2914523820 × 1042.69041.6960.665631640.46736.8842.720600542.45839.7042.665701842.82242.4250.3534558920 × 2042.66542.1080.536640240.08335.4053.005600542.61940.6082.031784142.75542.6010.2285597430 × 544.29743.2720.8371507542.21239.7391.5191350743.08536.8794.0371753744.30843.8000.35618940030 × 1047.47146.2361.0161493045.65342.5791.7821350745.16440.4833.4031919747.86247.1990.47522055230 × 2055.06454.4230.5831499953.14850.1771.6921350854.17849.0513.2732162355.57955.0180.50425178050 × 557.28956.5670.5424109156.74755.7480.6233751354.86850.1243.5126741257.30556.9140.27679313250 × 1051.36350.5790.6054140650.44449.3330.6253751147.59843.2753.2056922651.35750.8080.38793064150 × 2056.07654.7990.9594050455.21653.9390.8773751153.29548.7213.1397876056.31055.7390.374119414670 × 550.05448.9620.6488075049.82349.0320.4667351645.30238.7403.86720504549.96049.3740.496173078570 × 1056.83755.8920.5658159356.72955.8480.5447351551.30644.6054.05520054357.00256.4590.367214371870 × 2060.33059.4220.5528076760.06459.2340.4657351755.58950.5373.47020520260.51859.9340.3642798744Average50.83349.9440.6623586749.49047.2701.4113263548.42043.8173.2327552550.97250.4870.373866642Table 2
Comparison results of four algorithms on 21 instances with differentα.
Instance (N, m)IGAMSA_FMSDE_FES_V1DE_FESBIPAIPSDCTBIPAIPSDCTBIPAIPSDCTBIPAIPSDCTα20 × 10049.16548.9090.314714647.35744.1462.328600448.75146.8111.133766149.07648.7000.405454760.259.23858.2150.976611656.76552.9362.179600358.34057.3300.922691559.23958.4800.604408320.462.25359.1441.544625560.11957.3942.148600662.05660.2162.909681262.27561.9910.298449660.665.59764.9080.273636762.23557.4184.363600565.15661.1013.838717065.60065.1550.336506470.826.98525.3041.098625523.70219.1292.779600427.13523.3344.309695327.13526.7330.390496081.025.08325.0660.053596722.58418.0833.553600525.25918.6845.355689725.91825.4080.435513691.510.50810.3240.395610610.5099.0831.691600610.50910.4500.186671710.50910.5090.0003622730 × 10066.16264.7221.5061545963.18559.2591.7661350763.98662.0551.0981816466.07164.4050.9732004280.270.86670.1370.5501494768.84266.7001.7751350870.63768.8351.0451917970.89670.3150.3752156440.464.58362.5662.0421484963.19859.1341.6791350764.40858.9463.8901862965.43464.4320.6862151380.648.55647.6421.0431504046.79544.2151.5971350746.24742.3062.8741958948.55548.0690.5252257170.842.16040.3941.0491480041.49338.1762.5931350638.88231.5394.9422065743.57043.3380.1952324611.031.32229.7880.7771456927.70324.5641.5231351023.54615.4986.4191889331.85631.1940.5572255531.58.6478.4050.144148478.3556.0081.540135078.4414.2033.552192698.6488.6420.01822892470 × 10075.65975.1320.3818267776.68875.2160.7237351674.36472.6041.12415462376.23575.3420.54820924560.278.68777.4390.9258786378.23177.1900.7697351275.78673.4271.74517660078.55677.9030.38421303060.482.86482.0090.5418450082.61281.7880.7547351679.44075.0923.02319700683.27582.8000.35621306500.660.42558.1810.8368343559.47257.7830.8587351751.74337.8137.99118469059.86759.1580.60022079430.852.21151.3700.7597745752.53352.1000.2387351546.68138.0424.13820219852.76252.2610.30521597771.041.86041.0840.4317749841.45240.8490.3807351532.75222.8876.61521994942.19141.7150.28021696241.56.1506.0310.084777226.1156.0110.08273515−1.620−7.6313.7512687326.1306.0350.0932115272Average48.99947.9410.7493428047.61645.1041.6823100946.30941.5973.3747558649.22848.6950.398803287It is clear from Tables1 and 2 that, in most instances, the values of AIP and BIP obtained by DE_FES are larger than those obtained by IGA and MSA_FMS and, in all instances, are larger than those obtained by DE_FES_V1. This confirms the superiority of DE_FES and clarifies the effect of utilizing the proposed strategies in DE. In addition, it can be seen that the CT values of DE_FES are obviously larger than those of IGA and MSA_FMS, and it increases quickly as the problem’s scale increases. This means that the proposed speed-up strategies can significantly reduce the CC of evaluating solutions and neighbors. More precisely, with the help of the proposed strategies, DE_FES can search more regions or solutions under the same running time. This greatly increases its probability of obtaining high-quality solutions. Besides, the SD values of DE_FES are relatively small, which indicates the robustness of DE_FES. In summary, DE_FES has powerful search ability to solve the considered problem.


## 6. Conclusions

As far as we know, this is the first paper on differential evolution (DE) for dealing with the TWT-NFSP with SSTs and RTs. In view of the complexity of the problem, a differential evolution algorithm with fast evaluating strategies (DE_FES) is developed to find satisfactory solutions of the considered problem. First, the LOV rule is adopted to ensure that DE is suitable for solving the flow-shop scheduling problems. Second, the DE-based global search is used to guide the search to enough promising regions distributed in solution space. Third, by investigating the problem’s model structure and the neighbourhood properties, three fast evaluating strategies are proposed and then applied to design a fast local search, which is used to execute thorough and fast exploitation from the promising regions obtained via DE-based search. Since the DE-based parallel search and the problem-dependent local search in DE_FES are well balanced, it can effectively solve the TWT-NFSP with SSTs and RTs. Test results manifest the efficiency and robustness of the proposed DE_FES. Future research direction is to find more valuable properties and neighbourhoods for scheduling problems and extend the DE-based algorithm to uncertain scheduling problems.



---

*Source: 8835359-2020-11-19.xml*