An effective co-evolutionary quantum genetic algorithm for the no-wait flow shop scheduling problem

Abstract

This article proposes a competitive co-evolutionary quantum genetic algorithm for the no-wait flow shop scheduling problem with the criterion to minimize makespan, which is a renowned NP-hard combinatorial optimization problem. An innovative coding and decoding mechanism is proposed. The mechanism uses square matrix to represent the quantum individual and adapts the quantum rotation gate to update the quantum individual. In the algorithm framework, the store-with-diversity is proposed to maintain the diversity of the population. Moreover, a competitive co-evolution strategy is introduced to enhance the evolutionary pressure and accelerate the convergence. The store-with-diversity and competitive co-evolution are designed to keep a balance between exploration and exploitation. Simulations based on a benchmark set and comparisons with several existing algorithms demonstrate the effectiveness and robustness of the proposed algorithm.

Introduction

The flow shop scheduling problem (FSP) is a renowned complex combinatorial optimization problem with strong practical background and has gained growing research in the past decades. However, in real industrial environment, the no-wait constraint exists when the production requires that each job must be processed from the start to completion with no waiting between or on consecutive machines. ¹ The no-wait flow shop scheduling problem (NWFSP) has been found in a host of industrial applications.^2,3

With respect to its computational complexity, the NWFSP has been proved to be NP-hard.^4,5 On account of its complexity and significance in both theory and application, the NWFSP has aroused much concern of researchers. The relatively earlier work was the heuristics developed by Bonney and Gundry ⁶ and King and Spachis. ⁷ In 1990s, Rajendran ⁸ and Gangadharan and Rajendran ⁹ proposed heuristics which outperformed the previous ones. As for metaheuristic method, Aldowaisan and Allahverdi ¹⁰ presented a genetic algorithm (GA) to minimize makespan, and Schuster and Framinan ¹¹ proposed two metaheuristics, genetic algorithm hybridized with simulated annealing (GASA) and variable neighborhood search (VNS), for the same problem. Then a descending search (DS) method and a tabu search (TS) algorithm were also employed. ¹² In recent years, the particle swarm optimization was introduced for the problem and yielded outstanding results.^13,14 Besides, the problem was also solved by an improved iterated greedy algorithm, ¹⁵ a discrete differential evolution (DDE), ¹⁶ and a novel discrete self-organizing migrating algorithm ¹⁷ for the makespan minimization. In 2015, Ding et al. ¹⁸ proposed a tabu-mechanism improved iterated greedy algorithm for the problem, which is a modification of the iterated greedy algorithm using a tabu-based reconstruction strategy. To minimize total flowtime, Gao et al. ¹⁹ put forward an effective discrete harmony search (DHS) algorithm as well as a hybrid harmony search algorithm (HHS) ²⁰ for the NWFSP, but they did not compare these two algorithms. For the same criterion, a new particle swarm optimization hybridizing with a local search method was presented by Akhshabi et al., ²¹ and several constructive heuristics were shown with impressive performance.^22–24

Since Grover’s ²⁵ database search algorithm and Narayanan and Moore’s ²⁶ quantum GA, quantum algorithm has been a fresh research area attracting much attention. Han and Kim ²⁷ proposed quantum-inspired evolutionary algorithm (QEA) which proved to be efficacious for the knapsack problem. Like other evolutionary algorithms, QEA is also characterized by the representation of the individual, the evaluation function, and the population dynamics. However, instead of binary, numeric, or symbolic representation, QEA uses a Q-bit, defined as the smallest unit of information, for the probabilistic representation and a Q-bit individual as a string of Q-bits. Meanwhile, a Q-gate (or quantum gate) is introduced as a variation operator to drive the individuals toward better solutions.

Although the solution representation of the scheduling problem is thoroughly dissimilar to that of knapsack problem, the researchers have devoted great efforts to adapting the QEA for the scheduling problem. Li and Wang ²⁸ presented a hybrid quantum-inspired genetic algorithm (HQGA) for multiobjective flow shop scheduling, and Gu et al. ²⁹ proposed a competitive co-evolutionary quantum genetic algorithm (CCQGA) for stochastic job shop scheduling problem. Some other related research work can be found in Gu et al.^30–32

