# Solutions to No-Wait Flow Shop Scheduling Problem Using the Flower Pollination Algorithm Based on the Hormone Modulation Mechanism

Authors: Chiwen Qu; Yanming Fu; Zhongjun Yi; Jun Tan
Journal: Complexity
 (2018)

---

## Abstract

A flower pollination algorithm is proposed based on the hormone modulation mechanism (HMM-FPA) to solve the no-wait flow shop scheduling problem (NWFSP). This algorithm minimizes the maximum accomplished time. Random keys are encoded based on an ascending sequence of components to make the flower pollination algorithm (FPA) suitable for the no-wait flow shop scheduling problem. The hormone modulation factor is introduced to strengthen information sharing among the flowers and improve FPA cross-pollination to enhance the algorithm global search performance. A variable neighborhood search strategy based on dynamic self-adaptive variable work piece blocks is constructed to improve the local search quality. Three common benchmark instances are applied to test the proposed algorithm. The result verifies that this algorithm is effective.


---

## Body

## 1. Introduction

The flow shop scheduling problem is a simplified model of many manufacturing enterprise processes, belonging to a kind of important combinatorial optimization problem. The no-wait flow shop scheduling problem is a scheduling problem developed on the flow shop scheduling problem. In manufacturing, such as chemical industry manufacturing, smelting, food processing, and pharmaceutical manufacturing, the processing of work pieces cannot be interrupted from start to finish due to manufacturing craft limitations or storage space. Optimization scheduling of this kind of process can be concluded as a solution to the no-wait flow shop scheduling problem. In a more competitive market, optimal production planning and scheduling methods can reduce enterprises’ production costs and improve their competitiveness. However, when the number of work pieces is over 3, the no-wait flow shop scheduling problem has been proven to be an NP-hard problem [1]. This problem has great engineering research value and important theoretical significance. In the past few decades, many scholars have put forward several approaches to solve such problems, which can be divided into three categories: exact solution, heuristic algorithm, and meta-heuristic method. The exact solution method includes the dynamic programming method, branch and bound method [2], enumeration method, and cutting plane method. Due to the difficulty of the no-wait flow shop scheduling problem, the exact solution is only suitable for problems with relatively small scales. With improvement in the problem size, the time complexity of the algorithm increases rapidly. Nagano and Miyata [3] presented a mechanism that describes in detail how to construct a heuristic algorithm to solve the no-wait flow shop scheduling problem. Laha and Chakraborty [4] developed a constructive heuristic algorithm based on the job insertion principle. Framinan et al. [5] tackled the no-wait flow shop problem with a constructive heuristic algorithm based on an analogy with the objective of minimizing makespan. In order to obtain good approximate solutions, a new constructive heuristic named QUARTS is proposed by Nagano et al. [6]. With the total flow time as the criterion, many heuristics were examined by Bonney and Gundry [7], King and Spachis [8], Nawaz et al. [9], Rajendran [10], Gangadharan and Rajendran [11], and Ronconi and Armentano [12]. Grabowski and Pempera [13] used different local search algorithms to solve the no-wait flow shop problem for minimizing makespan. A heuristic algorithm is able to acquire the solutions within short time, but the solutions are usually worse in quality.The meta-heuristic algorithm based on swarm optimization algorithm can acquire the optimal solution or approximate optimal solution to the no-wait flow shop scheduling problem within feasible time and space complexity. Considering the no-wait flow shop scheduling problem with makespan minimization, Aldowaisan and Allahverdi [14] investigated six heuristics based on simulated annealing (SA) and genetic algorithms (GA). Pan et al., respectively, used the discrete particle swarm optimization algorithm [15], differential evolution algorithm [16], hybrid discrete particle swarm algorithm [17], artificial bee colony algorithm [18], and harmony search algorithm [19] to solve the no-wait flow shop scheduling problem. The goal was to minimize the maximum accomplishment time. For the same criterion, Fink and Voß [20] employed the simulated annealing algorithm and Tabu search algorithm, and Liu et al. [21] introduced a hybrid particle swarm optimization algorithm based on local search and self-adaptive learning mechanism. An ant colony optimization algorithm that improved the ant colony algorithm based on local search was applied separately to solutions for NWFSP [22, 23]. Nagano et al. [24, 25] designed an algorithm based on the hybrid meta-heuristic evolutionary clustering search (ECS_NSL). By testing the standard instances and comparison with algorithms provided by other literature, ECS_NSL performance is better. Qi et al. [26] presented a fast local neighborhood search algorithm (FLNS) with makespan criterion. The experimental results show that FLNS outperformed IHA, IBHLS, GA-VNS, and DHS in the solution quality and robustness. Deng et al. [27] proposed a cooperative evolutionary quantum genetic algorithm based on the competition mechanism to solve NWFSP. By maintaining population diversity and a competition mechanism to balance the development and exploit algorithm abilities, good solution results were obtained. Davendra et al. [28] introduced a new discrete self-organizing migrating algorithm. Through standard testing instances, it was shown in the statistical results that the algorithm is better than the heuristic algorithm in the literature.FPA is a swarm intelligent bionic algorithm [29, 30] proposed by Yang et al. in 2012. The algorithm is highly regarded by scholars due to its simple structure, few parameter settings, relatively stronger global search performance, and easy implementation. Many scholars put forward an improvement method based on the FPA and popularized into industrial and agricultural production. Based on the basic FPA, Wang and Zhou [31] added a neighborhood search strategy and dimension-by-dimension greedy search method to improve cross-pollination. In comparison with other intelligent algorithms, the proposed algorithm is better. Abdel-Raouf and Abdel-Baset [32] proposed a hybrid FPA based on a combination particle swarm optimization algorithm and FPA to solve the constrained optimization problem. FPA is applied to solve the economic load dispatch problem [33–35]. Bekdaş et al. [36] used FPA to optimize the sizing truss structure. Abdelaziz et al. [37, 38] used FPA to obtain the optimal capacitor placement and sizing in distribution systems. They obtained the solution using combined economic and emission dispatch. In order to improve the accuracy and stability of cluster analysis, Wang et al. [39] proposed an FPA cluster analysis method with a bee pollinator. As shown in the experimental statistical results, the algorithm is better than DE, CS, ABC, PSO, FPA, and k-means algorithms in convergence, cluster accuracy, and stability performance. In order to solve the image segmentation problem via multilevel thresholding, Ouadfel and Taleb-Ahmed [40] presented an algorithm that combined social spider optimization (SSO) and FPA. The results showed that the proposed algorithm outperforms the PSO and BAT algorithms. Flower pollen gamete cross-pollination relies on animals like bees and butterflies; however, this is ignored in information sharing among the flowers in the basic FPA. Thus, the algorithm is inclined to engage in local optimum.Aiming at minimizing the NWFAP accomplishment time, the hormone modulation factor is introduced based on the FPA to realize information sharing and improve the global search performance. A variable neighborhood search strategy based on dynamic self-adaptive variable work piece blocks is constructed to improve the local search quality. The computational results based on benchmark instances show the effectiveness of the proposed algorithm.


## 2. No-Wait Flow Shop Scheduling Problem Model and Description

Based on the traditional flow shop scheduling problem, the no-wait flow shop scheduling problem is described as follows: Assuming thatn work pieces need to be processed on m machines in the same sequences (without any preemption and interruption). There is a continuous process through m machines without interruption when a work piece is started on the first machine. Here, the processing time ti,j of work piece i on machine j is provided. At any time, one work piece can be processed on only one machine and one machine can process only one work piece. To satisfy the no-wait constraints, on a given machine, the work piece completion time should be equal to the work piece start time on the next machine. For the purpose of minimizing the maximum accomplishment time, NWFSP can be described by the mathematics model below:
(1)Cπ1,k=∑j=1ktπ1,j,k=1,2,…,m,Cπi,k=Cπi−1,1+∑j=1ktπi,j+Δπi,i=2,3,…,n;k=1,2,…,m,Δπi=max0,maxCπi−1,k−Cπi−1,1−∑j=1k−1tπi,j,2≤i≤n,2≤k≤m,π∗=argCπn,m→min,where π=π1,π2,…,πn is a scheduling sequence of n work pieces, tπi,k is the processing time required by the job πi on the machine k, Cπi,k is the accomplishment time of the job πi on the machine k, and π∗ is the scheduling sequence aiming at the maximum accomplishment time minimum.


## 3. Flower Pollination Algorithm

FPA is a new swarm optimization algorithm based on flower pollination behavior. The basic thought is as follows: (i) Each flower is mapped as an individual in the population. (ii) Cross-pollination is conducted by the switch probabilityp∈0,1. (iii) Self-pollination is conducted at the probability (1−p).
(1)
Cross-pollination. Cross-pollination refers to animals like bees and butterflies pollinate among different kinds of flowers using thelevy flight mode. The flower update mode is shown as
(2)xit+1=xit+δ⋅levyλ⋅xbestt−xit,where δ is the scaling factor, xit is the flower individual xi at generation t, xbestt is the current optimal individual found among all flower individuals at generation t, and levyλ is the random number subordinated to Levy distribution.
(3)levyλ~λΓλsinπλ/2π⋅1s1+λs≫s0>0.For calculation convenience, Yang et al. [30] used the method proposed by Mantegna to calculate the step size s. The calculation method is shown below:
(4)s=uv1/λ,u~N0,σ2,v~N0,1,σ=Γ1+λ×sinπ×λ/2Γ1+λ/2⋅λ⋅2λ−1/21/λ,where λ=3/2 and Γλ is a standard gamma function.
(2)
Self-pollination. Self-pollination simulates close-distance pollination among the same species of flowers. The pollination method is shown below:
(5)xit+1=xit+ε⋅xjt−xkt,where xit is the flower individual xi at generation t, ε is the random number subordinated to uniform distribution in [0,1], and xjt and xkt are the different flower individuals.


## 4. FPA Based on the Hormone Modulation Mechanism

### 4.1. Coding of the Algorithm

A job-permutation-based encoding scheme has been widely used in solving the no-wait flow shop scheduling problem. The job scheduling problem is discrete; it is impossible to use the standard FPA encoding scheme to directly express the sequence of work pieces. A random key coding principle based on the work piece ascending order is applied in this paper to realize the reflecting relationship between individual flowers and the scheduling sequence. Let the solution vector bexi=xi1,xi2,…xij…,xin, where there are two meanings for each vector xij including its own value xij and the sequence number j representing the value of the new generating sequence. The process from a real vector of flower individual to the work pieces’ sequence is as follows: Each dimension vector value of xi is sequenced according to the ascending sequence principle; thus, θi=θi1,θi2,…θik…,θin. The sequence of work piece πi,θik can be acquired through (6). A case on transformation from flower individual to sequence of work piece is provided in Table 1.
(6)πi,θik=j.Table 1
Transformation from a flower individualxi to sequence of work piece πi.
Dimensionj
1
2
3
4
5
xij
3.56
2.23
−0.29
1.48
−2.97
θik
−2.97
−0.29
1.48
2.23
3.56
πi,θik
5
3
4
2
1


### 4.2. Population Initialization

The quality of the initial population is significantly affected by the intelligent swarm optimization algorithm solution result. In order to ensure initial population diversity and improve the algorithm convergence velocity, the NEH heuristic algorithm is applied to acquire the first solution to the initial population. The remainingnsize−1 (nsize is the size of population) solutions to the initial population randomly emerge.


### 4.3. The Cross-Pollination Operator Based on Hormone Modulation Mechanism

In standard flower pollination algorithm cross-pollination, the update of flower individuals is determined only by the current best solution. However, the solution is greatly influenced by the other flowers around it. Meanwhile, the flowers can be responsive to the surrounding flowers and adjusts itself in real time. Thus, inspired by hormone modulation mechanism, FARHY [41] discovered a general changing principle of biological hormone secretion: monotonicity and nonnegativity. The ascending and declining principles of hormone secretion abide by the Hill characteristic function, which is shown in
(7)fupg=gntn+gn,(8)fdowng=tntn+gn,where tt>0 and g refer to the independent variable and threshold of the function, respectively. nn≥1 is the coefficient of the Hill function. Setting the hormone and regulatory hormone as x and y, respectively, the relationship between the velocity vx of hormone secretion x and the concentration cy of regulatory hormone y is shown below:
(9)vx=α⋅fup,downcy+vx0,where vx0 and α are the basic secretion velocity and common hormone coefficient, respectively.Gu et al. [42] designed a hormone modulation mechanism and achieved great effect. In this paper, the hormone modulation mechanism is introduced into the FPA algorithm on the original cross-pollination to give the flower update method better global pollination performance. The flower update method is shown below:
(10)xit+1=xit+δ⋅levyλ⋅xbestt−xit+Hf⋅randn0,dim,where randn0,dim can satisfy the dim dimension random number in standard Gaussian distribution and Hf is the hormone regulatory function as shown in
(11)Hf=artanfavg−fi2fmax−fmin2+favg−fi2,fi<favgartanfmax−fmin2fmax−fmin2+fi2,fi≥favg,where fi is the flower fitness value xi, and fmax, fmin, and favg are the maximum fitness value, the minimum fitness value, and the average fitness value, respectively, of nt flowers that are closest to the flower xi in the current population. The solution method is shown in Algorithm 1.Algorithm 1: The pseudo code of the cross-pollination operator based on hormone modulation mechanism.
Step1: fork=1:size
Step2:distk=xk−xi%xi is the current solution
Step3: end for
Step4: Setdist array in order according to the ascending sequence.
Step5: Select the minimumnt flower locations, and record them as index1,index2,…,indexnt.
Step6:fmax=maxfitxindexj,j∈1,nt
Step7:fmin=minfitxindexj,j∈1,nt
Step8:favg=1/nt⋅∑j=1ntfitxindexj
Step9: iffi<favg
Step10:xi'←xi+δ⋅levyλ⋅xbest−xi+artanfavg−fi2/fmax−fmin2+favg−fi2⋅randn0,dim
Step11: else
Step12:xi'←xi+δ⋅levyλ⋅xbest−xi+artanfmax−fmin2/fmax−fmin2+fi2⋅randn0,dim
Step13: end if.According to the regulation in (11), the local location of flower xi is better whenfi≥favg. So fewer adjustment ranges should be conducted to the original flower. The local location of flower xi is worse whenfi<favg. The endocrine systems make the flower xi move to a better location by distributing more hormones.


### 4.4. The Variable Neighborhood Search of Dynamic Self-Adaptive Variable Work Piece Blocks