So far, there is little published research work on quantum algorithm solving the NWFSP. This article focuses on presenting an effective quantum-inspired hybrid metaheuristic algorithm for the NWFSP. The main innovation of the proposed algorithm lies in three aspects. First, an original coding and decoding mechanism is presented according to the characteristics of flow shop. Second, QEA and GA are combined concretely in a fresh way to form a new algorithm framework. In this framework, a store strategy, named store-with-diversity, is proposed, and QEA adopts Q-bit representation and GA adopts job permutation representation. Third, a competitive co-evolution is introduced in the algorithm to achieve a balance between exploration and exploitation. Generally, co-evolution can be classified into two categories: cooperative co-evolution and competitive co-evolution. ²⁹ Rosin and Belew ³³ conducted some research on competitive co-evolution adopting several interactional species. Due to the competition between individuals of different species, the individuals in each species evolve toward better solutions and the convergence is accelerated.

The remainder of this article is organized as follows: Section “Formulation of the NWFSP” provides the formulation of the NWFSP with makespan criterion. In section “CQGA,” a CQGA for NWFSP is proposed. Section “Simulations and comparisons” presents the computational results and comparisons. Finally, we summarize the contribution and draw some conclusions of this article in section “Conclusion.”

Formulation of the NWFSP

The NWFSP can be described as follows: Given the processing times p(j, k) for job j and machine k, each of n jobs (j = 1, 2,…, n) needs to be sequenced though m machines (k = 1, 2,…, m). The sequence in which the jobs are to be processed is the same for each machine. Each job j has a sequence of m operations (o_j1, o_j2,…, o_jm). To satisfy the no-wait restriction, the completion time of the operation o_jk must be equal to the earliest time to start of the operation o_j,k + 1 for k = 1, 2,…, m − 1. In other words, there must be no waiting time between the processing of any consecutive operation of each of n jobs. In this article, the makespan criterion is considered, so the problem is then to find a schedule minimizing the maximum completion time, that is, makespan.

Let the job permutation $\pi =\{{\pi }_1,{\pi }_2,\dots ,{\pi }_n\}$ represent the schedule of jobs to be processed, and $d({\pi }_{j-1},{\pi }_j)$ be the minimum delay on the first machine between the start of job ${\pi }_j$ and ${\pi }_{j-1}$ restricted by the no-wait constraint when the job ${\pi }_j$ is directly processed after the job ${\pi }_{j-1}$ . The minimum delay can be calculated from the following expression

$$d({\pi }_{j-1},{\pi }_j)=p({\pi }_{j-1},1)+\max \left[0,\underset{2\le k\le m}{\max }\left\{{\displaystyle \sum _{h=2}^{k}p({\pi }_{j-1},h)}-{\displaystyle \sum _{h=1}^{k-1}p({\pi }_j,h)}\right\}\right]$$

(1)

And the makespan can be calculated in O(mn) time as

$$C_{max}(\pi )=\sum _{j=2}^{n}d({\pi }_{j-1},{\pi }_j)+\sum _{k=1}^{m}p({\pi }_n,k)$$

(2)

Let $\Pi$ denote the set of all permutations, then the NWFSP with the makespan criterion is to find a permutation ${\pi }^{*}$ in $\Pi$ such that

$$C_{max}({\pi }^{*})\le C_{max}(\pi )\forall \pi \in \Pi$$

(3)

To illustrate the scheduling of jobs under the no-wait constraint, a simple example with n = 4 and m = 3 is used. The processing times p(j, k) compose matrix P with list of machines in columns and list of jobs in lines. Suppose that

$$P=\left(\begin{array}{ccc}\hfill 2\hfill & \hfill 3\hfill & \hfill 5\hfill \\ \multicolumn{1}{c}{5}& \hfill 1\hfill & \hfill 3\hfill \\ \multicolumn{1}{c}{4}& \hfill 5\hfill & \hfill 2\hfill \\ \multicolumn{1}{c}{1}& \hfill 3\hfill & \hfill 2\hfill \end{array}\right)$$

and the job permutation is $\pi =\{1,2,3,4\}$ , then the scheduling Gantt chart is shown in Figure 1. The makespan is calculated as follows

$$d(1,2)=p(1,1)+\max [0,\max \{p(1,2)-p(2,1),p(1,2)+p(1,3)-(p(2,1)+p(2,2))\}]=2+2=4$$