As a specific scheduling problem, the no-wait flow shop scheduling problem solutions are difficult and easily trapped into local optimum. The local search improvement can enhance the search performance for the swarm intelligent algorithm [43]. Hansen and Mladenović [44] proved that the probability of obtaining the optimal solution through systematic transformation of the neighborhood structure is higher than that from search results using a single neighborhood structure. A variable neighborhood search based on dynamic self-adaptive variable work piece blocks for local search is constructed in this paper. For a solution r=r1,r2,…,rn, the local search process in this paper is described in Algorithm 2.Algorithm 2: The pseudo code of variable neighborhood search of dynamic self-adaptive variable work piece blocks.
Step1: Calculate the accomplishment timeCmaxrbest of the current optimal solution (rbest).
Step2: Calculate thestep.
step←max_step−iteritermax⋅maxstep,
whereiter is the iteration, itermaxis the largest iteration, max_step is the maximum of work piece blocks, and step is the size of current work piece blocks.
Step3: Generates∈1,n (random location), and delete consecutive step work pieces in rbestfrom location s to form a module. The deleted module is set to be r=r1,r2,…,rn, and the remaining work pieces form the sequence r′r′1,r′2,…,r′n−step.
Step4:fork=1:step
Step5:  Successively insertrk into corresponding location in r′.
Step6:  keep the result of the best location.
Step7: end.
Step8: Acquire a new solutionr′. If Cmaxrbest>Cmaxr′, rbest=r′.
Step9: Ifiter<itermax, iter=iter+1, then turn to Step 3. Or else, stop the algorithm.Compared with the traditional swap and insert neighborhood search methods, the variable neighborhood search strategy with dynamic self-adaptive variable work piece blocks can make the algorithm able to search in a broader search space. This increases the probability of acquiring better solutions. In early iterations, the algorithm has good global search ability due to the relatively large size of the work piece blocks. With increasing iterations, the size of the work piece blocksstep is adjusted dynamically, which makes the algorithm possess better local search ability.


### 4.5. Process of Solutions

The detailed procedure for the proposed algorithm is shown in Algorithm3.Algorithm 3: The pseudo code of HMM-FPA.
Step 1. Objective functionfxi=Cxi,x=x1,x2,…,xn.
Step 2. Initialize the parameters ofnsize, p, itermax et al.
Step 3. Generate the first flower individual by NEH heuristic algorithm, and generate (nsize−1) flower individuals randomly to construct the initial population.
Step 4. Evaluate its fitnessfitxi=fxi, and find the best solution xbest.
Step 5. while (stopping criterion is not satisfied).
Step 6.  fori=1 to nsize
Step 7.   Generate a random numberr that obey the uniformly distribution.
Step 8.   ifr < p.
Step 9.     Perform the cross-pollination operator based on hormone modulation mechanism (described in Algorithm1).
Step 10.   else
Step 11.     Perform the self-pollination operator.
xi'←xi+ε⋅xj−xkj≠k
Step 12.   end if.
Step 13.   Calculate the fitnessfitxi' of the new flower gamete xi'.
Step 14.   iffitxi'>fitxi, update xi with xi'.
Step 15.   iffitxi'>fitxbest, update xbest with xi'.
Step 16.  end for
Step 17.  Perform the variable domain search of dynamic self-adaptive variable work piece blocks operator for the best flower individualxbest (described in Algorithm 2).
Step 18.end while


## 4.1. Coding of the Algorithm

A job-permutation-based encoding scheme has been widely used in solving the no-wait flow shop scheduling problem. The job scheduling problem is discrete; it is impossible to use the standard FPA encoding scheme to directly express the sequence of work pieces. A random key coding principle based on the work piece ascending order is applied in this paper to realize the reflecting relationship between individual flowers and the scheduling sequence. Let the solution vector bexi=xi1,xi2,…xij…,xin, where there are two meanings for each vector xij including its own value xij and the sequence number j representing the value of the new generating sequence. The process from a real vector of flower individual to the work pieces’ sequence is as follows: Each dimension vector value of xi is sequenced according to the ascending sequence principle; thus, θi=θi1,θi2,…θik…,θin. The sequence of work piece πi,θik can be acquired through (6). A case on transformation from flower individual to sequence of work piece is provided in Table 1.
(6)πi,θik=j.Table 1
Transformation from a flower individualxi to sequence of work piece πi.
Dimensionj
1
2
3
4
5
xij
3.56
2.23
−0.29
1.48
−2.97
θik
−2.97
−0.29
1.48
2.23
3.56
πi,θik
5
3
4
2
1


## 4.2. Population Initialization

The quality of the initial population is significantly affected by the intelligent swarm optimization algorithm solution result. In order to ensure initial population diversity and improve the algorithm convergence velocity, the NEH heuristic algorithm is applied to acquire the first solution to the initial population. The remainingnsize−1 (nsize is the size of population) solutions to the initial population randomly emerge.


## 4.3. The Cross-Pollination Operator Based on Hormone Modulation Mechanism

In standard flower pollination algorithm cross-pollination, the update of flower individuals is determined only by the current best solution. However, the solution is greatly influenced by the other flowers around it. Meanwhile, the flowers can be responsive to the surrounding flowers and adjusts itself in real time. Thus, inspired by hormone modulation mechanism, FARHY [41] discovered a general changing principle of biological hormone secretion: monotonicity and nonnegativity. The ascending and declining principles of hormone secretion abide by the Hill characteristic function, which is shown in
(7)fupg=gntn+gn,(8)fdowng=tntn+gn,where tt>0 and g refer to the independent variable and threshold of the function, respectively. nn≥1 is the coefficient of the Hill function. Setting the hormone and regulatory hormone as x and y, respectively, the relationship between the velocity vx of hormone secretion x and the concentration cy of regulatory hormone y is shown below:
(9)vx=α⋅fup,downcy+vx0,where vx0 and α are the basic secretion velocity and common hormone coefficient, respectively.Gu et al. [42] designed a hormone modulation mechanism and achieved great effect. In this paper, the hormone modulation mechanism is introduced into the FPA algorithm on the original cross-pollination to give the flower update method better global pollination performance. The flower update method is shown below:
(10)xit+1=xit+δ⋅levyλ⋅xbestt−xit+Hf⋅randn0,dim,where randn0,dim can satisfy the dim dimension random number in standard Gaussian distribution and Hf is the hormone regulatory function as shown in
(11)Hf=artanfavg−fi2fmax−fmin2+favg−fi2,fi<favgartanfmax−fmin2fmax−fmin2+fi2,fi≥favg,where fi is the flower fitness value xi, and fmax, fmin, and favg are the maximum fitness value, the minimum fitness value, and the average fitness value, respectively, of nt flowers that are closest to the flower xi in the current population. The solution method is shown in Algorithm 1.Algorithm 1: The pseudo code of the cross-pollination operator based on hormone modulation mechanism.
Step1: fork=1:size
Step2:distk=xk−xi%xi is the current solution
Step3: end for
Step4: Setdist array in order according to the ascending sequence.
Step5: Select the minimumnt flower locations, and record them as index1,index2,…,indexnt.
Step6:fmax=maxfitxindexj,j∈1,nt
Step7:fmin=minfitxindexj,j∈1,nt
Step8:favg=1/nt⋅∑j=1ntfitxindexj
Step9: iffi<favg
Step10:xi'←xi+δ⋅levyλ⋅xbest−xi+artanfavg−fi2/fmax−fmin2+favg−fi2⋅randn0,dim
Step11: else
Step12:xi'←xi+δ⋅levyλ⋅xbest−xi+artanfmax−fmin2/fmax−fmin2+fi2⋅randn0,dim
Step13: end if.According to the regulation in (11), the local location of flower xi is better whenfi≥favg. So fewer adjustment ranges should be conducted to the original flower. The local location of flower xi is worse whenfi<favg. The endocrine systems make the flower xi move to a better location by distributing more hormones.


## 4.4. The Variable Neighborhood Search of Dynamic Self-Adaptive Variable Work Piece Blocks

As a specific scheduling problem, the no-wait flow shop scheduling problem solutions are difficult and easily trapped into local optimum. The local search improvement can enhance the search performance for the swarm intelligent algorithm [43]. Hansen and Mladenović [44] proved that the probability of obtaining the optimal solution through systematic transformation of the neighborhood structure is higher than that from search results using a single neighborhood structure. A variable neighborhood search based on dynamic self-adaptive variable work piece blocks for local search is constructed in this paper. For a solution r=r1,r2,…,rn, the local search process in this paper is described in Algorithm 2.Algorithm 2: The pseudo code of variable neighborhood search of dynamic self-adaptive variable work piece blocks.
Step1: Calculate the accomplishment timeCmaxrbest of the current optimal solution (rbest).
Step2: Calculate thestep.
step←max_step−iteritermax⋅maxstep,
whereiter is the iteration, itermaxis the largest iteration, max_step is the maximum of work piece blocks, and step is the size of current work piece blocks.
Step3: Generates∈1,n (random location), and delete consecutive step work pieces in rbestfrom location s to form a module. The deleted module is set to be r=r1,r2,…,rn, and the remaining work pieces form the sequence r′r′1,r′2,…,r′n−step.
Step4:fork=1:step
Step5:  Successively insertrk into corresponding location in r′.
Step6:  keep the result of the best location.
Step7: end.
Step8: Acquire a new solutionr′. If Cmaxrbest>Cmaxr′, rbest=r′.
Step9: Ifiter<itermax, iter=iter+1, then turn to Step 3. Or else, stop the algorithm.Compared with the traditional swap and insert neighborhood search methods, the variable neighborhood search strategy with dynamic self-adaptive variable work piece blocks can make the algorithm able to search in a broader search space. This increases the probability of acquiring better solutions. In early iterations, the algorithm has good global search ability due to the relatively large size of the work piece blocks. With increasing iterations, the size of the work piece blocksstep is adjusted dynamically, which makes the algorithm possess better local search ability.


## 4.5. Process of Solutions

The detailed procedure for the proposed algorithm is shown in Algorithm3.Algorithm 3: The pseudo code of HMM-FPA.
Step 1. Objective functionfxi=Cxi,x=x1,x2,…,xn.
Step 2. Initialize the parameters ofnsize, p, itermax et al.
Step 3. Generate the first flower individual by NEH heuristic algorithm, and generate (nsize−1) flower individuals randomly to construct the initial population.
Step 4. Evaluate its fitnessfitxi=fxi, and find the best solution xbest.
Step 5. while (stopping criterion is not satisfied).
Step 6.  fori=1 to nsize
Step 7.   Generate a random numberr that obey the uniformly distribution.
Step 8.   ifr < p.
Step 9.     Perform the cross-pollination operator based on hormone modulation mechanism (described in Algorithm1).
Step 10.   else
Step 11.     Perform the self-pollination operator.
xi'←xi+ε⋅xj−xkj≠k
Step 12.   end if.
Step 13.   Calculate the fitnessfitxi' of the new flower gamete xi'.
Step 14.   iffitxi'>fitxi, update xi with xi'.
Step 15.   iffitxi'>fitxbest, update xbest with xi'.
Step 16.  end for
Step 17.  Perform the variable domain search of dynamic self-adaptive variable work piece blocks operator for the best flower individualxbest (described in Algorithm 2).
Step 18.end while


## 5. Algorithm Simulation and Experimental Test

### 5.1. Test Settings

In order to testify the performance of the proposed algorithm for solving NWFSP, we conducted experiments using three common benchmark problems: (i) 8 small-scale instances provided by Carlier [45]: Car1 to Car8 that consist of eight problem instances with small job and machine sizes but large processing time; (ii) 21 instances provided by Reeves [46]: Rec01 to Rec41 that have 21 different problems with 20~75 work pieces and 5~20 machines; and (iii) 120 large-scale instances provided by Taillard [47]: Ta001 to Ta120 including 120 problem instances with 12 subsets of different sizes, ranging from 20 work pieces and 5 machines to 500 work pieces and 20 machines. In order to avoid the influence of random factors, each test instance runs independently 20 times. The algorithm in this paper was tested using Matlab 2016a coding on the platform with Win 10, Intel Core i5-4210U 2.4 GHZ, and 4 GB memory.To compare the results obtained from the experiments, the relative deviation (RD) between solutions from relative algorithms and the best known results up to now were collected. BRD, ARD, and WRD, respectively, refer to the optimal relative deviation, average relative deviation, and the worst relative deviation. The RD, BRD, ARD and WRD are calculated as follows:(12)RDi=Ci−C∗C∗∗100%,BRD=Cbest−C∗C∗∗100%,ARD=1R∑i=1RCi−C∗C∗∗100%,WRD=Cworst−C∗C∗∗100%,where Ci is the solution generated by a specific algorithm, R is the run times, C∗ is the best solution found, Cbestis the best solution over R runs, and Cworst is the worst solution over R runs. Obviously, the smaller the ARD value, the better the algorithm’s performance is. In addition, ACT [48, 49] and ARPT [48, 49] are also recorded to indicate the CPU time efforts.
(13)ACTi=1I∑i=1ITi,h,∀i=1,…I,ARPTh=1I∑i=1ITi,h−ACTiACT+1,∀i=1,…I,h=1,…,H,where Ti,h is the CPU time required by the algorithm h in instance i, I refers to the number of instances, and H is the number of swarm intelligent algorithms.This section includes four subsections. The first part discusses the influence of the work piece block size. Secondly, comparison of particle swarm optimization algorithm (PSO), cuckoo search algorithm (CS), flower pollination algorithm (FPA), and the proposed algorithm will be introduced. Third is the comparison of HMM-FPA with some other existing intelligent algorithms. Finally, for solving the large-scale problems, 120 Taillard instances are executed to identify the effectiveness of the proposed algorithm.


### 5.2. Analysis on Simulation Results

#### 5.2.1. Discussion on the Settings of the Size of Work Piece Blocks