$$d(2,3)=p(2,1)+max[0,max\{p(2,2)-p(3,1),p(2,2)+p(2,3)-(p(3,1)+p(3,2))\}]=5+0=5$$

$$d(3,4)=p(3,1)+max[0,max\{p(3,2)-p(4,1),p(3,2)+p(3,3)-(p(4,1)+p(4,2))\}]=4+4=8$$

$$C_{max}(\pi )=d(1,2)+d(2,3)+d(3,4)+\sum _{k=1}^{3}p(4,k)=23$$

Figure 1.

Gantt chart of the example.

CQGA

Since it was proposed recently, QEA has been applied to both functional and combinatorial problems and attracted lots of attention, but there is little published research work about quantum algorithm solving the NWFSP. This section proposes co-evolutionary quantum genetic algorithm (CQGA) and describes each part of it in detail. Before putting forward the framework of CQGA, we introduce an innovative coding and decoding mechanism.

Coding and decoding method

In the previous research by Li and Wang ²⁸ and Gu et al., ²⁹ they applied the qubit representation to the flow shop and job shop scheduling. They obtained binary strings from qubit individuals, decimal strings from binary strings, and job permutation from decimal strings, which was called random-key representation. For example, suppose a binary sting is [1 0 1 | 0 1 1 | 1 1 0], which is obtained from a Q-bit representation by observation, then the decimal string is [5 3 6]. From small to large, the job permutation is gained as [2 1 3]. More details could be found in their research articles.

According to the characteristics of NWFSP with n jobs, we propose that the state of a qubit can be represented as

$$|\Psi 〉={\alpha }_1|1〉+{\alpha }_2|2〉+\cdots +{\alpha }_n|n〉$$

(4)

where ${\alpha }_i$ is a complex number and ${\left|{\alpha }_i\right|}^2$ is the probability that job i is selected (i = 1, 2,…, n). Correspondingly, normalization of the state to unity requires

$$\sum _{i=1}^n{\left|{\alpha }_i\right|}^2=1$$

(5)

Thus, a qubit individual for NWFSP is defined as a square matrix

$$\left(\begin{array}{ccc}\hfill {\alpha }_{11}\hfill & \hfill \dots \hfill & \hfill {\alpha }_{1n}\hfill \\ \multicolumn{1}{c}{⋮}& \hfill \ddots \hfill & \hfill ⋮\hfill \\ \multicolumn{1}{c}{{\alpha }_{n1}}& \hfill \cdots \hfill & \hfill {\alpha }_{\mathrm{nn}}\hfill \end{array}\right)$$

(6)

where $\sum _{i=1}^n{\left|{\alpha }_{\mathrm{ij}}\right|}^2=1,j=1,2,\dots ,n$ , n is the number of jobs, and ${\left|{\alpha }_{\mathrm{ij}}\right|}^2$ denotes the probability of job i being scheduled in the jth position of permutation.

When it comes to the operation of observation, a job is got from each column of the square matrix and the job permutation can be obtained by rouletee wheel selection from the first to the last. Note that if a job has been selected in the permutation from the hth column of the matrix, then when selecting the (h + 1)th job in the permutation from the (h + 1)th column of the matrix, we can only select the unselected jobs yet. Suppose these jobs are job k₁, job k₂,…, job k_n − h, and therefore, the probabilities corresponding to these jobs to be selected are not simply ${\left|{\alpha }_{k_1,h+1}\right|}^2$ , ${\left|{\alpha }_{k_2,h+1}\right|}^2$ ,…, ${\left|{\alpha }_{k_{n-h},h+1}\right|}^2$ , but ${\left|{\alpha }_{k_1,h+1}\right|}^2/\Delta$ , ${\left|{\alpha }_{k_2,h+1}\right|}^2/\Delta$ ,…, ${\left|{\alpha }_{k_{n-h},h+1}\right|}^2/\Delta$ , where $\Delta =\sum _{i=1}^{n-h}{\left|{\alpha }_{k_i,h+1}\right|}^2$ .