In order to discuss the influence of the work piece block size in the neighborhood search of the proposed algorithm, seven Rec instances (Rec01, Rec07, Rec13, Rec19, Rec25, Rec31, and Rec37) and eight Car instances (Car1~Car8) are used to test. For the Car instances, the size of work piece blocksstep is, respectively, set as 1, 2, 3, 4, 6, and the dynamic self-adaptive variable work piece blocks (DSVWB). The step is, respectively, set as 1, 3, 5, 8, 10, and DSVWB for the seven Rec instances. Here, the values of C∗ for Car instances and Rec instances are the optimal solution found so far.It is clear from Tables2 and 3 that the proposed algorithm with DSVWB is the winner, since the ARD and WRD obtained by the DSVWB are better than or equal to those obtained by other step. The larger the work piece block size is, the better the algorithm search performance is. However, when the size of the work piece blocks surpasses a certain value, the larger the size is, the worse the search performance of the algorithm is.Table 2
Performance comparison of the tested work piece blocks with different size for Cars.
Problem
n×m
C∗
step = 1
step = 2
step = 3
step = 4
step = 6
DACWB
BRD
ARD
WRD
BRD
ARD
WRD
BRD
ARD
WRD
BRD
ARD
WRD
BRD
ARD
WRD
BRD
ARD
WRD
Car1
11 × 5
8142
0.00
0.15
0.26
0.00
0.03
0.28
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
Car2
13 × 4
8242
0.00
0.08
0.18
0.00
0.03
0.16
0.00
0.02
0.18
0.00
0.04
0.18
0.00
0.00
0.00
0.00
0.06
0.15
Car3
12 × 5
8866
0.00
0.03
0.07
0.00
0.03
0.09
0.00
0.03
0.08
0.00
0.01
0.07
0.00
0.00
0.00
0.00
0.05
0.08
Car4
14 × 4
9195
0.00
0.45
0.80
0.00
0.29
0.69
0.00
0.22
0.71
0.00
0.12
0.71
0.00
0.01
0.05
0.00
0.02
0.06
Car5
10 × 6
9159
0.00
0.40
1.87
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.45
2.05
0.00
0.00
0.00
Car6
8 × 9
9690
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
Car7
7 × 7
7705
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
Car8
8 × 8
9372
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.02
0.16
0.00
0.00
0.00
Average
0
0.139
0.398
0
0.048
0.153
0
0.034
0.121
0
0.0212
0.12
0
0.06
0.283
0
0.016
0.0363
C∗ is the best solution found.Table 3
Performance comparison of the tested work piece blocks with different size for Recs.
Problem
n×m
C∗
step = 1
step = 3
step = 5
step = 8
step = 10
DACWB
BRD
ARD
WRD
BRD
ARD
WRD
BRD
ARD
WRD
BRD
ARD
WRD
BRD
ARD
WRD
BRD
ARD
WRD
Rec01
20 × 5
1526
0.00
0.15
0.41
0.00
0.04
0.25
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
Rec07
20 × 10
2042
0.00
1.07
2.27
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
Rec13
20 × 15
2545
0.00
0.45
1.98
0.00
0.18
0.33
0.00
0.05
0.25
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
Rec19
30 × 10
2850
0.00
0.95
1.85
0.00
0.45
1.20
0.00
0.58
1.14
0.00
0.30
1.17
0.00
0.23
0.50
0.00
0.00
0.00
Rec25
30 × 15
3593
0.13
0.78
1.65
0.00
0.41
1.22
0.00
0.32
0.91
0.00
0.21
0.85
0.00
0.40
0.88
0.00
0.09
0.65
Rec31
50 × 10
4311
1.41
2.71
3.29
0.15
1.07
2.11
0.14
0.75
1.41
0.32
0.49
1.04
0.31
0.52
1.03
0.13
0.20
0.49
Rec37
75 × 20
8014
3.50
4.17
4.91
1.01
2.37
3.58
0.97
1.60
2.05
0.95
1.55
1.99
1.02
1.70
2.23
0.25
0.67
1.40
Average
0.720
1.469
2.337
0.166
0.646
1.241
0.159
0.471
0.823
0.181
0.364
0.721
0.190
0.407
0.663
0.0543
0.137
0.363
C∗ is the best solution found.As for the causes, the neighborhood search in this paper can be essentially regarded as a disturbance operation that can easily remove the current solution to other neighboring areas with partial characteristics of the current solution.The size of disturbance step exerts greater effects on algorithm performance. An excessively long disturbance step can easily lead to loss of great characteristics in the current solution, similar to the random emergence process. If the disturbance step is excessively short and the movement range of the current solution is excessively small, it is easier to fall into the local optimum position.Figures1 and 2 are the line charts of the average relative error (ARE) for solving Car instances and Rec instances. It can be indicated from Figures 1 and 2 that ARE solved by DSVWB is equivalent to or better than the results solved by other fixed steps. The size of oversized or undersize work piece blocks will decrease the local search ability of the neighborhood search. Apparently, taking the time complexity of the algorithm, it is reasonable to adopt the dynamic self-adaptive variable work piece block size, which not only balances the local and global search ability of the algorithm but also reduces the algorithm calculation time.Figure 1
The ARD line chart for Car set problems with differentstep.Figure 2
The ARD line chart for Rec set problems with differentstep.


#### 5.2.2. Comparison of PSO, CS, FPA, and HMM-FPA

Four algorithms were selected as contrast algorithms in the simulation experiment to evaluate the proposed algorithm’s performance, that is, particle swarm optimization algorithm (PSO) [15], cuckoo search algorithm (CS) [50], and flower pollination algorithm (FPA) [29], respectively. Eight Car instances (Car1~Car8) were used in this test.The same coding method is applied to the four algorithms as shown in Section4.1. The algorithm parameter settings are shown below:The flower pollination algorithm (FPA) has the size of the populationnsize=50, selection probability of pollination method p=0.8, and the largest iterations itermax=5000.The particle swarm optimization algorithm (PSO) has the population sizensize=50, the iterations itermax=5000, linear inertia wmax=0.9 and wmin=0.4, learning factor C1=C2=1.4692, and search range of particles xmax=4 and xmin=−4.The cuckoo search algorithm (CS) has the population sizensize=50, pa=0.25, λ=1.5, and the largest iterations itermax=5000.The flower pollination algorithm based on hormone modulation mechanism (HMM-FPA) has the population sizensize=50, pollination method selection probability p=0.8, the largest work piece blocks max_step=4, and the largest iterations itermax=5000.The statistical results of 20 independent runs for the four algorithms are listed in Table4, including the best relative deviation (BRD), the average relative deviation (ARD), and the average CPU time (Tavg) for finding the optimal solutions in the iterations. Here, the values of C∗ for Car1~Car8 are the optimal solution found so far. In order to be able to perform a fair comparison among swarm intelligent algorithms, we use ARPT as a measure of the computational effort. Results in terms of average CPU time and the ARPT are shown in Table 4 (the last two rows represent the average CPU time and the ARPT, resp.).Table 4
The comparative statistical results between FPA, PSO, CS, and HMM-FPA.
Problem
n×m
C∗
PSO
CS
FPA
HMM-FPA
BRD
ARD
Tavg
BRD
ARD
Tavg
BRD
ARD
Tavg
BRD
ARD
Tavg
Car1
11 × 5
8142
0.00
0.00
0.01
0.00
0.00
0.01
0.00
0.00
0.008
0.00
0.00
0.01
Car2
13 × 4
8242
0.60
1.24
0.01
0.18
2.75
0.01
0.64
1.85
0.008
0.00
0.06
0.01
Car3
12 × 5
8866
0.73
0.85
0.01
0.00
0.89
0.01
0.70
2.61
0.008
0.00
0.05
0.01
Car4
14 × 4
9195
3.54
4.46
0.02
0.65
3.79
0.015
3.49
6.45
0.010
0.00
0.02
0.011
Car5
10 × 6
9159
2.35
3.78
0.01
0.54
2.20
0.01
0.00
3.96
0.009
0.00
0.00
0.01
Car6
8 × 9
9690
0.00
0.00
0.004
0.00
0.00
0.008
0.00
0.00
0.005
0.00
0.00
0.006
Car7
7 × 7
7705
0.00
0.50
0.004
0.00
0.15
0.008
0.00
3.60
0.004
0.00
0.00
0.005
Car8
8 × 8
9372
0.00
0.15
0.004
0.00
0.20
0.008
0.00
0.19
0.005
0.00
0.00
0.006
Average
0.90
1.37
0.01
0.17
1.25
0.01
0.60
2.33
0.01
0.00
0.02
0.01
APRT
0.9707
1.1952
0.8331
1.0011
C∗ is the best solution.It can be indicated from Table4 that PSO can only acquire the optimal solution in four instances including Car 1, Car 6, Car 7, and Car 8. The optimal solutions to test instances of Car 2, Car 4, and Car 5 cannot be acquired by basic cuckoo algorithm. The basic FPA contributes nothing to test instances of Car 2, Car 3, and Car 4. The proposed algorithm can acquire all the optimal solutions to Car instances and is better in BRD and ARD than the other three swarm optimization algorithms.The average CPU time and APRT of the HMM-FPA algorithm is less than that of the CS algorithm, but more than that of the PSO and the standard FPA algorithm. However, its solution accuracy is apparently better than that of the other three swarm intelligent algorithms. This demonstrates that the global searching ability of HMM-FPA is effective and HMM-FPA is suitable for solving NWFSP.In the basic particle swarm optimization algorithm, the particle position update is determined by the particle at the current optimal position and the historical optimum position that the particle has experienced, neglecting the influence of the particles at the common nonoptimal position (the particles may be near the global optimum position). The algorithm is easily trapped into the local optimum position. In selecting the host bird nest position, a kind of random search method with levy distribution is applied in the cuckoo algorithm. It has been proven that the cuckoo algorithm is better than the basic particle swarm optimization algorithm [50] in searching for the global optimum solution. Thus, in solutions to NWFSP, the cuckoo algorithm is better than the basic particle swarm optimization algorithm. However, similarly, the two algorithms ignore the influence of other neighboring particle positions on themselves.In the HMM-FPA algorithm mentioned in this paper, when a single individual flower conducts cross-pollination with the help of animal vectors like bees and butterflies, the influence of neighboring flowers on itself and the irritability of the individual towards the flower’s status at other positions are both considered. Furthermore, certain adjustment is appropriately conducted on its position. For the proposed algorithm, the flower positions are updated by (10), and the neighboring individual flower factors are sufficiently considered. When fi<favg, the flower performance of flower i is better (in a better position), leading to a smaller adjustment range in the flower position. Conversely, the performance of flower i is worse (in a worse position), leading to a larger adjustment range in the flower position.The HMM-FPA sufficiently considers the flower information at the optimal position and neighboring flower positions, which combines the global expansion ability and local development ability, so the solution performance of the proposed algorithm is apparently better than that of other swarm intelligent algorithms.Figure3 is the statistical result from the makespan for PSO, CS, FPA, and HMM-FPA. It is shown that the makespan of the HMM-FPA is the least except Car1 and Car6 (the four algorithms can search the global optimal theoretical value).Figure 3
The makespan of the statistical results for the different algorithms.Figures4–11 are the statistical results from box diagrams for PSO, CS, FPA, and HMM-FPA. It can be seen from Figures 4–11 that the stability of HMM-FPA is better than the compared algorithm for solving Car instances, which illustrates the good robustness.Figure 4
ANOVA tests of Car1.Figure 5
ANOVA tests of Car2.Figure 6
ANOVA tests of Car3.Figure 7
ANOVA tests of Car4.Figure 8
ANOVA tests of Car5.Figure 9
ANOVA tests of Car6.Figure 10
ANOVA tests of Car7.Figure 11
ANOVA tests of Car8.


#### 5.2.3. Comparison of HMM-FPA and Existing Intelligent Algorithm

In order to further verify the algorithm performance, the proposed algorithm is compared with other intelligent algorithms. Comparisons are carried out with sex typical methods from the literatures, including the discrete particle swarm optimization algorithm (DPSO) [51], improved iterated greedy algorithm with a Tabu-based reconstruction strategy (TMIIG) [52], improved iterated greedy algorithm (IIGA) [53], DE-based approach (HDE) [54], effective hybrid particle swarm optimization (HPSO) [21], and GA [55]. Results of DPSO, TMIIG, IIGA, HDE, HPSO, and GA come from the corresponding literatures. The 21 Rec problems (Rec01~Rec41) are used as test instances. Comparison results are shown in Table 5. Table 5 shows that IMIIG only conducts statistics on the ARD perspective without statistics on BRD and Tavg. GA only conducts statistics on BRD.Table 5
The comparative statistical results between HMM-PFA and DPSO, IIGA, HPSO, HDE, TMIIG, and GA.
Problem
n×m
Best
DPSO
IIGA
HPSO
HDE
TMIIG
GA
HMM-PFA
BRD
ARD
Tavg
BRD
ARD
Tavg
BRD
ARD
Tavg
BRD
ARD
Tavg
BRD
ARD
Tavg
BRD
ARD
Tavg
BRD
ARD
Tavg
Rec1
20 × 5
1526
0.00
0.00
0.01
0.00
0.00
0.02
0.26
0.66
3.90
0.00
0.00
3.10
—
0.00
0.20
0.39
—
—
0.00
0.00
0.018
Rec3
20 × 5
1361
0.00
0.00
0.00
0.00
0.00
0.02
0.00
0.44
4.80
0.00
0.00
3.10
—
0.00
0.20
0.22
—
—
0.00
0.00
0.018
Rec5
20 × 5
1511
0.00
0.00
0.02
0.00
0.00
0.02
0.33
0.60
4.10
0.00
0.07
3.10
—
0.00
0.20
0.60
—
—
0.00
0.04
0.019
Rec7
20 × 10
2042
0.00
0.00
0.00
0.00
0.00
0.02
0.00
0.54
6.60
0.00
0.00
3.90
—
0.00
0.20
2.25
—
—
0.00
0.00
0.020
Rec9
20 × 10
2042
0.00
0.00
0.00
0.00
0.00
0.02
0.05
0.39
6.70
0.00
0.00
3.80
—
0.00
0.20
0.78
—
—
0.00
0.00
0.021
Rec11
20 × 10
1881
0.00
0.00
0.01
0.00
0.00
0.02
0.00
1.06
7.00
0.00
0.16
3.90
—
0.00
0.20
1.33
—
—
0.00
0.00
0.020
Rec13
20 × 15
2545
0.00
0.00
0.01
0.00
0.00
0.02
0.00
0.63
11.00
0.00
0.00
5.10
—
0.00
0.20
0.79
—
—
0.00
0.00
0.015
Rec15
20 × 15
2529
0.00
0.00
0.00
0.00
0.00
0.02
0.00
0.36
8.60
0.00
0.00
5.20
—
0.00
0.20
1.42
—
—
0.00
0.00
0.016
Rec17
20 × 15
2587
0.00
0.00
0.00
0.00
0.00
0.02
0.00
0.15
8.60
0.00
0.00
5.20
—
0.00
0.20
0.46
—
—
0.00
0.00
0.015
Rec19
30 × 10
2850
0.00
0.11
0.02
0.00
0.00
0.04
0.63
1.37
23.00
0.00
0.07
10.40
—
0.00
0.45
3.58
—
—
0.00
0.00
0.030
Rec21
30 × 10
2821
0.00
0.11
0.04
0.00
0.18
0.04
0.78
1.17
24.00
0.00
0.18
10.20
—
0.07
0.45
2.48
—
—
0.00
0.15
0.036
Rec23
30 × 10
2700
0.00
0.07
0.05
0.00
0.00
0.04
0.11
1.30
24.00
0.00
0.11
10.40
—
0.00
0.45
3.07
—
—
0.00
0.01
0.032
Rec25
30 × 15
3593
0.00
0.17
0.03
0.00
0.00
0.04
0.64
1.22
32.00
0.00
0.03
15.00
—
0.00
0.45
1.92
—
—
0.00
0.09
0.401
Rec27
30 × 15
3431
0.00
0.26
0.06
0.00
0.00
0.05
0.00
1.17
39.00
0.00
0.17
14.80
—
0.01
0.45
3.91
—
—
0.00
0.07
0.451
Rec29
30 × 15
3291
0.00
0.06
0.02
0.00
0.00
0.06
0.36
1.34
31.00
0.00
0.18
14.90
—
0.03
0.45
2.80
—
—
0.00
0.13
0.480
Rec31
50 × 10
4311
0.12
0.39
0.33
0.00
0.28
0.11
1.07
1.83
122.00
0.32
0.56
3.80
—
0.13
1.25
5.03
—
—
0.13
0.20
0.713
Rec33
50 × 10
4428
0.25
0.72
0.34
0.41
0.68
0.10
1.78
3.32
116.00
0.20
0.88
3.70
—
0.30
1.25
6.39
—
—
0.00
0.54
0.715
Rec35
50 × 10
4397
0.00
0.39
0.34
0.00
0.16
0.10
0.84
1.80
105.00
0.25
0.75
3.70
—
0.19
1.25
5.39
—
—
0.00
0.83
0.690
Rec37
75 × 20
8014
0.27
0.69
1.16
0.32
0.69
0.18
2.08
2.86
635.00
0.44
0.81
14.70
—
0.33
2.81
18.73
—
—
0.25
0.67
1.982
Rec39
75 × 20
8428
0.19
0.70
0.99
0.26
0.62
0.18
1.28
2.50
897.00
0.25
0.71
14.60
—
0.46
2.81
17.29
—
—
0.20
0.65
2.014
Rec41
75 × 20
8442
0.36
0.71
0.88
0.37
0.75
0.18
1.90
3.19
883.00
0.00
0.73
14.70
—
0.44
2.81
17.13
—
—
0.00
0.69
2.135
Average
0.06
0.21
0.21
0.06
0.16
0.06
0.58
1.33
142.49
0.07
0.26
7.97
—
0.09
0.79
4.57
—
—
0.03
0.20
0.47
APRT
0.0067
0.0078
4.3732
1.5113
0.0808
0.0202For BRD, the accuracy of results acquired from HMM-PFA is generally better than that from other algorithms. The advantages of some instances are more obvious, such as rec 31, rec 33, and rec 41. The average BRD value acquired from HMM-PFA is, respectively, fewer than that of DPSO, IIGA, HPSO, HDE, and GA by 0.03, 0.03, 0.55, 0.04, and 4.54. It can be concluded that the BRD performance of the proposed algorithm is superior to the comparison algorithms. For the average ARD values, the quality of solutions acquired from HMM-PFA is better than that of other algorithms, which illustrates that HMM-PFA can effectively solve NWFSP with good robustness.The statistical results on the last two lines in Table5 show that the average CPU time and ARPT of HMM-PFA are better than that of HPSO, HDE, and TIIIG, but slightly inferior to that of DPSO and IIGA algorithms. Comprehensive analysis shows that the dynamic self-adaptive variable work piece block (DSVWB) neighborhood search increases the time complexity in the HMM-PFA search process. However, from the BRD and ARD average, it can be concluded that HMM-PFA is significantly better than the other 6 algorithms.Figures12 and 13 are the Gantt charts for the optimal results obtained using HMM-FPA for Rec07 and Rec27.Figure 12
Gantt chart of the solution for Rec07.Figure 13
Gantt chart of the solution for Rec27.All in all, by applying the hormone modulation mechanism and the dynamic self-adaptive variable work piece block strategy, the HMM-PFA search quality can be enhanced, and the global search exploration and the local search exploitation can be well balanced. HMM-PFA is another effective method for solving no-wait flow shop scheduling problems with good quality.


#### 5.2.4. Comparison for the Large-Scale Instances

Taillard’s benchmark instances are used to test HMM-PFA algorithm performance for solving the large-scale no-wait flow shop scheduling problem. The data files for these instances are downloaded from the websitehttp://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html. Taillard’s benchmark instances include 120 problems. According to the scale of the instances, they are divided into 12 groups, with 10 in each group. The proposed algorithm is compared with the ACO-SA [56] algorithm and IIGA [53] algorithm. The ACO-SA algorithm only performed the test of the first 110 instances (Ta001–Ta110) and did not test the 10 instances in 500 × 20 scale (Ta111–Ta120). Therefore, the statistical results for the 120 instances in 500×20 scale are contained in Table 6, marked with “∗”. From the statistical results in Tables 7 and 6, we can find that without the statistics for the instances in 500×20 scale, the BRD and ARD of the HMM-PFA algorithm are better than those of the ACO-SA algorithm. Besides, the HMM-PFA algorithm has less average CPU time and ARPT than the ACO-SA algorithm. Compared with the IIGA algorithm, we can find that the ARD of the HMM-PFA algorithm is better. The results from the above analysis indicate that the HMM-PFA algorithm is effective in solving the large-scale no-wait flow shop scheduling problem.Table 6
Comparison of results based on Taillard’s benchmark instances.
n×m
ACO-SA
IIGA
HMM-PFA
BRD
ARD
Tavg
BRD
ARD
Tavg
BRD
ARD
Tavg
20 × 5
0
0
0.28
—
0
—
0
0
0.0161
20 × 10
0
0.320
0.44
—
0.01
—
0
0
0.021
20 × 20
0
0.493
0.56
—
0.02
—
0
0
0.026
50 × 5
0.346
0.852
1.79
—
1.34
—
0.22
0.37
0.888
50 × 10
0.145
0.885
2.96
—
0.71
—
0.04
0.18
1.584
50 × 20
0.095
1.770
3.18
—
0.58
—
0.05
0.37
2.202
100 × 5
0.847
2.899
30.20
—
2.78
—
0.62
1.13
25.974
100 × 10
0.607
1.781
57.23
—
1.7
—
0.47
0.97
48.559
100 × 20
0.599
1.546
61.26
—
1.46
—
0.41
0.69
73.573
200 × 10
2.009
2.695
189.17
—
2.49
—
1.26
1.49
162.453
200 × 20
1.633
2.190
200.82
—
2.1
—
1.04
1.35
221.214
500 × 20
—
—
—
—
2.94
—
2.10
2.31
883.166
Average
0.571
1.403
49.808
—
1.199 (1.344)∗
—
0.374 (0.518)∗
0.595 (0.738)∗
48.774 (118.306)∗
∗ is the statistical results for the 120 instances in 500 × 20 scale.Table 7
The HMM-PFA statistical result to solve 120 Taillard’s benchmark instances.
n×m
Instance
Opt
BRD
ARD
Tavg
n×m
Instance
Opt
BRD
ARD
Tavg
20 × 5
Ta001
1486
0
0
0.016
100 × 5
Ta061
6361
0.57
1.07
25.557
Ta002
1528
0
0
0.017
Ta062
6212
0.90
1.13
26.021
Ta003
1460
0
0
0.016
Ta063
6104
0.48
0.87
25.998
Ta004
1588
0
0
0.016
Ta064
5999
0.93
1.50
26.59
Ta005
1449
0
0
0.017
Ta065
6179
0.44
0.82
25.709
Ta006
1481
0
0
0.016
Ta066
6056
0.18
0.76
26.054
Ta007
1483
0
0
0.016
Ta067
6221
0.37
1.21
26.121
Ta008
1482
0
0
0.016
Ta068
6109
1.34
1.99
25.993
Ta009
1469
0
0
0.016
Ta069
6355
0.90
1.34
25.578
Ta010
1377
0
0
0.015
Ta070
6365
0.06
0.61
26.121
20 × 10
Ta011
2044
0
0
0.021
100 × 10
Ta071
8055
0.62
0.81
47.664
Ta012
2166
0
0
0.02
Ta072
7853
0.45
1.88
50.001
Ta013
1940
0
0
0.02
Ta073
8016
0.41
0.95
49.654
Ta014
1811
0
0
0.021
Ta074
8328
0.41
0.75
49.721
Ta015
1933
0
0
0.022
Ta075
7936
0.38
0.93
48.332
Ta016
1892
0
0
0.021
Ta076
7773
0.68
0.86
49.024
Ta017
1963
0
0
0.021
Ta077
7846
0.43
0.75
47.238
Ta018
2057
0
0
0.021
Ta078
7880
0.56
1.15
47.967
Ta019
1973
0
0
0.022
Ta079
8131
0.30
0.85
48.054
Ta020
2051
0
0
0.021
Ta080
8092
0.46
0.74
47.937
20 × 20
Ta021
2973
0
0
0.025
100 × 20
Ta081
10,675
0.09
0.21
75.345
Ta022
2852
0
0
0.026
Ta082
10,562
0.94
1.32
72.49
Ta023
3013
0
0
0.026
Ta083
10,587
0.73
0.89
70.376
Ta024
3001
0
0
0.026
Ta084
10,588
0.30
0.63
73.298
Ta025
3003
0
0
0.025
Ta085
10,506
0.10
0.42
71.439
Ta026
2998
0
0
0.025
Ta086
10,623
0.57
0.76
76.296
Ta027
3052
0
0
0.027
Ta087
10,793
0.29
0.53
74.387
Ta028
2839
0
0
0.027
Ta088
10,801
0.45
0.91
72.363
Ta029
3009
0
0
0.027
Ta089
10,703
0.14
0.53
75.832
Ta030
2979
0
0
0.026
Ta090
10,747
0.47
0.73
73.901
50 × 5
Ta031
3160
0.28
0.36
0.892
200 × 10
Ta091
15,225
1.22
1.48
159.072
Ta032
3432
0.26
0.53
0.902
Ta092
14,990
0.75
0.95
165.921
Ta033
3210
0.09
0.27
0.912
Ta093
15,257
1.07
1.40
162.209
Ta034
3338
0.30
0.50
0.89
Ta094
15,103
0.70
0.89
167.011
Ta035
3356
0.60
0.72
0.89
Ta095
15,088
1.47
1.79
158.001
Ta036
3346
0.00
0.04
0.914
Ta096
14,976
1.65
1.85
159.928
Ta037
3231
0.09
0.29
0.911
Ta097
15,277
1.07
1.23
163.785
Ta038
3235
0.12
0.17
0.799
Ta098
15,133
1.37
1.62
164.902
Ta039
3070
0.33
0.52
0.85
Ta099
14,985
1.77
1.98
158.397
Ta040
3317
0.15
0.26
0.922
Ta100
15,213
1.57
1.75
165.299
50 × 10
Ta041
4274
0.00
0.04
1.568
200 × 20
Ta101
19,531
0.65
0.77
220.632
Ta042
4177
0.05
0.21
1.57
Ta102
19,942
1.44
1.79
217.997
Ta043
4099
0.00
0.09
1.587
Ta103
19,759
1.16
1.31
218.318
Ta044
4399
0.05
0.14
1.563
Ta104
19,759
1.22
1.66
225.638
Ta045
4322
0.05
0.37
1.569
Ta105
19,697
0.90
1.05
237.689
Ta046
4289
0.02
0.18
1.601
Ta106
19,826
0.94
1.31
209.396
Ta047
4420
0.00
0.13
1.602
Ta107
19,946
0.87
1.63
217.332
Ta048
4318
0.07
0.11
1.59
Ta108
19,872
1.37
1.62
219.744
Ta049
4155
0.00
0.15
1.584
Ta109
19,784
1.08
1.20
216.655
Ta050
4283
0.16
0.37
1.601
Ta110
19,768
0.80
1.23
228.738
50 × 20
Ta051
6129
0.00
0.11
2.195
500 × 20
Ta111
46,121
1.96
2.20
873.905
Ta052
5725
0.00
0.18
2.221
Ta112
46,627
1.65
1.69
878.009
Ta053
5862
0.00
0.15
2.199
Ta113
46,013
2.12
2.54
890.675
Ta054
5788
0.24
0.42
2.198
Ta114
46,396
1.52
1.65
897.432
Ta055
5886
0.00
1.77
2.205
Ta115
46,251
2.07
2.33
870.002
Ta056
5863
0.12
0.20
2.208
Ta116
46,490
2.17
2.45
896.329
Ta057
5962
0.12
0.25
2.197
Ta117
46,043
1.96
2.15
869.428
Ta058
5926
0.02
0.20
2.199
Ta118
46,368
1.63
1.80
877.917
Ta059
5876
0.00
0.22
2.195
Ta119
46,240
3.76
3.92
879.013
Ta060
5957
0.03
0.22
2.199
Ta120
46,292
2.18
2.36
898.953


## 5.1. Test Settings

In order to testify the performance of the proposed algorithm for solving NWFSP, we conducted experiments using three common benchmark problems: (i) 8 small-scale instances provided by Carlier [45]: Car1 to Car8 that consist of eight problem instances with small job and machine sizes but large processing time; (ii) 21 instances provided by Reeves [46]: Rec01 to Rec41 that have 21 different problems with 20~75 work pieces and 5~20 machines; and (iii) 120 large-scale instances provided by Taillard [47]: Ta001 to Ta120 including 120 problem instances with 12 subsets of different sizes, ranging from 20 work pieces and 5 machines to 500 work pieces and 20 machines. In order to avoid the influence of random factors, each test instance runs independently 20 times. The algorithm in this paper was tested using Matlab 2016a coding on the platform with Win 10, Intel Core i5-4210U 2.4 GHZ, and 4 GB memory.To compare the results obtained from the experiments, the relative deviation (RD) between solutions from relative algorithms and the best known results up to now were collected. BRD, ARD, and WRD, respectively, refer to the optimal relative deviation, average relative deviation, and the worst relative deviation. The RD, BRD, ARD and WRD are calculated as follows:(12)RDi=Ci−C∗C∗∗100%,BRD=Cbest−C∗C∗∗100%,ARD=1R∑i=1RCi−C∗C∗∗100%,WRD=Cworst−C∗C∗∗100%,where Ci is the solution generated by a specific algorithm, R is the run times, C∗ is the best solution found, Cbestis the best solution over R runs, and Cworst is the worst solution over R runs. Obviously, the smaller the ARD value, the better the algorithm’s performance is. In addition, ACT [48, 49] and ARPT [48, 49] are also recorded to indicate the CPU time efforts.
(13)ACTi=1I∑i=1ITi,h,∀i=1,…I,ARPTh=1I∑i=1ITi,h−ACTiACT+1,∀i=1,…I,h=1,…,H,where Ti,h is the CPU time required by the algorithm h in instance i, I refers to the number of instances, and H is the number of swarm intelligent algorithms.This section includes four subsections. The first part discusses the influence of the work piece block size. Secondly, comparison of particle swarm optimization algorithm (PSO), cuckoo search algorithm (CS), flower pollination algorithm (FPA), and the proposed algorithm will be introduced. Third is the comparison of HMM-FPA with some other existing intelligent algorithms. Finally, for solving the large-scale problems, 120 Taillard instances are executed to identify the effectiveness of the proposed algorithm.