For instance, consider a NWFSP with three jobs. Suppose a qubit individual is represented as a square matrix with each elements equal to $1/\sqrt{3}$ . At first, a job is selected by rouletee wheel selection, and from the first column, we know the probabilities corresponding to job 1, job 2, and job 3 are 1/3, 1/3, and 1/3, respectively. According to rouletee wheel selection, a random number rnd is generated from the uniform distribution [0, 1]. If $\mathrm{rnd}\le 1/3$ , job 1 is selected, if $1/3<\mathrm{rnd}\le 2/3$ , job 2 is selected, and if $2/3<\mathrm{rnd}\le 1$ , job 3 is selected. Suppose job 2 has been selected in the permutation, and then when selecting the second job from the second column, there are two jobs to select, job 1 and job 3, and the corresponding probabilities are 1/2 and 1/2, respectively. Finally a job permutation will be generated. Such a mechanism which is an innovation in this article can make the permutation solution directly and will be used in the proposed algorithm.

CQGA for the NWFSP

The procedure of CQGA for the NWFSP is described in the following:

• Step 1: let t = 0 and initialize all the parameters and two quantum populations Q1(t), Q2(t).

• Step 2: make P1(t), P2(t) by observation operation of Q1(t), Q2(t), respectively.

• Step 3: evaluate P1(t), P2(t).

• Step 4: store the solutions from P1(t), P2(t) to B1(t), B2(t), respectively, store b and let hb^t = b^t.

• Step 5: if a stopping condition is satisfied, then output the results; otherwise, continue the following steps.

• Step 6: let t = t + 1 and make P1(t), P2(t) by observation operation of Q1(t − 1), Q2(t − 1), respectively.

• Step 7: evaluate P1(t), P2(t).

• Step 8: update Q1(t − 1), Q2(t − 1) using Q-gate.

• Step 9: store-with-diversity in B1(t), B2(t), and store b^t, hb^t.

• Step 10: P1(t), P2(t) are replaced with B1(t), B2(t), respectively.

• Step 11: compete between P1(t) and P2(t).

• Step 12: selection, crossover and mutation for P1(t), P2(t), respectively.

• Step 13: evaluate P1(t), P2(t).

• Step 14: store-with-diversity in B1(t), B2(t), and store b^t, hb^t.

• Step 15: perform the migration and go to Step 5.

The overall framework of CQGA is illustrated in Figure 2. It can be seen that CQGA contains two spaces and each space consists of three populations: Q, P, and B, like QEA. The proposed CQGA involving a competitive co-evolution strategy is a hybridization of QEA with GA, and it adopts a coding and decoding mechanism introduced above. Besides, we put forward the store-with-diversity in CQGA. The details of each step are described as follows:

• Step 1: initialize: the Gen (iterative generation), Pc (crossover probability), Pm (mutation probability), N (popsize), $\theta$ (rotation angle), Q1(0) and Q2(0) (quantum population). Q1(t) (or Q2(t)) is made up of N qubit individuals represented as in the proposed mechanism above. All elements in the matrix corresponding to every qubit individual are initialized with $1/\sqrt{n}$ , where n is the number of jobs in FSP, which means that all possible jobs are selected in the permutation with the same probability originally. Note: $Q1(0)=\{q_{11}^0,q_{12}^0,\dots ,q_{1N}^0\}$ and $Q2(0)=\{q_{21}^0,q_{22}^0,\dots ,q_{2N}^0\}$ at generation t = 0.

• Step 2: this step makes permutation solutions in P1(0), P2(0) by observing the states of Q1(0), Q2(0), respectively, and the observation is performed as in the proposed mechanism above. Note: $P1(0)=\{p_{11}^0,p_{12}^0,\dots ,p_{1N}^0\}$ and $P2(0)=\{p_{21}^0,p_{22}^0,\dots ,p_{2N}^0\}$ at generation t = 0. For notational simplicity, q is used instead of any individual in Q1(t) or Q2(t), and p in P1(t) or P2(t) is used instead of the corresponding individual of q. Let p = (e₁, e₂,…, e_n) and $q=({\alpha }_{\mathrm{ij}}{)}_{n\times n}$ , then e_j (j = 1, 2,…, n) is obtained by observing the jth column of q.

• Step 3: each solution in P1(0), P2(0) is evaluated by calculating the objective value. Given that we are solving the NWFSP, the objective value is obtained according to the formulation in section “Formulation of the NWFSP.”