## 5.2. Analysis on Simulation Results

### 5.2.1. Discussion on the Settings of the Size of Work Piece Blocks

In order to discuss the influence of the work piece block size in the neighborhood search of the proposed algorithm, seven Rec instances (Rec01, Rec07, Rec13, Rec19, Rec25, Rec31, and Rec37) and eight Car instances (Car1~Car8) are used to test. For the Car instances, the size of work piece blocksstep is, respectively, set as 1, 2, 3, 4, 6, and the dynamic self-adaptive variable work piece blocks (DSVWB). The step is, respectively, set as 1, 3, 5, 8, 10, and DSVWB for the seven Rec instances. Here, the values of C∗ for Car instances and Rec instances are the optimal solution found so far.It is clear from Tables2 and 3 that the proposed algorithm with DSVWB is the winner, since the ARD and WRD obtained by the DSVWB are better than or equal to those obtained by other step. The larger the work piece block size is, the better the algorithm search performance is. However, when the size of the work piece blocks surpasses a certain value, the larger the size is, the worse the search performance of the algorithm is.Table 2
Performance comparison of the tested work piece blocks with different size for Cars.
Problem
n×m
C∗
step = 1
step = 2
step = 3
step = 4
step = 6
DACWB
BRD
ARD
WRD
BRD
ARD
WRD
BRD
ARD
WRD
BRD
ARD
WRD
BRD
ARD
WRD
BRD
ARD
WRD
Car1
11 × 5
8142
0.00
0.15
0.26
0.00
0.03
0.28
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
Car2
13 × 4
8242
0.00
0.08
0.18
0.00
0.03
0.16
0.00
0.02
0.18
0.00
0.04
0.18
0.00
0.00
0.00
0.00
0.06
0.15
Car3
12 × 5
8866
0.00
0.03
0.07
0.00
0.03
0.09
0.00
0.03
0.08
0.00
0.01
0.07
0.00
0.00
0.00
0.00
0.05
0.08
Car4
14 × 4
9195
0.00
0.45
0.80
0.00
0.29
0.69
0.00
0.22
0.71
0.00
0.12
0.71
0.00
0.01
0.05
0.00
0.02
0.06
Car5
10 × 6
9159
0.00
0.40
1.87
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.45
2.05
0.00
0.00
0.00
Car6
8 × 9
9690
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
Car7
7 × 7
7705
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
Car8
8 × 8
9372
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.02
0.16
0.00
0.00
0.00
Average
0
0.139
0.398
0
0.048
0.153
0
0.034
0.121
0
0.0212
0.12
0
0.06
0.283
0
0.016
0.0363
C∗ is the best solution found.Table 3
Performance comparison of the tested work piece blocks with different size for Recs.
Problem
n×m
C∗
step = 1
step = 3
step = 5
step = 8
step = 10
DACWB
BRD
ARD
WRD
BRD
ARD
WRD
BRD
ARD
WRD
BRD
ARD
WRD
BRD
ARD
WRD
BRD
ARD
WRD
Rec01
20 × 5
1526
0.00
0.15
0.41
0.00
0.04
0.25
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
Rec07
20 × 10
2042
0.00
1.07
2.27
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
Rec13
20 × 15
2545
0.00
0.45
1.98
0.00
0.18
0.33
0.00
0.05
0.25
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
Rec19
30 × 10
2850
0.00
0.95
1.85
0.00
0.45
1.20
0.00
0.58
1.14
0.00
0.30
1.17
0.00
0.23
0.50
0.00
0.00
0.00
Rec25
30 × 15
3593
0.13
0.78
1.65
0.00
0.41
1.22
0.00
0.32
0.91
0.00
0.21
0.85
0.00
0.40
0.88
0.00
0.09
0.65
Rec31
50 × 10
4311
1.41
2.71
3.29
0.15
1.07
2.11
0.14
0.75
1.41
0.32
0.49
1.04
0.31
0.52
1.03
0.13
0.20
0.49
Rec37
75 × 20
8014
3.50
4.17
4.91
1.01
2.37
3.58
0.97
1.60
2.05
0.95
1.55
1.99
1.02
1.70
2.23
0.25
0.67
1.40
Average
0.720
1.469
2.337
0.166
0.646
1.241
0.159
0.471
0.823
0.181
0.364
0.721
0.190
0.407
0.663
0.0543
0.137
0.363
C∗ is the best solution found.As for the causes, the neighborhood search in this paper can be essentially regarded as a disturbance operation that can easily remove the current solution to other neighboring areas with partial characteristics of the current solution.The size of disturbance step exerts greater effects on algorithm performance. An excessively long disturbance step can easily lead to loss of great characteristics in the current solution, similar to the random emergence process. If the disturbance step is excessively short and the movement range of the current solution is excessively small, it is easier to fall into the local optimum position.Figures1 and 2 are the line charts of the average relative error (ARE) for solving Car instances and Rec instances. It can be indicated from Figures 1 and 2 that ARE solved by DSVWB is equivalent to or better than the results solved by other fixed steps. The size of oversized or undersize work piece blocks will decrease the local search ability of the neighborhood search. Apparently, taking the time complexity of the algorithm, it is reasonable to adopt the dynamic self-adaptive variable work piece block size, which not only balances the local and global search ability of the algorithm but also reduces the algorithm calculation time.Figure 1
The ARD line chart for Car set problems with differentstep.Figure 2
The ARD line chart for Rec set problems with differentstep.


### 5.2.2. Comparison of PSO, CS, FPA, and HMM-FPA

Four algorithms were selected as contrast algorithms in the simulation experiment to evaluate the proposed algorithm’s performance, that is, particle swarm optimization algorithm (PSO) [15], cuckoo search algorithm (CS) [50], and flower pollination algorithm (FPA) [29], respectively. Eight Car instances (Car1~Car8) were used in this test.The same coding method is applied to the four algorithms as shown in Section4.1. The algorithm parameter settings are shown below:The flower pollination algorithm (FPA) has the size of the populationnsize=50, selection probability of pollination method p=0.8, and the largest iterations itermax=5000.The particle swarm optimization algorithm (PSO) has the population sizensize=50, the iterations itermax=5000, linear inertia wmax=0.9 and wmin=0.4, learning factor C1=C2=1.4692, and search range of particles xmax=4 and xmin=−4.The cuckoo search algorithm (CS) has the population sizensize=50, pa=0.25, λ=1.5, and the largest iterations itermax=5000.The flower pollination algorithm based on hormone modulation mechanism (HMM-FPA) has the population sizensize=50, pollination method selection probability p=0.8, the largest work piece blocks max_step=4, and the largest iterations itermax=5000.The statistical results of 20 independent runs for the four algorithms are listed in Table4, including the best relative deviation (BRD), the average relative deviation (ARD), and the average CPU time (Tavg) for finding the optimal solutions in the iterations. Here, the values of C∗ for Car1~Car8 are the optimal solution found so far. In order to be able to perform a fair comparison among swarm intelligent algorithms, we use ARPT as a measure of the computational effort. Results in terms of average CPU time and the ARPT are shown in Table 4 (the last two rows represent the average CPU time and the ARPT, resp.).Table 4
The comparative statistical results between FPA, PSO, CS, and HMM-FPA.
Problem
n×m
C∗
PSO
CS
FPA
HMM-FPA
BRD
ARD
Tavg
BRD
ARD
Tavg
BRD
ARD
Tavg
BRD
ARD
Tavg
Car1
11 × 5
8142
0.00
0.00
0.01
0.00
0.00
0.01
0.00
0.00
0.008
0.00
0.00
0.01
Car2
13 × 4
8242
0.60
1.24
0.01
0.18
2.75
0.01
0.64
1.85
0.008
0.00
0.06
0.01
Car3
12 × 5
8866
0.73
0.85
0.01
0.00
0.89
0.01
0.70
2.61
0.008
0.00
0.05
0.01
Car4
14 × 4
9195
3.54
4.46
0.02
0.65
3.79
0.015
3.49
6.45
0.010
0.00
0.02
0.011
Car5
10 × 6
9159
2.35
3.78
0.01
0.54
2.20
0.01
0.00
3.96
0.009
0.00
0.00
0.01
Car6
8 × 9
9690
0.00
0.00
0.004
0.00
0.00
0.008
0.00
0.00
0.005
0.00
0.00
0.006
Car7
7 × 7
7705
0.00
0.50
0.004
0.00
0.15
0.008
0.00
3.60
0.004
0.00
0.00
0.005
Car8
8 × 8
9372
0.00
0.15
0.004
0.00
0.20
0.008
0.00
0.19
0.005
0.00
0.00
0.006
Average
0.90
1.37
0.01
0.17
1.25
0.01
0.60
2.33
0.01
0.00
0.02
0.01
APRT
0.9707
1.1952
0.8331
1.0011
C∗ is the best solution.It can be indicated from Table4 that PSO can only acquire the optimal solution in four instances including Car 1, Car 6, Car 7, and Car 8. The optimal solutions to test instances of Car 2, Car 4, and Car 5 cannot be acquired by basic cuckoo algorithm. The basic FPA contributes nothing to test instances of Car 2, Car 3, and Car 4. The proposed algorithm can acquire all the optimal solutions to Car instances and is better in BRD and ARD than the other three swarm optimization algorithms.The average CPU time and APRT of the HMM-FPA algorithm is less than that of the CS algorithm, but more than that of the PSO and the standard FPA algorithm. However, its solution accuracy is apparently better than that of the other three swarm intelligent algorithms. This demonstrates that the global searching ability of HMM-FPA is effective and HMM-FPA is suitable for solving NWFSP.In the basic particle swarm optimization algorithm, the particle position update is determined by the particle at the current optimal position and the historical optimum position that the particle has experienced, neglecting the influence of the particles at the common nonoptimal position (the particles may be near the global optimum position). The algorithm is easily trapped into the local optimum position. In selecting the host bird nest position, a kind of random search method with levy distribution is applied in the cuckoo algorithm. It has been proven that the cuckoo algorithm is better than the basic particle swarm optimization algorithm [50] in searching for the global optimum solution. Thus, in solutions to NWFSP, the cuckoo algorithm is better than the basic particle swarm optimization algorithm. However, similarly, the two algorithms ignore the influence of other neighboring particle positions on themselves.In the HMM-FPA algorithm mentioned in this paper, when a single individual flower conducts cross-pollination with the help of animal vectors like bees and butterflies, the influence of neighboring flowers on itself and the irritability of the individual towards the flower’s status at other positions are both considered. Furthermore, certain adjustment is appropriately conducted on its position. For the proposed algorithm, the flower positions are updated by (10), and the neighboring individual flower factors are sufficiently considered. When fi<favg, the flower performance of flower i is better (in a better position), leading to a smaller adjustment range in the flower position. Conversely, the performance of flower i is worse (in a worse position), leading to a larger adjustment range in the flower position.The HMM-FPA sufficiently considers the flower information at the optimal position and neighboring flower positions, which combines the global expansion ability and local development ability, so the solution performance of the proposed algorithm is apparently better than that of other swarm intelligent algorithms.Figure3 is the statistical result from the makespan for PSO, CS, FPA, and HMM-FPA. It is shown that the makespan of the HMM-FPA is the least except Car1 and Car6 (the four algorithms can search the global optimal theoretical value).Figure 3
The makespan of the statistical results for the different algorithms.Figures4–11 are the statistical results from box diagrams for PSO, CS, FPA, and HMM-FPA. It can be seen from Figures 4–11 that the stability of HMM-FPA is better than the compared algorithm for solving Car instances, which illustrates the good robustness.Figure 4
ANOVA tests of Car1.Figure 5
ANOVA tests of Car2.Figure 6
ANOVA tests of Car3.Figure 7
ANOVA tests of Car4.Figure 8
ANOVA tests of Car5.Figure 9
ANOVA tests of Car6.Figure 10
ANOVA tests of Car7.Figure 11
ANOVA tests of Car8.


### 5.2.3. Comparison of HMM-FPA and Existing Intelligent Algorithm

In order to further verify the algorithm performance, the proposed algorithm is compared with other intelligent algorithms. Comparisons are carried out with sex typical methods from the literatures, including the discrete particle swarm optimization algorithm (DPSO) [51], improved iterated greedy algorithm with a Tabu-based reconstruction strategy (TMIIG) [52], improved iterated greedy algorithm (IIGA) [53], DE-based approach (HDE) [54], effective hybrid particle swarm optimization (HPSO) [21], and GA [55]. Results of DPSO, TMIIG, IIGA, HDE, HPSO, and GA come from the corresponding literatures. The 21 Rec problems (Rec01~Rec41) are used as test instances. Comparison results are shown in Table 5. Table 5 shows that IMIIG only conducts statistics on the ARD perspective without statistics on BRD and Tavg. GA only conducts statistics on BRD.Table 5
The comparative statistical results between HMM-PFA and DPSO, IIGA, HPSO, HDE, TMIIG, and GA.
Problem
n×m
Best
DPSO
IIGA
HPSO
HDE
TMIIG
GA
HMM-PFA
BRD
ARD
Tavg
BRD
ARD
Tavg
BRD
ARD
Tavg
BRD
ARD
Tavg
BRD
ARD
Tavg
BRD
ARD
Tavg
BRD
ARD
Tavg
Rec1
20 × 5
1526
0.00
0.00
0.01
0.00
0.00
0.02
0.26
0.66
3.90
0.00
0.00
3.10
—
0.00
0.20
0.39
—
—
0.00
0.00
0.018
Rec3
20 × 5
1361
0.00
0.00
0.00
0.00
0.00
0.02
0.00
0.44
4.80
0.00
0.00
3.10
—
0.00
0.20
0.22
—
—
0.00
0.00
0.018
Rec5
20 × 5
1511
0.00
0.00
0.02
0.00
0.00
0.02
0.33
0.60
4.10
0.00
0.07
3.10
—
0.00
0.20
0.60
—
—
0.00
0.04
0.019
Rec7
20 × 10
2042
0.00
0.00
0.00
0.00
0.00
0.02
0.00
0.54
6.60
0.00
0.00
3.90
—
0.00
0.20
2.25
—
—
0.00
0.00
0.020
Rec9
20 × 10
2042
0.00
0.00
0.00
0.00
0.00
0.02
0.05
0.39
6.70
0.00
0.00
3.80
—
0.00
0.20
0.78
—
—
0.00
0.00
0.021
Rec11
20 × 10
1881
0.00
0.00
0.01
0.00
0.00
0.02
0.00
1.06
7.00
0.00
0.16
3.90
—
0.00
0.20
1.33
—
—
0.00
0.00
0.020
Rec13
20 × 15
2545
0.00
0.00
0.01
0.00
0.00
0.02
0.00
0.63
11.00
0.00
0.00
5.10
—
0.00
0.20
0.79
—
—
0.00
0.00
0.015
Rec15
20 × 15
2529
0.00
0.00
0.00
0.00
0.00
0.02
0.00
0.36
8.60
0.00
0.00
5.20
—
0.00
0.20
1.42
—
—
0.00
0.00
0.016
Rec17
20 × 15
2587
0.00
0.00
0.00
0.00
0.00
0.02
0.00
0.15
8.60
0.00
0.00
5.20
—
0.00
0.20
0.46
—
—
0.00
0.00
0.015
Rec19
30 × 10
2850
0.00
0.11
0.02
0.00
0.00
0.04
0.63
1.37
23.00
0.00
0.07
10.40
—
0.00
0.45
3.58
—
—
0.00
0.00
0.030
Rec21
30 × 10
2821
0.00
0.11
0.04
0.00
0.18
0.04
0.78
1.17
24.00
0.00
0.18
10.20
—
0.07
0.45
2.48
—
—
0.00
0.15
0.036
Rec23
30 × 10
2700
0.00
0.07
0.05
0.00
0.00
0.04
0.11
1.30
24.00
0.00
0.11
10.40
—
0.00
0.45
3.07
—
—
0.00
0.01
0.032
Rec25
30 × 15
3593
0.00
0.17
0.03
0.00
0.00
0.04
0.64
1.22
32.00
0.00
0.03
15.00
—
0.00
0.45
1.92
—
—
0.00
0.09
0.401
Rec27
30 × 15
3431
0.00
0.26
0.06
0.00
0.00
0.05
0.00
1.17
39.00
0.00
0.17
14.80
—
0.01
0.45
3.91
—
—
0.00
0.07
0.451
Rec29
30 × 15
3291
0.00
0.06
0.02
0.00
0.00
0.06
0.36
1.34
31.00
0.00
0.18
14.90
—
0.03
0.45
2.80
—
—
0.00
0.13
0.480
Rec31
50 × 10
4311
0.12
0.39
0.33
0.00
0.28
0.11
1.07
1.83
122.00
0.32
0.56
3.80
—
0.13
1.25
5.03
—
—
0.13
0.20
0.713
Rec33
50 × 10
4428
0.25
0.72
0.34
0.41
0.68
0.10
1.78
3.32
116.00
0.20
0.88
3.70
—
0.30
1.25
6.39
—
—
0.00
0.54
0.715
Rec35
50 × 10
4397
0.00
0.39
0.34
0.00
0.16
0.10
0.84
1.80
105.00
0.25
0.75
3.70
—
0.19
1.25
5.39
—
—
0.00
0.83
0.690
Rec37
75 × 20
8014
0.27
0.69
1.16
0.32
0.69
0.18
2.08
2.86
635.00
0.44
0.81
14.70
—
0.33
2.81
18.73
—
—
0.25
0.67
1.982
Rec39
75 × 20
8428
0.19
0.70
0.99
0.26
0.62
0.18
1.28
2.50
897.00
0.25
0.71
14.60
—
0.46
2.81
17.29
—
—
0.20
0.65
2.014
Rec41
75 × 20
8442
0.36
0.71
0.88
0.37
0.75
0.18
1.90
3.19
883.00
0.00
0.73
14.70
—
0.44
2.81
17.13
—
—
0.00
0.69
2.135
Average
0.06
0.21
0.21
0.06
0.16
0.06
0.58
1.33
142.49
0.07
0.26
7.97
—
0.09
0.79
4.57
—
—
0.03
0.20
0.47
APRT
0.0067
0.0078
4.3732
1.5113
0.0808
0.0202For BRD, the accuracy of results acquired from HMM-PFA is generally better than that from other algorithms. The advantages of some instances are more obvious, such as rec 31, rec 33, and rec 41. The average BRD value acquired from HMM-PFA is, respectively, fewer than that of DPSO, IIGA, HPSO, HDE, and GA by 0.03, 0.03, 0.55, 0.04, and 4.54. It can be concluded that the BRD performance of the proposed algorithm is superior to the comparison algorithms. For the average ARD values, the quality of solutions acquired from HMM-PFA is better than that of other algorithms, which illustrates that HMM-PFA can effectively solve NWFSP with good robustness.The statistical results on the last two lines in Table5 show that the average CPU time and ARPT of HMM-PFA are better than that of HPSO, HDE, and TIIIG, but slightly inferior to that of DPSO and IIGA algorithms. Comprehensive analysis shows that the dynamic self-adaptive variable work piece block (DSVWB) neighborhood search increases the time complexity in the HMM-PFA search process. However, from the BRD and ARD average, it can be concluded that HMM-PFA is significantly better than the other 6 algorithms.Figures12 and 13 are the Gantt charts for the optimal results obtained using HMM-FPA for Rec07 and Rec27.Figure 12
Gantt chart of the solution for Rec07.Figure 13
Gantt chart of the solution for Rec27.All in all, by applying the hormone modulation mechanism and the dynamic self-adaptive variable work piece block strategy, the HMM-PFA search quality can be enhanced, and the global search exploration and the local search exploitation can be well balanced. HMM-PFA is another effective method for solving no-wait flow shop scheduling problems with good quality.


### 5.2.4. Comparison for the Large-Scale Instances

Taillard’s benchmark instances are used to test HMM-PFA algorithm performance for solving the large-scale no-wait flow shop scheduling problem. The data files for these instances are downloaded from the websitehttp://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html. Taillard’s benchmark instances include 120 problems. According to the scale of the instances, they are divided into 12 groups, with 10 in each group. The proposed algorithm is compared with the ACO-SA [56] algorithm and IIGA [53] algorithm. The ACO-SA algorithm only performed the test of the first 110 instances (Ta001–Ta110) and did not test the 10 instances in 500 × 20 scale (Ta111–Ta120). Therefore, the statistical results for the 120 instances in 500×20 scale are contained in Table 6, marked with “∗”. From the statistical results in Tables 7 and 6, we can find that without the statistics for the instances in 500×20 scale, the BRD and ARD of the HMM-PFA algorithm are better than those of the ACO-SA algorithm. Besides, the HMM-PFA algorithm has less average CPU time and ARPT than the ACO-SA algorithm. Compared with the IIGA algorithm, we can find that the ARD of the HMM-PFA algorithm is better. The results from the above analysis indicate that the HMM-PFA algorithm is effective in solving the large-scale no-wait flow shop scheduling problem.Table 6
Comparison of results based on Taillard’s benchmark instances.
n×m
ACO-SA
IIGA
HMM-PFA
BRD
ARD
Tavg
BRD
ARD
Tavg
BRD
ARD
Tavg
20 × 5
0
0
0.28
—
0
—
0
0
0.0161
20 × 10
0
0.320
0.44
—
0.01
—
0
0
0.021
20 × 20
0
0.493
0.56
—
0.02
—
0
0
0.026
50 × 5
0.346
0.852
1.79
—
1.34
—
0.22
0.37
0.888
50 × 10
0.145
0.885
2.96
—
0.71
—
0.04
0.18
1.584
50 × 20
0.095
1.770
3.18
—
0.58
—
0.05
0.37
2.202
100 × 5
0.847
2.899
30.20
—
2.78
—
0.62
1.13
25.974
100 × 10
0.607
1.781
57.23
—
1.7
—
0.47
0.97
48.559
100 × 20
0.599
1.546
61.26
—
1.46
—
0.41
0.69
73.573
200 × 10
2.009
2.695
189.17
—
2.49
—
1.26
1.49
162.453
200 × 20
1.633
2.190
200.82
—
2.1
—
1.04
1.35
221.214
500 × 20
—
—
—
—
2.94
—
2.10
2.31
883.166
Average
0.571
1.403
49.808
—
1.199 (1.344)∗
—
0.374 (0.518)∗
0.595 (0.738)∗
48.774 (118.306)∗
∗ is the statistical results for the 120 instances in 500 × 20 scale.Table 7
The HMM-PFA statistical result to solve 120 Taillard’s benchmark instances.
n×m
Instance
Opt
BRD
ARD
Tavg
n×m
Instance
Opt
BRD
ARD
Tavg
20 × 5
Ta001
1486
0
0
0.016
100 × 5
Ta061
6361
0.57
1.07
25.557
Ta002
1528
0
0
0.017
Ta062
6212
0.90
1.13
26.021
Ta003
1460
0
0
0.016
Ta063
6104
0.48
0.87
25.998
Ta004
1588
0
0
0.016
Ta064
5999
0.93
1.50
26.59
Ta005
1449
0
0
0.017
Ta065
6179
0.44
0.82
25.709
Ta006
1481
0
0
0.016
Ta066
6056
0.18
0.76
26.054
Ta007
1483
0
0
0.016
Ta067
6221
0.37
1.21
26.121
Ta008
1482
0
0
0.016
Ta068
6109
1.34
1.99
25.993
Ta009
1469
0
0
0.016
Ta069
6355
0.90
1.34
25.578
Ta010
1377
0
0
0.015
Ta070
6365
0.06
0.61
26.121
20 × 10
Ta011
2044
0
0
0.021
100 × 10
Ta071
8055
0.62
0.81
47.664
Ta012
2166
0
0
0.02
Ta072
7853
0.45
1.88
50.001
Ta013
1940
0
0
0.02
Ta073
8016
0.41
0.95
49.654
Ta014
1811
0
0
0.021
Ta074
8328
0.41
0.75
49.721
Ta015
1933
0
0
0.022
Ta075
7936
0.38
0.93
48.332
Ta016
1892
0
0
0.021
Ta076
7773
0.68
0.86
49.024
Ta017
1963
0
0
0.021
Ta077
7846
0.43
0.75
47.238
Ta018
2057
0
0
0.021
Ta078
7880
0.56
1.15
47.967
Ta019
1973
0
0
0.022
Ta079
8131
0.30
0.85
48.054
Ta020
2051
0
0
0.021
Ta080
8092
0.46
0.74
47.937
20 × 20
Ta021
2973
0
0
0.025
100 × 20
Ta081
10,675
0.09
0.21
75.345
Ta022
2852
0
0
0.026
Ta082
10,562
0.94
1.32
72.49
Ta023
3013
0
0
0.026
Ta083
10,587
0.73
0.89
70.376
Ta024
3001
0
0
0.026
Ta084
10,588
0.30
0.63
73.298
Ta025
3003
0
0
0.025
Ta085
10,506
0.10
0.42
71.439
Ta026
2998
0
0
0.025
Ta086
10,623
0.57
0.76
76.296
Ta027
3052
0
0
0.027
Ta087
10,793
0.29
0.53
74.387
Ta028
2839
0
0
0.027
Ta088
10,801
0.45
0.91
72.363
Ta029
3009
0
0
0.027
Ta089
10,703
0.14
0.53
75.832
Ta030
2979
0
0
0.026
Ta090
10,747
0.47
0.73
73.901
50 × 5
Ta031
3160
0.28
0.36
0.892
200 × 10
Ta091
15,225
1.22
1.48
159.072
Ta032
3432
0.26
0.53
0.902
Ta092
14,990
0.75
0.95
165.921
Ta033
3210
0.09
0.27
0.912
Ta093
15,257
1.07
1.40
162.209
Ta034
3338
0.30
0.50
0.89
Ta094
15,103
0.70
0.89
167.011
Ta035
3356
0.60
0.72
0.89
Ta095
15,088
1.47
1.79
158.001
Ta036
3346
0.00
0.04
0.914
Ta096
14,976
1.65
1.85
159.928
Ta037
3231
0.09
0.29
0.911
Ta097
15,277
1.07
1.23
163.785
Ta038
3235
0.12
0.17
0.799
Ta098
15,133
1.37
1.62
164.902
Ta039
3070
0.33
0.52
0.85
Ta099
14,985
1.77
1.98
158.397
Ta040
3317
0.15
0.26
0.922
Ta100
15,213
1.57
1.75
165.299
50 × 10
Ta041
4274
0.00
0.04
1.568
200 × 20
Ta101
19,531
0.65
0.77
220.632
Ta042
4177
0.05
0.21
1.57
Ta102
19,942
1.44
1.79
217.997
Ta043
4099
0.00
0.09
1.587
Ta103
19,759
1.16
1.31
218.318
Ta044
4399
0.05
0.14
1.563
Ta104
19,759
1.22
1.66
225.638
Ta045
4322
0.05
0.37
1.569
Ta105
19,697
0.90
1.05
237.689
Ta046
4289
0.02
0.18
1.601
Ta106
19,826
0.94
1.31
209.396
Ta047
4420
0.00
0.13
1.602
Ta107
19,946
0.87
1.63
217.332
Ta048
4318
0.07
0.11
1.59
Ta108
19,872
1.37
1.62
219.744
Ta049
4155
0.00
0.15
1.584
Ta109
19,784
1.08
1.20
216.655
Ta050
4283
0.16
0.37
1.601
Ta110
19,768
0.80
1.23
228.738
50 × 20
Ta051
6129
0.00
0.11
2.195
500 × 20
Ta111
46,121
1.96
2.20
873.905
Ta052
5725
0.00
0.18
2.221
Ta112
46,627
1.65
1.69
878.009
Ta053
5862
0.00
0.15
2.199
Ta113
46,013
2.12
2.54
890.675
Ta054
5788
0.24
0.42
2.198
Ta114
46,396
1.52
1.65
897.432
Ta055
5886
0.00
1.77
2.205
Ta115
46,251
2.07
2.33
870.002
Ta056
5863
0.12
0.20
2.208
Ta116
46,490
2.17
2.45
896.329
Ta057
5962
0.12
0.25
2.197
Ta117
46,043
1.96
2.15
869.428
Ta058
5926
0.02
0.20
2.199
Ta118
46,368
1.63
1.80
877.917
Ta059
5876
0.00
0.22
2.195
Ta119
46,240
3.76
3.92
879.013
Ta060
5957
0.03
0.22
2.199
Ta120
46,292
2.18
2.36
898.953


## 5.2.1. Discussion on the Settings of the Size of Work Piece Blocks