• Step 4: the solutions in P1(0), P2(0) are stored into B1(0), B2(0), respectively, where $B1(0)=\{b_{11}^0,b_{12}^0,\dots ,b_{1N}^0\}$ and $B2(0)=\{b_{21}^0,b_{22}^0,\dots ,b_{2N}^0\}$ . B1(t) and B2(t) are used to store relatively better solutions. At the initial generation, we have $b_{\mathrm{ij}}^0=p_{\mathrm{ij}}^0,i=1,2;j=1,2,\dots ,N$ . The best solution in B1(t), B2(t) is stored as b^t, and hb^t represents the history best solution. Thus hb⁰ is the same as b⁰ at t = 0.

• Step 5: the stopping condition is t = Gen. The best solution for output is hb^t.

• Step 6: permutation solutions in P1(t), P2(t) are formed by observing Q1(t − 1), Q2(t − 1), respectively, as in Step 2.

• Step 7: evaluate each solution as in Step 3.

• Step 8: this step updates qubit individuals by operation of a quantum gate which is modified in accordance with the novel coding and decoding mechanism.

Figure 2.

Overall framework of CQGA.

A Q-gate is an important updating method to drive the individuals toward better solutions in quantum evolutionary algorithm. ²⁸ A quantum gate is a reversible gate and can be represented as a unitary operator U satisfying U⁺U = UU⁺, where U⁺ is the hermitian adjoint of U. There are several quantum gates, such as the NOT gate, controlled NOT gate, rotation gate, and Hadamard gate.

Here, a rotation gate is used. To comply with the proposed coding and decoding mechanism, only two numbers may need to be updated in the jth Q-bit $({\alpha }_{1j},{\alpha }_{2j},\dots ,{\alpha }_{\mathrm{nj}})$ as follows

$$\left[\begin{array}{c}\hfill {\alpha }_{\mathrm{xj}}^{\prime }\hfill \\ \multicolumn{1}{c}{{\alpha }_{\mathrm{yj}}^{\prime }}\end{array}\right]=U({\theta }_j)\left[\begin{array}{c}\hfill {\alpha }_{\mathrm{xj}}\hfill \\ \multicolumn{1}{c}{{\alpha }_{\mathrm{yj}}}\end{array}\right]=\left[\begin{array}{cc}\hfill \cos ({\theta }_j)\hfill & \hfill -\sin ({\theta }_j)\hfill \\ \multicolumn{1}{c}{\sin ({\theta }_j)}& \hfill \cos ({\theta }_j)\hfill \end{array}\right]\left[\begin{array}{c}\hfill {\alpha }_{\mathrm{xj}}\hfill \\ \multicolumn{1}{c}{{\alpha }_{\mathrm{yj}}}\end{array}\right]$$

(7)

where ${\theta }_j$ is a rotation angle determining the rotation direction and magnitude and its lookup table is presented in Table 1, and x, y are jobs scheduled in the jth position of p, b, respectively, assuming b in B1(t) or B2(t) is the corresponding individual of p.

Table 1.

Lookup table of ${\theta }_j$ .

f(p) > f(b)	$x\ne y$	Quadrant ( ${\alpha }_{\mathrm{xj}},{\alpha }_{\mathrm{yj}}$ )	${\theta }_j$
True	True	1 or 3	$\theta$
True	True	2 or 4	$-\theta$
True	False	1 or 3	0
True	False	2 or 4	0
False	True	1 or 3	0
False	True	2 or 4	0
False	False	1 or 3	0
False	False	2 or 4	0

Figure 3 depicts the polar plot of the rotation gate for Q-bit individuals. As illustrated in Table 1, the rotation occurs only when the condition f(p) > f(b) is true and x is not the same as y: if ( ${\alpha }_{\mathrm{xj}},{\alpha }_{\mathrm{yj}}$ ) is located in the first or the third quadrant in Figure 3, the angle value is set to a positive value $\theta$ to increase the probability of job y being selected; if ( ${\alpha }_{\mathrm{xj}},{\alpha }_{\mathrm{yj}}$ ) is located in the second or the fourth quadrant, $-\theta$ is used to increase the probability of job y being selected. For all the other situations, even when ( ${\alpha }_{\mathrm{xj}},{\alpha }_{\mathrm{yj}}$ ) is located in the coordinate axes, ${\theta }_j$ is set to 0, which means no rotation.