In order to discuss the influence of the work piece block size in the neighborhood search of the proposed algorithm, seven Rec instances (Rec01, Rec07, Rec13, Rec19, Rec25, Rec31, and Rec37) and eight Car instances (Car1~Car8) are used to test. For the Car instances, the size of work piece blocksstep is, respectively, set as 1, 2, 3, 4, 6, and the dynamic self-adaptive variable work piece blocks (DSVWB). The step is, respectively, set as 1, 3, 5, 8, 10, and DSVWB for the seven Rec instances. Here, the values of C∗ for Car instances and Rec instances are the optimal solution found so far.It is clear from Tables2 and 3 that the proposed algorithm with DSVWB is the winner, since the ARD and WRD obtained by the DSVWB are better than or equal to those obtained by other step. The larger the work piece block size is, the better the algorithm search performance is. However, when the size of the work piece blocks surpasses a certain value, the larger the size is, the worse the search performance of the algorithm is.Table 2
Performance comparison of the tested work piece blocks with different size for Cars.
Problem
n×m
C∗
step = 1
step = 2
step = 3
step = 4
step = 6
DACWB
BRD
ARD
WRD
BRD
ARD
WRD
BRD
ARD
WRD
BRD
ARD
WRD
BRD
ARD
WRD
BRD
ARD
WRD
Car1
11 × 5
8142
0.00
0.15
0.26
0.00
0.03
0.28
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
Car2
13 × 4
8242
0.00
0.08
0.18
0.00
0.03
0.16
0.00
0.02
0.18
0.00
0.04
0.18
0.00
0.00
0.00
0.00
0.06
0.15
Car3
12 × 5
8866
0.00
0.03
0.07
0.00
0.03
0.09
0.00
0.03
0.08
0.00
0.01
0.07
0.00
0.00
0.00
0.00
0.05
0.08
Car4
14 × 4
9195
0.00
0.45
0.80
0.00
0.29
0.69
0.00
0.22
0.71
0.00
0.12
0.71
0.00
0.01
0.05
0.00
0.02
0.06
Car5
10 × 6
9159
0.00
0.40
1.87
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.45
2.05
0.00
0.00
0.00
Car6
8 × 9
9690
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
Car7
7 × 7
7705
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
Car8
8 × 8
9372
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.02
0.16
0.00
0.00
0.00
Average
0
0.139
0.398
0
0.048
0.153
0
0.034
0.121
0
0.0212
0.12
0
0.06
0.283
0
0.016
0.0363
C∗ is the best solution found.Table 3
Performance comparison of the tested work piece blocks with different size for Recs.
Problem
n×m
C∗
step = 1
step = 3
step = 5
step = 8
step = 10
DACWB
BRD
ARD
WRD
BRD
ARD
WRD
BRD
ARD
WRD
BRD
ARD
WRD
BRD
ARD
WRD
BRD
ARD
WRD
Rec01
20 × 5
1526
0.00
0.15
0.41
0.00
0.04
0.25
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
Rec07
20 × 10
2042
0.00
1.07
2.27
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
Rec13
20 × 15
2545
0.00
0.45
1.98
0.00
0.18
0.33
0.00
0.05
0.25
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
Rec19
30 × 10
2850
0.00
0.95
1.85
0.00
0.45
1.20
0.00
0.58
1.14
0.00
0.30
1.17
0.00
0.23
0.50
0.00
0.00
0.00
Rec25
30 × 15
3593
0.13
0.78
1.65
0.00
0.41
1.22
0.00
0.32
0.91
0.00
0.21
0.85
0.00
0.40
0.88
0.00
0.09
0.65
Rec31
50 × 10
4311
1.41
2.71
3.29
0.15
1.07
2.11
0.14
0.75
1.41
0.32
0.49
1.04
0.31
0.52
1.03
0.13
0.20
0.49
Rec37
75 × 20
8014
3.50
4.17
4.91
1.01
2.37
3.58
0.97
1.60
2.05
0.95
1.55
1.99
1.02
1.70
2.23
0.25
0.67
1.40
Average
0.720
1.469
2.337
0.166
0.646
1.241
0.159
0.471
0.823
0.181
0.364
0.721
0.190
0.407
0.663
0.0543
0.137
0.363
C∗ is the best solution found.As for the causes, the neighborhood search in this paper can be essentially regarded as a disturbance operation that can easily remove the current solution to other neighboring areas with partial characteristics of the current solution.The size of disturbance step exerts greater effects on algorithm performance. An excessively long disturbance step can easily lead to loss of great characteristics in the current solution, similar to the random emergence process. If the disturbance step is excessively short and the movement range of the current solution is excessively small, it is easier to fall into the local optimum position.Figures1 and 2 are the line charts of the average relative error (ARE) for solving Car instances and Rec instances. It can be indicated from Figures 1 and 2 that ARE solved by DSVWB is equivalent to or better than the results solved by other fixed steps. The size of oversized or undersize work piece blocks will decrease the local search ability of the neighborhood search. Apparently, taking the time complexity of the algorithm, it is reasonable to adopt the dynamic self-adaptive variable work piece block size, which not only balances the local and global search ability of the algorithm but also reduces the algorithm calculation time.Figure 1
The ARD line chart for Car set problems with differentstep.Figure 2
The ARD line chart for Rec set problems with differentstep.


## 5.2.2. Comparison of PSO, CS, FPA, and HMM-FPA

Four algorithms were selected as contrast algorithms in the simulation experiment to evaluate the proposed algorithm’s performance, that is, particle swarm optimization algorithm (PSO) [15], cuckoo search algorithm (CS) [50], and flower pollination algorithm (FPA) [29], respectively. Eight Car instances (Car1~Car8) were used in this test.The same coding method is applied to the four algorithms as shown in Section4.1. The algorithm parameter settings are shown below:The flower pollination algorithm (FPA) has the size of the populationnsize=50, selection probability of pollination method p=0.8, and the largest iterations itermax=5000.The particle swarm optimization algorithm (PSO) has the population sizensize=50, the iterations itermax=5000, linear inertia wmax=0.9 and wmin=0.4, learning factor C1=C2=1.4692, and search range of particles xmax=4 and xmin=−4.The cuckoo search algorithm (CS) has the population sizensize=50, pa=0.25, λ=1.5, and the largest iterations itermax=5000.The flower pollination algorithm based on hormone modulation mechanism (HMM-FPA) has the population sizensize=50, pollination method selection probability p=0.8, the largest work piece blocks max_step=4, and the largest iterations itermax=5000.The statistical results of 20 independent runs for the four algorithms are listed in Table4, including the best relative deviation (BRD), the average relative deviation (ARD), and the average CPU time (Tavg) for finding the optimal solutions in the iterations. Here, the values of C∗ for Car1~Car8 are the optimal solution found so far. In order to be able to perform a fair comparison among swarm intelligent algorithms, we use ARPT as a measure of the computational effort. Results in terms of average CPU time and the ARPT are shown in Table 4 (the last two rows represent the average CPU time and the ARPT, resp.).Table 4
The comparative statistical results between FPA, PSO, CS, and HMM-FPA.
Problem
n×m
C∗
PSO
CS
FPA
HMM-FPA
BRD
ARD
Tavg
BRD
ARD
Tavg
BRD
ARD
Tavg
BRD
ARD
Tavg
Car1
11 × 5
8142
0.00
0.00
0.01
0.00
0.00
0.01
0.00
0.00
0.008
0.00
0.00
0.01
Car2
13 × 4
8242
0.60
1.24
0.01
0.18
2.75
0.01
0.64
1.85
0.008
0.00
0.06
0.01
Car3
12 × 5
8866
0.73
0.85
0.01
0.00
0.89
0.01
0.70
2.61
0.008
0.00
0.05
0.01
Car4
14 × 4
9195
3.54
4.46
0.02
0.65
3.79
0.015
3.49
6.45
0.010
0.00
0.02
0.011
Car5
10 × 6
9159
2.35
3.78
0.01
0.54
2.20
0.01
0.00
3.96
0.009
0.00
0.00
0.01
Car6
8 × 9
9690
0.00
0.00
0.004
0.00
0.00
0.008
0.00
0.00
0.005
0.00
0.00
0.006
Car7
7 × 7
7705
0.00
0.50
0.004
0.00
0.15
0.008
0.00
3.60
0.004
0.00
0.00
0.005
Car8
8 × 8
9372
0.00
0.15
0.004
0.00
0.20
0.008
0.00
0.19
0.005
0.00
0.00
0.006
Average
0.90
1.37
0.01
0.17
1.25
0.01
0.60
2.33
0.01
0.00
0.02
0.01
APRT
0.9707
1.1952
0.8331
1.0011
C∗ is the best solution.It can be indicated from Table4 that PSO can only acquire the optimal solution in four instances including Car 1, Car 6, Car 7, and Car 8. The optimal solutions to test instances of Car 2, Car 4, and Car 5 cannot be acquired by basic cuckoo algorithm. The basic FPA contributes nothing to test instances of Car 2, Car 3, and Car 4. The proposed algorithm can acquire all the optimal solutions to Car instances and is better in BRD and ARD than the other three swarm optimization algorithms.The average CPU time and APRT of the HMM-FPA algorithm is less than that of the CS algorithm, but more than that of the PSO and the standard FPA algorithm. However, its solution accuracy is apparently better than that of the other three swarm intelligent algorithms. This demonstrates that the global searching ability of HMM-FPA is effective and HMM-FPA is suitable for solving NWFSP.In the basic particle swarm optimization algorithm, the particle position update is determined by the particle at the current optimal position and the historical optimum position that the particle has experienced, neglecting the influence of the particles at the common nonoptimal position (the particles may be near the global optimum position). The algorithm is easily trapped into the local optimum position. In selecting the host bird nest position, a kind of random search method with levy distribution is applied in the cuckoo algorithm. It has been proven that the cuckoo algorithm is better than the basic particle swarm optimization algorithm [50] in searching for the global optimum solution. Thus, in solutions to NWFSP, the cuckoo algorithm is better than the basic particle swarm optimization algorithm. However, similarly, the two algorithms ignore the influence of other neighboring particle positions on themselves.In the HMM-FPA algorithm mentioned in this paper, when a single individual flower conducts cross-pollination with the help of animal vectors like bees and butterflies, the influence of neighboring flowers on itself and the irritability of the individual towards the flower’s status at other positions are both considered. Furthermore, certain adjustment is appropriately conducted on its position. For the proposed algorithm, the flower positions are updated by (10), and the neighboring individual flower factors are sufficiently considered. When fi<favg, the flower performance of flower i is better (in a better position), leading to a smaller adjustment range in the flower position. Conversely, the performance of flower i is worse (in a worse position), leading to a larger adjustment range in the flower position.The HMM-FPA sufficiently considers the flower information at the optimal position and neighboring flower positions, which combines the global expansion ability and local development ability, so the solution performance of the proposed algorithm is apparently better than that of other swarm intelligent algorithms.Figure3 is the statistical result from the makespan for PSO, CS, FPA, and HMM-FPA. It is shown that the makespan of the HMM-FPA is the least except Car1 and Car6 (the four algorithms can search the global optimal theoretical value).Figure 3
The makespan of the statistical results for the different algorithms.Figures4–11 are the statistical results from box diagrams for PSO, CS, FPA, and HMM-FPA. It can be seen from Figures 4–11 that the stability of HMM-FPA is better than the compared algorithm for solving Car instances, which illustrates the good robustness.Figure 4
ANOVA tests of Car1.Figure 5
ANOVA tests of Car2.Figure 6
ANOVA tests of Car3.Figure 7
ANOVA tests of Car4.Figure 8
ANOVA tests of Car5.Figure 9
ANOVA tests of Car6.Figure 10
ANOVA tests of Car7.Figure 11
ANOVA tests of Car8.


## 5.2.3. Comparison of HMM-FPA and Existing Intelligent Algorithm