Figure 3.

Polar plot of rotation gate for Q-bit individuals.

It is clear that unitary operator $U({\theta }_j)$ can still meet the demand of normalization. In fact, after the unitary operator U, we have

$${\left|{\alpha }_{\mathrm{xj}}^{\prime }\right|}^2+{\left|{\alpha }_{\mathrm{yj}}^{\prime }\right|}^2={\left|{\alpha }_{\mathrm{xj}}\right|}^2+{\left|{\alpha }_{\mathrm{yj}}\right|}^2$$

(8)

which still makes

$$\sum _{i=1}^n{\left|{\alpha }_{\mathrm{ij}}\right|}^2=1,j=1,2,\dots ,n$$

(9)

• Step 9: in population B1(t) and B2(t), there may be some individuals with the same permutations. Therefore, store-with-diversity is proposed in the framework of CQGA to maintain the diversity of populations, which is different from the initial store in Step 4. After store-with-diversity, if the best solution in B1(t) and B2(t) is better than the stored b^t−1, b^t is replaced with the new one, then if b^t is better than the stored hb^t−1, hb^t is replaced with b^t.

In store-with-diversity, the generation t is omitted for simplicity. For population P1, we try to store $p_{11},p_{12},\dots ,p_{1N}$ into $b_{11},b_{12},\dots ,b_{1N}$ , respectively, in sequence. $b_{11},b_{12},\dots ,b_{1N}$ are randomly rearranged to get ready to accept the individuals in P1 before storing. At first, if $p_{11}$ is better than or equal to $b_{11}$ , $b_{11}$ is replaced with $p_{11}$ , otherwise compare $p_{11}$ with $b_{12}$ , if $p_{11}$ is better than or equal to $b_{12}$ , $b_{12}$ is replaced with $p_{11}$ , otherwise go on till $p_{11}$ and $b_{1N}$ are compared, when it is worse than all individuals in P1, $p_{11}$ is not stored. Then we consider $p_{12},\dots ,p_{1N}$ in sequence. The same operation is performed for population P2. It is clear that store-with-diversity can keep the diversity of populations.

• Step 10: P1(t), P2(t) are replaced with B1(t), B2(t), respectively. This step prepares for the ensuing competition and the genetic operations.

• Step 11: the improved competition is held between P1(t) and P2(t). For each individual p in P1(t), all the individuals in P2(t) are its competitors. The value of competition is defined as