In order to further verify the algorithm performance, the proposed algorithm is compared with other intelligent algorithms. Comparisons are carried out with sex typical methods from the literatures, including the discrete particle swarm optimization algorithm (DPSO) [51], improved iterated greedy algorithm with a Tabu-based reconstruction strategy (TMIIG) [52], improved iterated greedy algorithm (IIGA) [53], DE-based approach (HDE) [54], effective hybrid particle swarm optimization (HPSO) [21], and GA [55]. Results of DPSO, TMIIG, IIGA, HDE, HPSO, and GA come from the corresponding literatures. The 21 Rec problems (Rec01~Rec41) are used as test instances. Comparison results are shown in Table 5. Table 5 shows that IMIIG only conducts statistics on the ARD perspective without statistics on BRD and Tavg. GA only conducts statistics on BRD.Table 5
The comparative statistical results between HMM-PFA and DPSO, IIGA, HPSO, HDE, TMIIG, and GA.
Problem
n×m
Best
DPSO
IIGA
HPSO
HDE
TMIIG
GA
HMM-PFA
BRD
ARD
Tavg
BRD
ARD
Tavg
BRD
ARD
Tavg
BRD
ARD
Tavg
BRD
ARD
Tavg
BRD
ARD
Tavg
BRD
ARD
Tavg
Rec1
20 × 5
1526
0.00
0.00
0.01
0.00
0.00
0.02
0.26
0.66
3.90
0.00
0.00
3.10
—
0.00
0.20
0.39
—
—
0.00
0.00
0.018
Rec3
20 × 5
1361
0.00
0.00
0.00
0.00
0.00
0.02
0.00
0.44
4.80
0.00
0.00
3.10
—
0.00
0.20
0.22
—
—
0.00
0.00
0.018
Rec5
20 × 5
1511
0.00
0.00
0.02
0.00
0.00
0.02
0.33
0.60
4.10
0.00
0.07
3.10
—
0.00
0.20
0.60
—
—
0.00
0.04
0.019
Rec7
20 × 10
2042
0.00
0.00
0.00
0.00
0.00
0.02
0.00
0.54
6.60
0.00
0.00
3.90
—
0.00
0.20
2.25
—
—
0.00
0.00
0.020
Rec9
20 × 10
2042
0.00
0.00
0.00
0.00
0.00
0.02
0.05
0.39
6.70
0.00
0.00
3.80
—
0.00
0.20
0.78
—
—
0.00
0.00
0.021
Rec11
20 × 10
1881
0.00
0.00
0.01
0.00
0.00
0.02
0.00
1.06
7.00
0.00
0.16
3.90
—
0.00
0.20
1.33
—
—
0.00
0.00
0.020
Rec13
20 × 15
2545
0.00
0.00
0.01
0.00
0.00
0.02
0.00
0.63
11.00
0.00
0.00
5.10
—
0.00
0.20
0.79
—
—
0.00
0.00
0.015
Rec15
20 × 15
2529
0.00
0.00
0.00
0.00
0.00
0.02
0.00
0.36
8.60
0.00
0.00
5.20
—
0.00
0.20
1.42
—
—
0.00
0.00
0.016
Rec17
20 × 15
2587
0.00
0.00
0.00
0.00
0.00
0.02
0.00
0.15
8.60
0.00
0.00
5.20
—
0.00
0.20
0.46
—
—
0.00
0.00
0.015
Rec19
30 × 10
2850
0.00
0.11
0.02
0.00
0.00
0.04
0.63
1.37
23.00
0.00
0.07
10.40
—
0.00
0.45
3.58
—
—
0.00
0.00
0.030
Rec21
30 × 10
2821
0.00
0.11
0.04
0.00
0.18
0.04
0.78
1.17
24.00
0.00
0.18
10.20
—
0.07
0.45
2.48
—
—
0.00
0.15
0.036
Rec23
30 × 10
2700
0.00
0.07
0.05
0.00
0.00
0.04
0.11
1.30
24.00
0.00
0.11
10.40
—
0.00
0.45
3.07
—
—
0.00
0.01
0.032
Rec25
30 × 15
3593
0.00
0.17
0.03
0.00
0.00
0.04
0.64
1.22
32.00
0.00
0.03
15.00
—
0.00
0.45
1.92
—
—
0.00
0.09
0.401
Rec27
30 × 15
3431
0.00
0.26
0.06
0.00
0.00
0.05
0.00
1.17
39.00
0.00
0.17
14.80
—
0.01
0.45
3.91
—
—
0.00
0.07
0.451
Rec29
30 × 15
3291
0.00
0.06
0.02
0.00
0.00
0.06
0.36
1.34
31.00
0.00
0.18
14.90
—
0.03
0.45
2.80
—
—
0.00
0.13
0.480
Rec31
50 × 10
4311
0.12
0.39
0.33
0.00
0.28
0.11
1.07
1.83
122.00
0.32
0.56
3.80
—
0.13
1.25
5.03
—
—
0.13
0.20
0.713
Rec33
50 × 10
4428
0.25
0.72
0.34
0.41
0.68
0.10
1.78
3.32
116.00
0.20
0.88
3.70
—
0.30
1.25
6.39
—
—
0.00
0.54
0.715
Rec35
50 × 10
4397
0.00
0.39
0.34
0.00
0.16
0.10
0.84
1.80
105.00
0.25
0.75
3.70
—
0.19
1.25
5.39
—
—
0.00
0.83
0.690
Rec37
75 × 20
8014
0.27
0.69
1.16
0.32
0.69
0.18
2.08
2.86
635.00
0.44
0.81
14.70
—
0.33
2.81
18.73
—
—
0.25
0.67
1.982
Rec39
75 × 20
8428
0.19
0.70
0.99
0.26
0.62
0.18
1.28
2.50
897.00
0.25
0.71
14.60
—
0.46
2.81
17.29
—
—
0.20
0.65
2.014
Rec41
75 × 20
8442
0.36
0.71
0.88
0.37
0.75
0.18
1.90
3.19
883.00
0.00
0.73
14.70
—
0.44
2.81
17.13
—
—
0.00
0.69
2.135
Average
0.06
0.21
0.21
0.06
0.16
0.06
0.58
1.33
142.49
0.07
0.26
7.97
—
0.09
0.79
4.57
—
—
0.03
0.20
0.47
APRT
0.0067
0.0078
4.3732
1.5113
0.0808
0.0202For BRD, the accuracy of results acquired from HMM-PFA is generally better than that from other algorithms. The advantages of some instances are more obvious, such as rec 31, rec 33, and rec 41. The average BRD value acquired from HMM-PFA is, respectively, fewer than that of DPSO, IIGA, HPSO, HDE, and GA by 0.03, 0.03, 0.55, 0.04, and 4.54. It can be concluded that the BRD performance of the proposed algorithm is superior to the comparison algorithms. For the average ARD values, the quality of solutions acquired from HMM-PFA is better than that of other algorithms, which illustrates that HMM-PFA can effectively solve NWFSP with good robustness.The statistical results on the last two lines in Table5 show that the average CPU time and ARPT of HMM-PFA are better than that of HPSO, HDE, and TIIIG, but slightly inferior to that of DPSO and IIGA algorithms. Comprehensive analysis shows that the dynamic self-adaptive variable work piece block (DSVWB) neighborhood search increases the time complexity in the HMM-PFA search process. However, from the BRD and ARD average, it can be concluded that HMM-PFA is significantly better than the other 6 algorithms.Figures12 and 13 are the Gantt charts for the optimal results obtained using HMM-FPA for Rec07 and Rec27.Figure 12
Gantt chart of the solution for Rec07.Figure 13
Gantt chart of the solution for Rec27.All in all, by applying the hormone modulation mechanism and the dynamic self-adaptive variable work piece block strategy, the HMM-PFA search quality can be enhanced, and the global search exploration and the local search exploitation can be well balanced. HMM-PFA is another effective method for solving no-wait flow shop scheduling problems with good quality.


## 5.2.4. Comparison for the Large-Scale Instances

Taillard’s benchmark instances are used to test HMM-PFA algorithm performance for solving the large-scale no-wait flow shop scheduling problem. The data files for these instances are downloaded from the websitehttp://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html. Taillard’s benchmark instances include 120 problems. According to the scale of the instances, they are divided into 12 groups, with 10 in each group. The proposed algorithm is compared with the ACO-SA [56] algorithm and IIGA [53] algorithm. The ACO-SA algorithm only performed the test of the first 110 instances (Ta001–Ta110) and did not test the 10 instances in 500 × 20 scale (Ta111–Ta120). Therefore, the statistical results for the 120 instances in 500×20 scale are contained in Table 6, marked with “∗”. From the statistical results in Tables 7 and 6, we can find that without the statistics for the instances in 500×20 scale, the BRD and ARD of the HMM-PFA algorithm are better than those of the ACO-SA algorithm. Besides, the HMM-PFA algorithm has less average CPU time and ARPT than the ACO-SA algorithm. Compared with the IIGA algorithm, we can find that the ARD of the HMM-PFA algorithm is better. The results from the above analysis indicate that the HMM-PFA algorithm is effective in solving the large-scale no-wait flow shop scheduling problem.Table 6
Comparison of results based on Taillard’s benchmark instances.
n×m
ACO-SA
IIGA
HMM-PFA
BRD
ARD
Tavg
BRD
ARD
Tavg
BRD
ARD
Tavg
20 × 5
0
0
0.28
—
0
—
0
0
0.0161
20 × 10
0
0.320
0.44
—
0.01
—
0
0
0.021
20 × 20
0
0.493
0.56
—
0.02
—
0
0
0.026
50 × 5
0.346
0.852
1.79
—
1.34
—
0.22
0.37
0.888
50 × 10
0.145
0.885
2.96
—
0.71
—
0.04
0.18
1.584
50 × 20
0.095
1.770
3.18
—
0.58
—
0.05
0.37
2.202
100 × 5
0.847
2.899
30.20
—
2.78
—
0.62
1.13
25.974
100 × 10
0.607
1.781
57.23
—
1.7
—
0.47
0.97
48.559
100 × 20
0.599
1.546
61.26
—
1.46
—
0.41
0.69
73.573
200 × 10
2.009
2.695
189.17
—
2.49
—
1.26
1.49
162.453
200 × 20
1.633
2.190
200.82
—
2.1
—
1.04
1.35
221.214
500 × 20
—
—
—
—
2.94
—
2.10
2.31
883.166
Average
0.571
1.403
49.808
—
1.199 (1.344)∗
—
0.374 (0.518)∗
0.595 (0.738)∗
48.774 (118.306)∗
∗ is the statistical results for the 120 instances in 500 × 20 scale.Table 7
The HMM-PFA statistical result to solve 120 Taillard’s benchmark instances.
n×m
Instance
Opt
BRD
ARD
Tavg
n×m
Instance
Opt
BRD
ARD
Tavg
20 × 5
Ta001
1486
0
0
0.016
100 × 5
Ta061
6361
0.57
1.07
25.557
Ta002
1528
0
0
0.017
Ta062
6212
0.90
1.13
26.021
Ta003
1460
0
0
0.016
Ta063
6104
0.48
0.87
25.998
Ta004
1588
0
0
0.016
Ta064
5999
0.93
1.50
26.59
Ta005
1449
0
0
0.017
Ta065
6179
0.44
0.82
25.709
Ta006
1481
0
0
0.016
Ta066
6056
0.18
0.76
26.054
Ta007
1483
0
0
0.016
Ta067
6221
0.37
1.21
26.121
Ta008
1482
0
0
0.016
Ta068
6109
1.34
1.99
25.993
Ta009
1469
0
0
0.016
Ta069
6355
0.90
1.34
25.578
Ta010
1377
0
0
0.015
Ta070
6365
0.06
0.61
26.121
20 × 10
Ta011
2044
0
0
0.021
100 × 10
Ta071
8055
0.62
0.81
47.664
Ta012
2166
0
0
0.02
Ta072
7853
0.45
1.88
50.001
Ta013
1940
0
0
0.02
Ta073
8016
0.41
0.95
49.654
Ta014
1811
0
0
0.021
Ta074
8328
0.41
0.75
49.721
Ta015
1933
0
0
0.022
Ta075
7936
0.38
0.93
48.332
Ta016
1892
0
0
0.021
Ta076
7773
0.68
0.86
49.024
Ta017
1963
0
0
0.021
Ta077
7846
0.43
0.75
47.238
Ta018
2057
0
0
0.021
Ta078
7880
0.56
1.15
47.967
Ta019
1973
0
0
0.022
Ta079
8131
0.30
0.85
48.054
Ta020
2051
0
0
0.021
Ta080
8092
0.46
0.74
47.937
20 × 20
Ta021
2973
0
0
0.025
100 × 20
Ta081
10,675
0.09
0.21
75.345
Ta022
2852
0
0
0.026
Ta082
10,562
0.94
1.32
72.49
Ta023
3013
0
0
0.026
Ta083
10,587
0.73
0.89
70.376
Ta024
3001
0
0
0.026
Ta084
10,588
0.30
0.63
73.298
Ta025
3003
0
0
0.025
Ta085
10,506
0.10
0.42
71.439
Ta026
2998
0
0
0.025
Ta086
10,623
0.57
0.76
76.296
Ta027
3052
0
0
0.027
Ta087
10,793
0.29
0.53
74.387
Ta028
2839
0
0
0.027
Ta088
10,801
0.45
0.91
72.363
Ta029
3009
0
0
0.027
Ta089
10,703
0.14
0.53
75.832
Ta030
2979
0
0
0.026
Ta090
10,747
0.47
0.73
73.901
50 × 5
Ta031
3160
0.28
0.36
0.892
200 × 10
Ta091
15,225
1.22
1.48
159.072
Ta032
3432
0.26
0.53
0.902
Ta092
14,990
0.75
0.95
165.921
Ta033
3210
0.09
0.27
0.912
Ta093
15,257
1.07
1.40
162.209
Ta034
3338
0.30
0.50
0.89
Ta094
15,103
0.70
0.89
167.011
Ta035
3356
0.60
0.72
0.89
Ta095
15,088
1.47
1.79
158.001
Ta036
3346
0.00
0.04
0.914
Ta096
14,976
1.65
1.85
159.928
Ta037
3231
0.09
0.29
0.911
Ta097
15,277
1.07
1.23
163.785
Ta038
3235
0.12
0.17
0.799
Ta098
15,133
1.37
1.62
164.902
Ta039
3070
0.33
0.52
0.85
Ta099
14,985
1.77
1.98
158.397
Ta040
3317
0.15
0.26
0.922
Ta100
15,213
1.57
1.75
165.299
50 × 10
Ta041
4274
0.00
0.04
1.568
200 × 20
Ta101
19,531
0.65
0.77
220.632
Ta042
4177
0.05
0.21
1.57
Ta102
19,942
1.44
1.79
217.997
Ta043
4099
0.00
0.09
1.587
Ta103
19,759
1.16
1.31
218.318
Ta044
4399
0.05
0.14
1.563
Ta104
19,759
1.22
1.66
225.638
Ta045
4322
0.05
0.37
1.569
Ta105
19,697
0.90
1.05
237.689
Ta046
4289
0.02
0.18
1.601
Ta106
19,826
0.94
1.31
209.396
Ta047
4420
0.00
0.13
1.602
Ta107
19,946
0.87
1.63
217.332
Ta048
4318
0.07
0.11
1.59
Ta108
19,872
1.37
1.62
219.744
Ta049
4155
0.00
0.15
1.584
Ta109
19,784
1.08
1.20
216.655
Ta050
4283
0.16
0.37
1.601
Ta110
19,768
0.80
1.23
228.738
50 × 20
Ta051
6129
0.00
0.11
2.195
500 × 20
Ta111
46,121
1.96
2.20
873.905
Ta052
5725
0.00
0.18
2.221
Ta112
46,627
1.65
1.69
878.009
Ta053
5862
0.00
0.15
2.199
Ta113
46,013
2.12
2.54
890.675
Ta054
5788
0.24
0.42
2.198
Ta114
46,396
1.52
1.65
897.432
Ta055
5886
0.00
1.77
2.205
Ta115
46,251
2.07
2.33
870.002
Ta056
5863
0.12
0.20
2.208
Ta116
46,490
2.17
2.45
896.329
Ta057
5962
0.12
0.25
2.197
Ta117
46,043
1.96
2.15
869.428
Ta058
5926
0.02
0.20
2.199
Ta118
46,368
1.63
1.80
877.917
Ta059
5876
0.00
0.22
2.195
Ta119
46,240
3.76
3.92
879.013
Ta060
5957
0.03
0.22
2.199
Ta120
46,292
2.18
2.36
898.953


## 6. Conclusion

A flower pollination algorithm based on the hormone modulation mechanism is designed for NFWSP. The proposed method uses a variable neighborhood search strategy based on dynamic self-adaptive variable work piece in the local search. The application of improvement on cross-pollination operators in flower pollination algorithm by hormone modulation mechanism is introduced, which considers information sharing among the flowers. The benchmark instances for NWFSP are used to conduct test experiments on the targeted algorithm. Compared with other swarm optimization algorithms, the solution quality of the proposed algorithm in this paper is apparently better than the other algorithms, which sufficiently testify the algorithm effectiveness.Future extensions will be conducted in the following directions. First, the proposed algorithm will be used to solve other complex flow shop scheduling problems (the limited buffer permutation flow shop scheduling problem, the blocking flow shop problem, and the no-idle flow shop scheduling problem). Secondly, we can combine the hormone modulation mechanism with other intelligent algorithms for solving job (or flexible) shop scheduling problems. Furthermore, we can also use the HMM-PFA to solve optimization problems based on sequencing (e.g., vehicle routing problem and traveling salesman problem).



---

*Source: 1973604-2018-08-06.xml*