$$c(p)=\sum _{p_{2j}^t\in P2(t)}\{\begin{array}{cc}\hfill 1\hfill & \hfill \mathrm{if}p\mathrm{is}\mathrm{better}\mathrm{than}{p}_{2j}^t\hfill \\ \multicolumn{1}{c}{0}& \hfill \mathrm{else}\hfill \end{array},j=1,2,\dots ,N$$

(10)

It can be seen that c(p) is an integer in the range of [0, N], then the fitness of p is computed as

$$\mathrm{fit}(p)=r\times \frac{c(p)+1}{N}$$

(11)

where r affects the effects of competition.

For each individual in P2(t), all the individuals in P1(t) are its competitors. The competition is performed as above.

• Step 12: this step executes the genetic evolution on P1(t) and P2(t), respectively. Here, Rouletee wheel selection based on fitness value, partially mapped crossover (PMX), ³⁴ and mutation operator INSERT ²⁸ is adopted.

• Step 13: the same as in Step 7.

• Step 14: the same as in Step 9.

• Step 15: the migration ²⁶ is performed in each generation. The best in B1(t) is swapped with the best in B2(t), so is the worst.

Simulations and comparisons

All the algorithms involved in this article were programmed in Visual C++ and conducted on an Intel Pentium IV 3.06 GHz PC with 1024 MB memory. To compare the performance of different algorithms, the experiments were conducted using the well-known Taillard ³⁵ benchmark set, which is composed of 120 problem instances, ranging from 20 jobs and five machines to 500 jobs and 20 machines. In our simulations, only the former 90 instances were treated by the compared algorithms for simplicity. The satisfied parameter setting of the CQGA was calibrated, and then we employed the CQGA to solve each instance with replications. The solution quality is evaluated according to the reference makespans. As in Ding et al., ¹⁸ the indicator percentage relative deviation (PRD) was adopted to measure the amount of improvement over the reference makespans. Obviously, the smaller PRD is, the better the corresponding solution is. To be specific, PRD is calculated as

$$\mathrm{PRD}=\frac{(M-M_{\mathrm{ref}})}{M_{\mathrm{ref}}}\times 100$$

(12)

where M, M_ref are makespan obtained by algorithms in each run and the reference makespan, respectively. The best known solutions provided in Ding et al. ¹⁸ are used as reference makespan, as shown in Table 2.

Table 2.

Best known solutions for Taillard benchmark set.

Instance	Best known solution	Instance	Best known solution	Instance	Best known solution
20 × 5		50 × 5		100 × 5
Ta01	1486	Ta31	3161	Ta61	6397
Ta02	1528	Ta32	3432	Ta62	6234
Ta03	1460	Ta33	3211	Ta63	6121
Ta04	1588	Ta34	3339	Ta64	6026
Ta05	1449	Ta35	3356	Ta65	6200
Ta06	1481	Ta36	3347	Ta66	6074
Ta07	1483	Ta37	3231	Ta67	6247
Ta08	1482	Ta38	3235	Ta68	6130
Ta09	1469	Ta39	3072	Ta69	6370
Ta10	1377	Ta40	3317	Ta70	6381
20 × 10		50 × 10		100 × 10
Ta11	2044	Ta41	4274	Ta71	8077
Ta12	2166	Ta42	4177	Ta72	7880
Ta13	1940	Ta43	4099	Ta73	8028
Ta14	1811	Ta44	4399	Ta74	8348
Ta15	1933	Ta45	4322	Ta75	7958
Ta16	1892	Ta46	4289	Ta76	7801
Ta17	1963	Ta47	4420	Ta77	7866
Ta18	2057	Ta48	4318	Ta78	7913
Ta19	1973	Ta49	4155	Ta79	8161
Ta20	2051	Ta50	4283	Ta80	8114
20 × 20		50 × 20		100 × 20
Ta21	2973	Ta51	6129	Ta81	10,700
Ta22	2852	Ta52	5725	Ta82	10,594
Ta23	3013	Ta53	5862	Ta83	10,611
Ta24	3001	Ta54	5788	Ta84	10,607
Ta25	3003	Ta55	5886	Ta85	10,539
Ta26	2998	Ta56	5863	Ta86	10,690
Ta27	3052	Ta57	5962	Ta87	10,825
Ta28	2839	Ta58	5926	Ta88	10,839
Ta29	3009	Ta59	5876	Ta89	10,723
Ta30	2979	Ta60	5958	Ta90	10,798

Parameter calibration

This part considers the values of the parameters to make CQGA obtain satisfying results for the NWFSP. For fair comparison, we set CQGA with N = 10 n and the stopping criterion as elapsed CPU time not less than 3 n²m milliseconds. For parameter r, our pilot experiment showed that a value between 600 and 1200 is acceptable, and here we set it to 1000 to get a proper competition pressure. Besides, there are three essential parameters $\theta$ , Pc, and Pm to be determined. To get a convincing parameter setting, a design of experiments was performed. The parameters were tested at the following levels: (a) θ = 0.0005π, 0.002π, 0.01π, 0.05π; (b) Pc = 0.6, 0.7, 0.8, 0.9; and (c) Pm = 0.005, 0.025, 0.1, 0.2. Therefore, 4³ parameter configurations were examined. We selected nine instances, Ta01, Ta11,…, Ta81, from each problem group to avoid bias of the results, and the algorithm is run five replications for each configuration for each considered instance. In total, we have 4³ × 9 × 5 = 2880 runs. Based on such a large data set, the analysis of variance (ANOVA) results are shown in Table 3. It can be seen from Table 3 that since its p-value is less than 0.0001, the parameters $\theta$ and Pc are both significant, while that parameters Pm with p-value equal to 0.1586 is less significant.

Table 3.

ANOVA results for the experiment on the parameter calibration.

Source	Sum of squares	Df	F-value	p-Value
Main effects
A: theta	6.38	3	57.43	<0.0001
B: pc	4.85	3	22.66	<0.0001
C: pm	0.72	3	2.82	0.1586
Interactions
AB	2.174e−004	9	4.346e−003	1.0000
AC	3.509e−004	9	2.105e−003	1.0000
BC	4.21	9	2.64	<0.0001

To show the performance differences of parameter levels more clearly, the one factor means plots with 95% least significant difference (LSD) confidence intervals of the factors $\theta$ and Pc are shown in Figure 4. Note that if the LSD intervals for two means are not overlapping, then the means are considered significantly different. Therefore, Figure 4 illustrates that for factor $\theta$ , the value 0.01π is significantly better than the others, while for factor Pc, the value 0.8 is a relatively better choice. As regards parameter Pm, the differences are small and its means plot is omitted for simplicity, and in the performance test, it is set as 0.1.

Figure 4.

Means plot with 95% LSD intervals for the parameters of the algorithm.

Comparisons of VNS, GASA, hybrid particle swarm optimization, and CQGA

For the NWFSP, the GA ¹⁰ and GASA ¹¹ were impressive because they successfully solved the problem in a considerably minor time. Besides, the hybrid particle swarm optimization (HPSO) proposed by Liu et al. ¹³ also showed its excellent performance. As far as we know, no literature could be found about quantum algorithms for the NWFSP, and in this part, we will compare CQGA with GA, GASA, and HPSO. The computational experiments were based on the 90 Taillard instances, and each algorithm was run for each instance with 30 replications. The stopping criterion was 3 n²m milliseconds CPU time to get an unbiased statistical result. The average percentage relative deviation (APRD) values grouped in subsets of different sizes are summarized in Table 4.

Table 4.

APRD of each algorithm on Taillard benchmark set.

n × m	GA	GASA	HPSO	CQGA
20 × 5	4.39	2.97	1.97	1.62
20 × 10	4.65	3.19	2.25	1.84
20 × 20	4.77	3.36	2.46	1.98
50 × 5	4.94	3.45	2.57	2.17
50 × 10	5.30	3.83	2.96	2.49
50 × 20	6.62	5.23	4.48	3.91
100 × 5	5.85	4.29	3.32	2.86
100 × 10	6.52	5.14	4.17	3.75
100 × 20	6.94	5.67	4.62	4.17
Overall mean	5.55	4.13	3.20	2.76

GA: genetic algorithm; GASA: genetic algorithm hybridized with simulated annealing; HPSO: hybrid particle swarm optimization; CQGA: co-evolutionary quantum genetic algorithm.

It should be noted that the compared algorithms were executed in the same running environment and with the stopping criterion, so the results are comparable. We can see from Table 4 that the overall mean PRD value obtained by the CQGA is 2.76, which is substantially lower than that of the HPSO (3.20), that of the GASA (4.13), and that of the HPSO (5.55). The similar priority relation holds when the APRD values of each subset of different sizes are examined.

In order to observe whether the performance differences in the PRD values are indeed statistically significant, we employed the original PRD data points and conducted an ANOVA. To be brief, we only provide the one factor means plots with 95% least significant difference (LSD) confidence intervals of the algorithms in Figure 5. The statistical results indicate that the differences between these algorithms are significant. The GA yields the poorest results while the CQGA is superior to the others. It is worth noting that the HPSO is also a positive algorithm because it achieved excellent results whereas its structure is quite simple.

Figure 5.

Means plot with 95% LSD intervals for the compared algorithms.

Conclusion

This article presents an effective and robust quantum-inspired hybrid metaheuristic combining QEA and GA for the NWFSP. According to the characteristics of the problem, an innovative coding and decoding mechanism is presented. In this mechanism, a quantum individual is represented as a square matrix, and a job permutation can thus be simply gained without use of random-key representation. In the framework combining QEA and GA, we put forward the store-with-diversity to maintain the diversity of populations. A competitive co-evolution is introduced in the algorithm to achieve a balance between exploration and exploitation. Simulation results and comparisons based on a set of benchmarks demonstrate the effectiveness and robustness of the proposed algorithm. Our future work lies in two directions. One is to apply quantum-inspired hybrid algorithms to the FSP with no-idle constraint, ³⁶ as well as job shop scheduling problems. The other is to consider more powerful problem-dependent algorithms for the NWFSP and its multiobjective optimization.