# Pareto-Ranking Based Quantum-Behaved Particle Swarm Optimization for Multiobjective Optimization

Authors: Na Tian; Zhicheng Ji
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

A study on pareto-ranking based quantum-behaved particle swarm optimization (QPSO) for multiobjective optimization problems is presented in this paper. During the iteration, an external repository is maintained to remember the nondominated solutions, from which the global best position is chosen. The comparison between different elitist selection strategies (preference order, sigma value, and random selection) is performed on four benchmark functions and two metrics. The results demonstrate that QPSO with preference order has comparative performance with sigma value according to different number of objectives. Finally, QPSO with sigma value is applied to solve multiobjective flexible job-shop scheduling problems.


---

## Body

## 1. Introduction

Most real-world optimization problems have more than one objective, with at least two objectives conflicting with each other. The conflicting objectives lead to a problem where a single solution does not exist. Instead, a set of optimal trade-off solutions exists, which are referred to as the pareto-optimal front or pareto front. This kind of optimization problems is referred to as multiobjective optimization problems.In the past ten years, a wide variety of algorithms have been proposed to address such problems. Deb et al. [1] gave rise to a fast and elitist multiobjective genetic algorithm (NSGA-II) to reduce the computational complexity and adopted an elitism strategy. In [2], Konak et al. gave a tutorial about several variants of genetic algorithms and compared their performance. A particle swarm optimization (PSO) with pareto dominance was proposed in [3], in which a secondary repository and a special mutation operator were incorporated. A survey of the state-of-the-art multiobjective PSOs is presented in [4]. From the above literatures, the great difference between genetic algorithm (GA) and PSO exists for solving the multiobjective optimization problems. In GA, a set of particles are needed to be selected into next generation, while, in QPSO, one particle has to be chosen from the nondominated optima as the global best position (gbest). Therefore, different pareto-ranking strategies are required.Inspired by the quantum mechanics, QPSO was proposed by Sun et al. in 2004 [5], which has been proved to outperform PSO in both convergence rate and global search ability [6, 7]. Similar to other population-based algorithms (GA, PSO), maintaining a diverse population is an important consideration in multiobjective optimization to ensure solutions uniformly distributed over the pareto front. Therefore, in this paper, QPSO with three pareto-ranking strategies is compared on some benchmark functions and two metrics are used to test the performance of each strategy.The research on the multiobjective FJSP is not as widely as that on the monoobjective FJSP. Brandimarte [8] was first to apply the decomposition method to FJSP and solved the routing subproblem by using some existing dispatching rules and addressed the scheduling subproblem by using a tabu search algorithm. Davarzani et al. [9] used artificial immune system to solve the multiobjective FJSP and compared it with Approach by Localization [10], AL + CGA [11]. Considering the advantages and disadvantages of stochastic algorithms and local search methods, some hybrid approaches were also proposed [12, 13]. In this paper, QPSO with sigma value is applied to solve multiobjective flexible job-shop scheduling.The remainder of this paper is organized as follows. In Section2, some basic concepts for multiobjective optimization are provided. Section 3 describes the three variants of pareto-ranking based QPSO in detail. Numerical tests on benchmark functions are presented in Section 4. In Section 5, QPSO with sigma value is applied to solve multiobjective flexible job-shop scheduling. Finally, conclusion is given in Section 6.


## 2. Basic Concepts for Multiobjective Optimization

Without loss of generality, only minimization problem is assumed here:(1)minimizef→x→=f1x→,f2x→,…,fnx→Tsubjected togix→≤0,i=1,2,…,q,hix→=0,i=1,2,…,p,where x→=x1,x2,…,xDT∈Ω is the vector of decision variables. fi, i=1,2,…,n, are the objective functions, gi and hj(i=1,2,…,q, j=1,2,…,p) are the constraint functions of the problem, D is the dimension size of the search space, and n is the number of objectives.Definition 1 (pareto dominance).
A vectoru→=u1,u2,…,un dominates v→=v1,v2,…,vn (denoted by u→⪯v→) if and only if u is partially less than v; that is, ∀i∈1,2,…,n, ui≤vi, and ∃i∈1,2,…,n, ui<vi.Definition 2 (pareto optimal set).
One hasP∗=x∈Ω∣¬∃x′∈Ω,f→x′⪯f→x.Definition 3 (pareto front).
For a given pareto optimal setP∗, the pareto front is defined as PF∗=u→=f→=f1(x),f2(x),…,fn(x)∣x∈P∗.Generally, the analytical expression of the line or surface which contain those points does not exist. It is only possible for us to determine the nondominated points and to produce the pareto front.


## 3. Pareto-Ranking Based Quantum-Behaved Particle Swarm Optimization

### 3.1. Particle Swarm Optimization

PSO is a population-based optimization technique originally proposed by Kennedy and Eberhart in 1995 [14]. A PSO system simulates the knowledge evolvement of a social organism, in which particles represent candidate solutions of an optimization problem. The position of each particle is evaluated according to the objective function, and particles share memories of their “best” positions. These memories are used to adjust the particles’ own velocities and their subsequent positions. It has already been shown that PSO is comparable in performance with and may be considered as an alternative to GA [15].Ina PSO system withM particles in the D-dimensional space, the position, and velocity vector of particle i at thekth iteration is represented as Xi(t)=(Xi1(t),Xi2(t),…,XiD(t)) and Vi(t)=(Vi1(t),Vi2(t),…,ViD(t)). The particle moves according to the following equations: (2)Vit+1=ωVit+c1r1Pit-Xit+c2r2Pgt-Xit,Xit+1=Xit+Vit+1,where, i=1,2,…,M, j=1,2,…,D, c1 and c2 are acceleration coefficient. r1 and r2 are random numbers distributed uniformly in (0,1). ω is inertia weight. Vector Pi=(Pi1,Pi2,…,PiD) is the previous best position of particle i (pbest), and vector Pg=(Pg1,Pg2,…,PgD) is the position of the best particle g in the swarm (gbest).


### 3.2. Quantum-Behaved Particle Swarm Optimization

The main disadvantage of PSO is that it is not guaranteed to be global convergent [16]. Concepts of QPSO were developed to address this disadvantage and first reported by Sun et al. in 2004 [5]. Trajectory analysis in [17] demonstrated the fact that the convergence of PSO may be achieved if each particle converges to its local attractor, pi=(pi1,pi2,…,piD), defined as (3)pit=φPit+1-φPgt,where φ∈(0,1). It can be seen that pi is a stochastic attractor of particle i that lies in a hyperrectangle with Pi and Pg being two ends of its diagonal and moves following Pi and Pg.In quantum world, the velocity of the particle is meaningless, so, in QPSO system, position is the only state to depict the particles, which moves according to the following equation [5]: (4)Xit+1=pit±αmbestt-Xitln⁡1u,where u is a random number uniformly distributed in (0,1) and mbest(t), called mean best position, is defined as the mean value of personal best positions of the swarm: (5)mbestt=1M∑i=1MPi=1M∑i=1MPi1t,1M∑i=1MPi2t,…,1M∑i=1MPiDt.The parameter α in (4) is named as contraction-expansion (CE) coefficient, which can be adjusted to control convergence rate. The most commonly used method to control CE is linearly decreasing from αmax to αmin: (6)α=αmax⁡-αmin⁡tmax⁡-ttmax⁡+αmin⁡,where t is the current iteration step, tmax is the predefined maximum iteration steps, and αmax and αmin are the maximum and minimum value of CE.QPSO does not require velocity vectors for the particles and has fewer parameters to control, making the algorithm easier to implement. Experimental results performed on some well-known benchmark functions show that QPSO has better performance than PSO [5–7].A great deal of efforts has been made to PSO for solving multiobjective optimization problems. A survey of state-of-the-art works is presented in [4]. The most contributive work is proposed by Ceollo et al. [3], in which the objective space is divided into hypercubes using an adaptive grid. The nondominated solutions are distributed into grids and then the grid is chosen according to a roulette wheel selection strategy. However, the grid is problems dependent and computation complicated. While in [18] a new density measure strategy named as sigma method was introduced to multiobjective PSO, so as to choose a gbest from the nondominated archive, the sigma method can guide particles to the pareto optimal front. However, if the initialized solutions in nondominated archive are bad, the algorithm will fall into local optimum due to the fast convergence. Yang et al. [19] proposed a hybrid method which combined the density information and sigma method so as to achieve a balance between global search and local search. Considering the calculation of the density value and crowding distance is limited by two objectives. When the number of objectives becomes large, the measure of density and crowding distance will become invalid. Therefore, the idea of preference order is introduced [20].


### 3.3. Preference Order

As we all know, when the optimization problem has two objectives, the pareto optimal solutions can be plotted on a curve. Though the trade-off surface can also be visualized for three objectives, it is not easy to pick the final point. For problems with more than three objectives, it becomes extremely difficult to find the optimized solution through visualization.The idea of preference order was firstly proposed in 1999 [21]. A point x∗∈Ω is said to be efficiency of order k if f(x∗) is not dominated by any of the k-element subsets of fΩ.Consider a minimization example with three objectives in Table1; combination of all subsets of the objectives is f1,f2,f3,(f1,f2),(f2,f3),(f1,f3).Table 1
Nondominated set.
Points
f
1
f
2
f
3
Point 1
0.5
2.1
11.2
Point 2
6
1.1
1.3
Point 3
3.14
0
3.76
Point 4
1.1
0.5
4.32
Point 5
3.89
0.1
3.23The dominant relation of all points in 2-element subsets is shown in Table2, from which only Point 3 is nondominated by any points on all 2-element subsets. So Point 3 is said to be efficiency of order 2.Table 2
Dominant relation.
Points
Point 1
Point 2
Point 3
Point 4
Point 5
Point 1
×
×
×
×
×
Point 2
(
f
2
,
f
3
)
×
×
×
×
Point 3
(
f
2
,
f
3
)
(
f
1
,
f
2
)
×
(
f
2
,
f
3
)
(
f
1
,
f
2
)
Point 4
(
f
2
,
f
3
)
(
f
1
,
f
2
)
×
×
(
f
1
,
f
2
)
Point 5
(
f
2
,
f
3
)
(
f
1
,
f
2
)
×
(
f
2
,
f
3
)
×About efficiency of order, [22] gave three claims.Claim 1.
In a space withn objectives, there is no more than one point with efficiency of order n-1.Claim 2.
x
∗ is efficient of order k+1, if it is efficient of order k.Claim 3.
x
∗ is not efficient of order k-1, if it is not efficient of order k.The pseudocode of QPSO with preference order is shown below.Preference-Order Based QPSO
(1)
Initialization: initialize the swarm sizeM, the external archive size ND, and the maximum number of iterations tmax, CE α. Position of each particle Xi, i=1,2,…,M, is randomly initialized. Personal best position of each particle pbesti is equal to Xi. Construct external nondominated set nds.
(2)
Update the following:
(a)
Identify global best position using preference-order method.
(i)
Get combination of all subsets forn objectives.
(ii)
Compute the efficiency order for each nondominated solution.
(iii)
Sort nondominated solutions in descending order according to their efficiency order.
(iv)
Getgbest.
(b)
Update position of each particle according to (3), (4), and (5).
(c)
Updatepbest according to dominance rule.
(d)
Update external archive and remove solution with lower efficiency order if archive sizeND is exceeded.
(e)
Updateα according to (6).
(3)
Repeat(2) until the maximum number of iterations is reached.


### 3.4. Sigma Method

The sigma method was first proposed in [18] for finding the best local guide for each particle. Each nondominated solution in the external repository is assigned a value σi, i=1,2,…,ND, which is defined as (for two objectives shown in Figure 1.) (7)σi=fi,12-fi,22fi,12+fi,22.In the general case, σ is a vector of N2 elements, and each element is the combination of two coordinates. Take a problem of three objectives; for example, (8)σi=fi,12-fi,22fi,22-fi,32fi,32-fi,12fi,12+fi,22+fi,32.Figure 1
Sigma value for a two-objective space.The pseudocode of QPSO with sigma value is shown below.QPSO with Sigma Method
(1)
Initialization: initialize the swarm sizeM, the external archive size ND, and the maximum number of iterations tmax, CE α. Position of each particle Xi, i=1,2,…,M, is randomly initialized. Personal best position of each particle pbesti is equal to Xi. Construct external nondominated set nds.
(2)
Update the following:
(a)
Identify local best position using sigma method.
(i)
Assign the valueσj to each particle in the external archive.
(ii)
Calculate the valueσi for each particle in the swarm.
(iii)
Calculate the distance betweenσi and σj.
(iv)
The particlek in the archive with σk has the minimum distance to σi selected as the best local guide for the particle i.
(b)
Update position of each particle according to (3), (4), and (5).
(c)
Updatepbest according to dominance rule.
(d)
Updateα according to (6).
(3)
Repeat
(
2
) until the maximum number of iterations is reached.


## 3.1. Particle Swarm Optimization

PSO is a population-based optimization technique originally proposed by Kennedy and Eberhart in 1995 [14]. A PSO system simulates the knowledge evolvement of a social organism, in which particles represent candidate solutions of an optimization problem. The position of each particle is evaluated according to the objective function, and particles share memories of their “best” positions. These memories are used to adjust the particles’ own velocities and their subsequent positions. It has already been shown that PSO is comparable in performance with and may be considered as an alternative to GA [15].Ina PSO system withM particles in the D-dimensional space, the position, and velocity vector of particle i at thekth iteration is represented as Xi(t)=(Xi1(t),Xi2(t),…,XiD(t)) and Vi(t)=(Vi1(t),Vi2(t),…,ViD(t)). The particle moves according to the following equations: (2)Vit+1=ωVit+c1r1Pit-Xit+c2r2Pgt-Xit,Xit+1=Xit+Vit+1,where, i=1,2,…,M, j=1,2,…,D, c1 and c2 are acceleration coefficient. r1 and r2 are random numbers distributed uniformly in (0,1). ω is inertia weight. Vector Pi=(Pi1,Pi2,…,PiD) is the previous best position of particle i (pbest), and vector Pg=(Pg1,Pg2,…,PgD) is the position of the best particle g in the swarm (gbest).


## 3.2. Quantum-Behaved Particle Swarm Optimization

The main disadvantage of PSO is that it is not guaranteed to be global convergent [16]. Concepts of QPSO were developed to address this disadvantage and first reported by Sun et al. in 2004 [5]. Trajectory analysis in [17] demonstrated the fact that the convergence of PSO may be achieved if each particle converges to its local attractor, pi=(pi1,pi2,…,piD), defined as (3)pit=φPit+1-φPgt,where φ∈(0,1). It can be seen that pi is a stochastic attractor of particle i that lies in a hyperrectangle with Pi and Pg being two ends of its diagonal and moves following Pi and Pg.In quantum world, the velocity of the particle is meaningless, so, in QPSO system, position is the only state to depict the particles, which moves according to the following equation [5]: (4)Xit+1=pit±αmbestt-Xitln⁡1u,where u is a random number uniformly distributed in (0,1) and mbest(t), called mean best position, is defined as the mean value of personal best positions of the swarm: (5)mbestt=1M∑i=1MPi=1M∑i=1MPi1t,1M∑i=1MPi2t,…,1M∑i=1MPiDt.The parameter α in (4) is named as contraction-expansion (CE) coefficient, which can be adjusted to control convergence rate. The most commonly used method to control CE is linearly decreasing from αmax to αmin: (6)α=αmax⁡-αmin⁡tmax⁡-ttmax⁡+αmin⁡,where t is the current iteration step, tmax is the predefined maximum iteration steps, and αmax and αmin are the maximum and minimum value of CE.QPSO does not require velocity vectors for the particles and has fewer parameters to control, making the algorithm easier to implement. Experimental results performed on some well-known benchmark functions show that QPSO has better performance than PSO [5–7].A great deal of efforts has been made to PSO for solving multiobjective optimization problems. A survey of state-of-the-art works is presented in [4]. The most contributive work is proposed by Ceollo et al. [3], in which the objective space is divided into hypercubes using an adaptive grid. The nondominated solutions are distributed into grids and then the grid is chosen according to a roulette wheel selection strategy. However, the grid is problems dependent and computation complicated. While in [18] a new density measure strategy named as sigma method was introduced to multiobjective PSO, so as to choose a gbest from the nondominated archive, the sigma method can guide particles to the pareto optimal front. However, if the initialized solutions in nondominated archive are bad, the algorithm will fall into local optimum due to the fast convergence. Yang et al. [19] proposed a hybrid method which combined the density information and sigma method so as to achieve a balance between global search and local search. Considering the calculation of the density value and crowding distance is limited by two objectives. When the number of objectives becomes large, the measure of density and crowding distance will become invalid. Therefore, the idea of preference order is introduced [20].


## 3.3. Preference Order

As we all know, when the optimization problem has two objectives, the pareto optimal solutions can be plotted on a curve. Though the trade-off surface can also be visualized for three objectives, it is not easy to pick the final point. For problems with more than three objectives, it becomes extremely difficult to find the optimized solution through visualization.The idea of preference order was firstly proposed in 1999 [21]. A point x∗∈Ω is said to be efficiency of order k if f(x∗) is not dominated by any of the k-element subsets of fΩ.Consider a minimization example with three objectives in Table1; combination of all subsets of the objectives is f1,f2,f3,(f1,f2),(f2,f3),(f1,f3).Table 1
Nondominated set.
Points
f
1
f
2
f
3
Point 1
0.5
2.1
11.2
Point 2
6
1.1
1.3
Point 3
3.14
0
3.76
Point 4
1.1
0.5
4.32
Point 5
3.89
0.1
3.23The dominant relation of all points in 2-element subsets is shown in Table2, from which only Point 3 is nondominated by any points on all 2-element subsets. So Point 3 is said to be efficiency of order 2.Table 2
Dominant relation.
Points
Point 1
Point 2
Point 3
Point 4
Point 5
Point 1
×
×
×
×
×
Point 2
(
f
2
,
f
3
)
×
×
×
×
Point 3
(
f
2
,
f
3
)
(
f
1
,
f
2
)
×
(
f
2
,
f
3
)
(
f
1
,
f
2
)
Point 4
(
f
2
,
f
3
)
(
f
1
,
f
2
)
×
×
(
f
1
,
f
2
)
Point 5
(
f
2
,
f
3
)
(
f
1
,
f
2
)
×
(
f
2
,
f
3
)
×About efficiency of order, [22] gave three claims.Claim 1.
In a space withn objectives, there is no more than one point with efficiency of order n-1.Claim 2.
x
∗ is efficient of order k+1, if it is efficient of order k.Claim 3.
x
∗ is not efficient of order k-1, if it is not efficient of order k.The pseudocode of QPSO with preference order is shown below.Preference-Order Based QPSO
(1)
Initialization: initialize the swarm sizeM, the external archive size ND, and the maximum number of iterations tmax, CE α. Position of each particle Xi, i=1,2,…,M, is randomly initialized. Personal best position of each particle pbesti is equal to Xi. Construct external nondominated set nds.
(2)
Update the following:
(a)
Identify global best position using preference-order method.
(i)
Get combination of all subsets forn objectives.
(ii)
Compute the efficiency order for each nondominated solution.
(iii)
Sort nondominated solutions in descending order according to their efficiency order.
(iv)
Getgbest.
(b)
Update position of each particle according to (3), (4), and (5).
(c)
Updatepbest according to dominance rule.
(d)
Update external archive and remove solution with lower efficiency order if archive sizeND is exceeded.
(e)
Updateα according to (6).
(3)
Repeat(2) until the maximum number of iterations is reached.


## 3.4. Sigma Method

The sigma method was first proposed in [18] for finding the best local guide for each particle. Each nondominated solution in the external repository is assigned a value σi, i=1,2,…,ND, which is defined as (for two objectives shown in Figure 1.) (7)σi=fi,12-fi,22fi,12+fi,22.In the general case, σ is a vector of N2 elements, and each element is the combination of two coordinates. Take a problem of three objectives; for example, (8)σi=fi,12-fi,22fi,22-fi,32fi,32-fi,12fi,12+fi,22+fi,32.Figure 1
Sigma value for a two-objective space.The pseudocode of QPSO with sigma value is shown below.QPSO with Sigma Method
(1)
Initialization: initialize the swarm sizeM, the external archive size ND, and the maximum number of iterations tmax, CE α. Position of each particle Xi, i=1,2,…,M, is randomly initialized. Personal best position of each particle pbesti is equal to Xi. Construct external nondominated set nds.
(2)
Update the following:
(a)
Identify local best position using sigma method.
(i)
Assign the valueσj to each particle in the external archive.
(ii)
Calculate the valueσi for each particle in the swarm.
(iii)
Calculate the distance betweenσi and σj.
(iv)
The particlek in the archive with σk has the minimum distance to σi selected as the best local guide for the particle i.
(b)
Update position of each particle according to (3), (4), and (5).
(c)
Updatepbest according to dominance rule.
(d)
Updateα according to (6).
(3)
Repeat
(
2
) until the maximum number of iterations is reached.


## 4.  Numerical Experiments

### 4.1. Test Functions

Seven common test functions [20–23] are used to test the proposed algorithm (DTLZ1, DTLZ2, DTLZ3, and DTLZ4), as listed in Table 3. We call k=x→N difficulty factor. Table 4 gives the difficulty factor, number of runs, number of iterations, number of particles, and size of nondominated archive used in our test. The reason why these functions are chosen is due to the following features:(1)
The relatively small implementation effort.(2)
The ability to be scaled to any number of objectives and decision variable.(3)
The global pareto front being known analytically.(4)
Convergence and diversity difficulties that can be easily controlled.Table 3
Description of the tested functions.
Name
Expression
Optimal solution
DTLZ1
min
⁡
f
x
→, x→∈Ω Ω=x→∣0≤xi≤1∀i=1,2,…,D f1x→=0.51+gx→Nx1x2⋯xN-1 f2x→=0.51+gx→Nx1x2⋯1-xN-1 ⋮ fNx→=0.51+gx→N1-x1 gx→N=100x→N+∑xi∈x→Nxi-0.52-cos⁡20πxi-0.5
x
i
=
0.5,∀i∈x→N
DTLZ2
min
⁡
f
x
→, x→∈Ω Ω=x→∣0≤xi≤1∀i=1,2,…,D f1x→=1+gx→Ncos⁡0.5πx1⋯cos⁡0.5πxN-2cos⁡0.5πxN-1 f2x→=1+gx→Ncos⁡0.5πx1⋯cos⁡0.5πxN-2sin⁡0.5πxN-1 ⋮  fNx→=1+gx→Nsin⁡0.5πx1 gx→N=∑xi∈x→Nxi-0.52
x
i
=
0.5,∀i∈x→N
DTLZ3
min
⁡
f
x
→, x→∈Ω Ω=x→∣0≤xi≤1∀i=1,2,…,D f1x→=1+gx→Ncos⁡0.5πx1⋯cos⁡0.5πxN-2cos⁡0.5πxN-1 f2x→=1+gx→Ncos⁡0.5πx1⋯cos⁡0.5πxN-2sin⁡0.5πxN-1 ⋮ fNx→=1+gx→Nsin⁡0.5πx1 gx→N=100x→N+∑xi∈x→Nxi-0.52-cos⁡20πxi-0.5
x
i
=
0.5,∀i∈x→N
DTLZ4
min
⁡
f
x
→, x→∈Ω Ω=x→∣0≤xi≤1∀i=1,2,…,D f1x→=1+gx→Ncos⁡0.5πx1α⋯cos⁡0.5πxN-2αcos⁡0.5πxN-1α f2x→=1+gx→Ncos⁡0.5πx1α⋯cos⁡0.5πxN-2αsin⁡0.5πxN-1α ⋮ fNx→=1+gx→Nsin⁡0.5πx1α gx→N=∑xi∈x→Nxi-0.52
x
i
=
0.5,∀i∈x→NTable 4
Difficulty factor, number of runs, iterations, particles, and external archive.
Name
k
Number of runs
Number of iterations
M
ND
DTLZ1
5
10
600
80
80
DTLZ2
10
10
600
80
80
DTLZ3
10
10
600
80
80
DTLZ4
10
10
600
80
80


### 4.2. Performance Metrics

Usually, pareto-based multiobjective algorithms consider two aspects: closeness to the global pareto front (distance) and spread along the pareto front (diversity) [2], which are defined as follows.Generational Distance (GD). It is a way of estimating how far the elements in the nondominated set are found so far from those in the pareto optimal set, which is defined as(9)GD=∑i=1NDdi2ND,where ND is the number of points in nondominated set and di is the Euclidean distance between a point and the nearest member of Pareto optimal set.Spacing (SP). It is a metric measuring the distance variance of neighboring points in the nondominated set, which is defined as (10)S=1n-1∑i=1NDd--di2,where di=minj∑k=1Nfki(x→)-fkj(x→),   i,j=1,2,…,ND, d- is the mean of all di, and N is the number of objectives.


### 4.3. Experiments Results

Tables5 and 6 show the mean values of generational distance and spacing for three methods (QPSO + PO, QPSO + Rand, and QPSO + Sigma) with different number of objectives (2, 3, 4, 5, 6, 7, and 8). It is easy to note that QPSO with preference order has comparative performance with sigma value. When the number of objectives is small (e.g., 2, 3, 4, and 5), QPSO with sigma value performs better. When the number of objectives becomes larger (e.g., 6, 7, and 8), QPSO with preference order obtains solutions closer to the true pareto front, but it is very time-consuming.Table 5
Mean value of generational distance.
Name
N
QPSO + PO
QPSO + Rand
QPSO + Sigma
DTLZ1
2
299.14
273.50
270
.
71
3
957.39
321.18
287
.
55
4
548.28
408.88
298
.
15
5
616.97
525.00
466
.
76
6
332
.
29
359.63
538.87
7
398
.
67
472.19
424.32
8
298
.
87
415.31
830.97
DTLZ2
2
3.8
E
-
03
3.7
E
-
03
1
.
5
E
-
03
3
1.02
E
-
02
1.22
E
-
02
4
.
9
E
-
03
4
2.76
E
-
02
3.26
E
-
02
1
.
52
E
-
02
5
6.64
E
-
02
6.55
E
-
02
4
.
48
E
-
02
6
7
.
34
E
-
02
9.54
E
-
02
7.49
E
-
02
7
9
.
65
E
-
02
0.116
0.111
8
9
.
87
E
-
02
0.128
0.117
DTLZ3
2
1
.
31
E
04
2.40
E
04
2.59
E
04
3
2.76
E
04
2.38
E
04
1
.
70
E
04
4
3.93
E
04
2.86
E
04
2
.
05
E
04
5
5.95
E
04
3.81
E
04
2
.
68
E
04
6
5.35
E
04
3.98
E
04
3
.
19
E
04
7
1
.
20
E
04
5.52
E
04
3.72
E
04
8
4
.
04
E
04
4.73
E
04
4.98
E
04
DTLZ4
2
3.98
E
-
08
2.64
E
-
14
0
3
0
1.1
E
-
03
0
4
9.74
E
-
04
1.62
E
-
09
0
5
1.38
E
-
06
2.55
E
-
05
5
.
84
E
-
18
6
2.32
E
-
02
0.17
5
.
3
E
-
03
7
7
.
11
E
-
02
0.16
0.21
8
4
.
11
E
-
02
9.09
E
-
02
1.43
E
-
01Table 6
Mean value of spacing.
Name
N
QPSO + PO
QPSO + Rand
QPSO + Sigma
DTLZ1
2
12.51
2
.
58
9.56
3
19.32
7.78
7
.
42
4
8
.
42
10.76
9.16
5
19.42
18.50
15
.
78
6
7
.
80
11.61
18.24
7
28.45
23.16
19
.
75
8
5
.
63
17.90
27.53
DTLZ2
2
0.099
0.108
0
.
098
3
0.165
0.155
0
.
148
4
0.267
0.275
0
.
225
5
0.429
0.360
0
.
305
6
0.452
0.441
0
.
425
7
0
.
436
0.461
0.477
8
0
.
332
0.569
0.438
DTLZ3
2
104.69
22.13
1
.
16
3
54.21
87.79
53
.
11
4
180.30
82
.
14
116.29
5
124.35
137.43
108
.
40
6
219.13
143.94
111
.
38
7
158
.
78
209.16
171.57
8
112
.
1
147.65
123.78
DTLZ4
2
0
1.15
0
3
0
2.79
E
-
04
0.223
4
4
.
76
E
-
04
0
0.25
5
0
0
0.23
6
4
.
5
E
-
03
0.12
1.10
7
0
.
47
1.19
1.05
8
4
.
9
E
-
03
4.81
E
-
01
9.17
E
-
01WhenN becomes larger, the number of nondominated particles in external archive ND and the number of subsets Ni(i=1,2,…,N-1) will accordingly become large. Therefore, the computing complexity of QPSO with preference order is O(N3).Furthermore, in QPSO with sigma value, each particle flies towards its nearest nondominated particle in external archive, which will easily result in a premature convergence and the particles will get trapped in a local optimum.


## 4.1. Test Functions

Seven common test functions [20–23] are used to test the proposed algorithm (DTLZ1, DTLZ2, DTLZ3, and DTLZ4), as listed in Table 3. We call k=x→N difficulty factor. Table 4 gives the difficulty factor, number of runs, number of iterations, number of particles, and size of nondominated archive used in our test. The reason why these functions are chosen is due to the following features:(1)
The relatively small implementation effort.(2)
The ability to be scaled to any number of objectives and decision variable.(3)
The global pareto front being known analytically.(4)
Convergence and diversity difficulties that can be easily controlled.Table 3
Description of the tested functions.
Name
Expression
Optimal solution
DTLZ1
min
⁡
f
x
→, x→∈Ω Ω=x→∣0≤xi≤1∀i=1,2,…,D f1x→=0.51+gx→Nx1x2⋯xN-1 f2x→=0.51+gx→Nx1x2⋯1-xN-1 ⋮ fNx→=0.51+gx→N1-x1 gx→N=100x→N+∑xi∈x→Nxi-0.52-cos⁡20πxi-0.5
x
i
=
0.5,∀i∈x→N
DTLZ2
min
⁡
f
x
→, x→∈Ω Ω=x→∣0≤xi≤1∀i=1,2,…,D f1x→=1+gx→Ncos⁡0.5πx1⋯cos⁡0.5πxN-2cos⁡0.5πxN-1 f2x→=1+gx→Ncos⁡0.5πx1⋯cos⁡0.5πxN-2sin⁡0.5πxN-1 ⋮  fNx→=1+gx→Nsin⁡0.5πx1 gx→N=∑xi∈x→Nxi-0.52
x
i
=
0.5,∀i∈x→N
DTLZ3
min
⁡
f
x
→, x→∈Ω Ω=x→∣0≤xi≤1∀i=1,2,…,D f1x→=1+gx→Ncos⁡0.5πx1⋯cos⁡0.5πxN-2cos⁡0.5πxN-1 f2x→=1+gx→Ncos⁡0.5πx1⋯cos⁡0.5πxN-2sin⁡0.5πxN-1 ⋮ fNx→=1+gx→Nsin⁡0.5πx1 gx→N=100x→N+∑xi∈x→Nxi-0.52-cos⁡20πxi-0.5
x
i
=
0.5,∀i∈x→N
DTLZ4
min
⁡
f
x
→, x→∈Ω Ω=x→∣0≤xi≤1∀i=1,2,…,D f1x→=1+gx→Ncos⁡0.5πx1α⋯cos⁡0.5πxN-2αcos⁡0.5πxN-1α f2x→=1+gx→Ncos⁡0.5πx1α⋯cos⁡0.5πxN-2αsin⁡0.5πxN-1α ⋮ fNx→=1+gx→Nsin⁡0.5πx1α gx→N=∑xi∈x→Nxi-0.52
x
i
=
0.5,∀i∈x→NTable 4
Difficulty factor, number of runs, iterations, particles, and external archive.
Name
k
Number of runs
Number of iterations
M
ND
DTLZ1
5
10
600
80
80
DTLZ2
10
10
600
80
80
DTLZ3
10
10
600
80
80
DTLZ4
10
10
600
80
80


## 4.2. Performance Metrics

Usually, pareto-based multiobjective algorithms consider two aspects: closeness to the global pareto front (distance) and spread along the pareto front (diversity) [2], which are defined as follows.Generational Distance (GD). It is a way of estimating how far the elements in the nondominated set are found so far from those in the pareto optimal set, which is defined as(9)GD=∑i=1NDdi2ND,where ND is the number of points in nondominated set and di is the Euclidean distance between a point and the nearest member of Pareto optimal set.Spacing (SP). It is a metric measuring the distance variance of neighboring points in the nondominated set, which is defined as (10)S=1n-1∑i=1NDd--di2,where di=minj∑k=1Nfki(x→)-fkj(x→),   i,j=1,2,…,ND, d- is the mean of all di, and N is the number of objectives.


## 4.3. Experiments Results

Tables5 and 6 show the mean values of generational distance and spacing for three methods (QPSO + PO, QPSO + Rand, and QPSO + Sigma) with different number of objectives (2, 3, 4, 5, 6, 7, and 8). It is easy to note that QPSO with preference order has comparative performance with sigma value. When the number of objectives is small (e.g., 2, 3, 4, and 5), QPSO with sigma value performs better. When the number of objectives becomes larger (e.g., 6, 7, and 8), QPSO with preference order obtains solutions closer to the true pareto front, but it is very time-consuming.Table 5
Mean value of generational distance.
Name
N
QPSO + PO
QPSO + Rand
QPSO + Sigma
DTLZ1
2
299.14
273.50
270
.
71
3
957.39
321.18
287
.
55
4
548.28
408.88
298
.
15
5
616.97
525.00
466
.
76
6
332
.
29
359.63
538.87
7
398
.
67
472.19
424.32
8
298
.
87
415.31
830.97
DTLZ2
2
3.8
E
-
03
3.7
E
-
03
1
.
5
E
-
03
3
1.02
E
-
02
1.22
E
-
02
4
.
9
E
-
03
4
2.76
E
-
02
3.26
E
-
02
1
.
52
E
-
02
5
6.64
E
-
02
6.55
E
-
02
4
.
48
E
-
02
6
7
.
34
E
-
02
9.54
E
-
02
7.49
E
-
02
7
9
.
65
E
-
02
0.116
0.111
8
9
.
87
E
-
02
0.128
0.117
DTLZ3
2
1
.
31
E
04
2.40
E
04
2.59
E
04
3
2.76
E
04
2.38
E
04
1
.
70
E
04
4
3.93
E
04
2.86
E
04
2
.
05
E
04
5
5.95
E
04
3.81
E
04
2
.
68
E
04
6
5.35
E
04
3.98
E
04
3
.
19
E
04
7
1
.
20
E
04
5.52
E
04
3.72
E
04
8
4
.
04
E
04
4.73
E
04
4.98
E
04
DTLZ4
2
3.98
E
-
08
2.64
E
-
14
0
3
0
1.1
E
-
03
0
4
9.74
E
-
04
1.62
E
-
09
0
5
1.38
E
-
06
2.55
E
-
05
5
.
84
E
-
18
6
2.32
E
-
02
0.17
5
.
3
E
-
03
7
7
.
11
E
-
02
0.16
0.21
8
4
.
11
E
-
02
9.09
E
-
02
1.43
E
-
01Table 6
Mean value of spacing.
Name
N
QPSO + PO
QPSO + Rand
QPSO + Sigma
DTLZ1
2
12.51
2
.
58
9.56
3
19.32
7.78
7
.
42
4
8
.
42
10.76
9.16
5
19.42
18.50
15
.
78
6
7
.
80
11.61
18.24
7
28.45
23.16
19
.
75
8
5
.
63
17.90
27.53
DTLZ2
2
0.099
0.108
0
.
098
3
0.165
0.155
0
.
148
4
0.267
0.275
0
.
225
5
0.429
0.360
0
.
305
6
0.452
0.441
0
.
425
7
0
.
436
0.461
0.477
8
0
.
332
0.569
0.438
DTLZ3
2
104.69
22.13
1
.
16
3
54.21
87.79
53
.
11
4
180.30
82
.
14
116.29
5
124.35
137.43
108
.
40
6
219.13
143.94
111
.
38
7
158
.
78
209.16
171.57
8
112
.
1
147.65
123.78
DTLZ4
2
0
1.15
0
3
0
2.79
E
-
04
0.223
4
4
.
76
E
-
04
0
0.25
5
0
0
0.23
6
4
.
5
E
-
03
0.12
1.10
7
0
.
47
1.19
1.05
8
4
.
9
E
-
03
4.81
E
-
01
9.17
E
-
01WhenN becomes larger, the number of nondominated particles in external archive ND and the number of subsets Ni(i=1,2,…,N-1) will accordingly become large. Therefore, the computing complexity of QPSO with preference order is O(N3).Furthermore, in QPSO with sigma value, each particle flies towards its nearest nondominated particle in external archive, which will easily result in a premature convergence and the particles will get trapped in a local optimum.


## 5. QPSO for Flexible Job-Shop Scheduling Problems

### 5.1. Flexible Job-Shop Scheduling Problems

The FJSP could be formulated as follows. There is a set ofn jobs and a set of m machines. M denotes the set of all machines. Each job i consists of a sequence of ni operations. Each operation Oi,j(i=1,2,…,n; j=1,2,…,ni) of job i has to be processed on one machine Mk out of a set of given compatible machines Mi,j for (Mk∈Mi,j, Mi,j⊆M). The execution of each operation requires one machine selected from a set of available machines. In addition, the FJSP needs to set each operation’s starting and ending time. The FJSP is needed to determine both an assignment and a sequence of the operations on the machines in order to satisfy the given criteria. If there is Mi,j⊂M for at least one operation, it is partial flexibility FJSP (P-FJSP); while there is Mi,j=M for each operation, it is total flexibility FJSP (T-FJSP) [10, 11].In this paper, the following criteria are to be minimized:(1)
The maximal completion time of machines, that is, the makespan.(2)
The maximal machine workload, that is, the maximum working time spent on any machine.(3)
The total workload of machines, which represents the total working time over all machines.During the process of solving this problem, the following assumptions are made:(1)
Each operation cannot be interrupted during its performance (nonpreemptive condition).(2)
Each machine can perform at most one operation at any time (resource constraint).(3)
The precedence constraints of the operations in a job can be defined for any pair of operations.(4)
Setting up time of machines and move time between operations are negligible.(5)
Machines are independent from each other.(6)
Jobs are independent from each other.(7)
All machines are available at time 0.(8)
Each job has its own release date.(9)
The order of operations for each job is predefined and invariant.The model of the multiobjective FJSP is then given as follows:(11)min⁡f1=max1≤k≤m⁡Ck(12)min⁡f2=max1≤k≤m⁡Wk(13)min⁡f3=∑k=1mWk(14)s.t.Ci,j-Ci,j-1≥Pi,j,kxi,j,k,j=1,2,…,ni,∀i,j;(15)Ch,g-th,g,k-Ci,jxh,g,kxi,j,k≥0∨Ci,j-ti,j,k-Ch,gxh,g,kxi,j,k≥0,∀i,j,h,g,k;(16)∑k∈Mi,jxi,j,k=1,∀i,j.Inequation (14) ensures the operation precedence constraint. Inequity (15) ensures that each machine could process only one operation at each time. Equation (16) states that one machine could be selected from the set of available machines for each operation.


### 5.2. Encoding Scheme

Particle’s position representation is the most important task for successful application of PSO or QPSO to solve the FJSP. In this paper, the particle’s position is represented by a vector which consists of two parts (take Table7, e.g.). The first part represents the sequence of the operations (O1,1,O2,1,O3,1,O3,2,O1,2,O1,3,O2,2,O2,3). The second part represents the machines on which the operations in Table 7 are processed; take Figure 2 for example, 1000 represents O1,1 is processed on M1 and 0001 represents O1,2 is processed on M4. The length of the vector is equal to ∑i=1nni(1+m). The advantage of this encoding method is that it is easy to apply crossover and mutation on operation part and machine part separately, while the disadvantage is the storage complexity.Table 7
Example of 3 jobs in 4 machines.
Job
Operation
M
1
M
2
M
3
M
4
J
1
O
11
1
3
4
1
O
12
3
8
2
1
O
13
3
5
4
7
J
2
O
21
4
1
1
4
O
22
2
3
9
3
O
23
9
1
2
2
J
3
O
31
8
6
3
5
O
32
4
5
8
1Figure 2
Encoding of a particle.


### 5.3. Swarm Initialization

The initial population has great influence on the performance of the algorithm. Here in this paper, a guided initialization method is used. In order to ensure the diversity of the population, 50% of the particles are initialized randomly, and the others are initialized according to the following rules.Guided InitializationStep
0:Initialize.It includes the following:(a)
Create an array for a random job order J (e.g., J4 J2 J3 J1).(b)
Assign the first operationOx,1 of each job to a suitable machine following the order O4,1O2,1O3,1O1,1. This machine is selected by calling Step 1(b); Ox,1 is assigned directly to the selected machine. If there is no operation assigned to the selected machine, Ox,1 starts from time 0. Otherwise, it starts from the stop time of the last operation on the selected machine.Step
1:Find a Suitable Machine to Process an Operation.It includes the following:(a)
Identify the machine with earliest stop time Ms and the last operationOi,j on Ms. If more than one machine is satisfied, a random machine of them is selected. Let t be the stop time of Ms.(b)
Find a suitable machine to processOi,j+1 by the following procedure:
(i)
Identify all the machines that can processOi,j+1: P(Oi,j+1).(ii)
Calculate the waiting time of each machineMk∈P(Oi,j+1): if Mk does not process any operation at time t, it is equal to processing time of Oi,j+1 on Mk. Otherwise, if it is processing an operation Oz,y, its waiting time is the total processing times of operations on Mk’s waiting list + (remaining time of Oz,y) + processing time of Oi,j+1 on machine Mk.(iii)
The machine with shortest waiting time is chosen to processOi,j+1. If this machine does not process any operation at time t, assign Oi,j+1 to it to be processed. Otherwise, add Oi,j+1 to the waiting list of this machine.Step
2:Find a Suitable Order of Operations on a Machine. from Step 1(a), Ms and Oi,j are identified, and then assign Oi,j+1 to a machine. Now an operation is needed to find on the waiting list to be processed on Ms. If there is more than one operation on the waiting list of Ms, select one of them depending on one of the following dispatching rules: shortest processing time, longest processing time, or first in first out.Step
3. Return to Step 1.


### 5.4. Crossover and Mutation

For combinational optimization problems, effective information exchanging is able to help find the better solution. The crossover operator on the operation part is shown in Figure3, in which the offspring C1 and C2 inherit some operations from the parents P1 ({1}) and P2 ({2,3}) directly, and the other operations are copied from another parent.Figure 3
Crossover on operation part.The crossover operator on the machine part is shown in Figure4, in which two positions are selected randomly, the same as that in GA.Figure 4
Crossover on machine part.The mutation of a particle is also divided into two steps; one is on operation part (Figure5), in which, two positions are randomly chosen, and the operations between them are reversed.Figure 5
Mutation on operation part.Another mutation is on machine part, but the operation to be mutated cannot be randomly chosen. Because the makespan and workload are determined by the critical path [13] in the scheduling sequence, the feasible mutation method to reduce the makespan is to choose a critical operation on the critical path, and then try to move it to another machine. Taking Figure 6, for example, the critical path is constructed by {O4,1,O2,1,O2,2,O2,3}. The operation O4,1 is moved from M1 to M4, and then the makespan is reduced from 12 to 11.Figure 6
The Gantt graph of moving operation.
(a)
(b)


### 5.5. Experimental Results

As the benchmark results analysis in Section4, QPSO with sigma value outperforms QPSO with preference order for smaller number of objectives. In this section, only three objectives are defined (makespan, max machine workload, and total workload), so QPSO with sigma value is adopted.To illustrate the performance of QPSO with sigma value, four representative examples based on practical data have been selected [8–11]: problem 4×5, problem 8×8, problem 10×10, and problem 15×10.The parameters are set as population sizeM=100; size of the external archive ND=100; dimensional size equals the total number of operations ∑i=1nni; the maximum number of iterations kmax=2000.From Table8, it is easy to notice that, for the problems of 4×5, 8×8, and 15×10, the results obtained by QPSO with sigma dominate other algorithms. For problem of 10×10, the result obtained by QPSO with sigma is not dominated by other algorithms. Therefore, QPSO with sigma value is competitive for solving multiobjective flexible job-shop scheduling problems.Table 8
Comparison of results in four problems.
Problem
Objective
AL + CGA
PSO + SA
GA
QPSO + Sigma
4
×
5
f
1
16
11
12
11
f
2
10
10
11
10
f
3
34
32
33
32
8
×
8
f
1
16
16
15
14
f
2
15
13
14
13
f
3
75
73
73
73
10
×
10
f
1
7
7
7
7
f
2
5
6
6
5
f
3
45
44
43
44
15
×
10
f
1
24
12
12
11
f
2
11
11
11
11
f
3
91
91
92
91Figures7–10 show the Gantt graph of the optimized scheduling sequence by QPSO with sigma.Figure 7
Gantt graph of problem4×5.Figure 8
Gantt graph of problem8×8.Figure 9
Gantt graph of problem10×10.Figure 10
Gantt graph of problem15×10.


## 5.1. Flexible Job-Shop Scheduling Problems

The FJSP could be formulated as follows. There is a set ofn jobs and a set of m machines. M denotes the set of all machines. Each job i consists of a sequence of ni operations. Each operation Oi,j(i=1,2,…,n; j=1,2,…,ni) of job i has to be processed on one machine Mk out of a set of given compatible machines Mi,j for (Mk∈Mi,j, Mi,j⊆M). The execution of each operation requires one machine selected from a set of available machines. In addition, the FJSP needs to set each operation’s starting and ending time. The FJSP is needed to determine both an assignment and a sequence of the operations on the machines in order to satisfy the given criteria. If there is Mi,j⊂M for at least one operation, it is partial flexibility FJSP (P-FJSP); while there is Mi,j=M for each operation, it is total flexibility FJSP (T-FJSP) [10, 11].In this paper, the following criteria are to be minimized:(1)
The maximal completion time of machines, that is, the makespan.(2)
The maximal machine workload, that is, the maximum working time spent on any machine.(3)
The total workload of machines, which represents the total working time over all machines.During the process of solving this problem, the following assumptions are made:(1)
Each operation cannot be interrupted during its performance (nonpreemptive condition).(2)
Each machine can perform at most one operation at any time (resource constraint).(3)
The precedence constraints of the operations in a job can be defined for any pair of operations.(4)
Setting up time of machines and move time between operations are negligible.(5)
Machines are independent from each other.(6)
Jobs are independent from each other.(7)
All machines are available at time 0.(8)
Each job has its own release date.(9)
The order of operations for each job is predefined and invariant.The model of the multiobjective FJSP is then given as follows:(11)min⁡f1=max1≤k≤m⁡Ck(12)min⁡f2=max1≤k≤m⁡Wk(13)min⁡f3=∑k=1mWk(14)s.t.Ci,j-Ci,j-1≥Pi,j,kxi,j,k,j=1,2,…,ni,∀i,j;(15)Ch,g-th,g,k-Ci,jxh,g,kxi,j,k≥0∨Ci,j-ti,j,k-Ch,gxh,g,kxi,j,k≥0,∀i,j,h,g,k;(16)∑k∈Mi,jxi,j,k=1,∀i,j.Inequation (14) ensures the operation precedence constraint. Inequity (15) ensures that each machine could process only one operation at each time. Equation (16) states that one machine could be selected from the set of available machines for each operation.


## 5.2. Encoding Scheme

Particle’s position representation is the most important task for successful application of PSO or QPSO to solve the FJSP. In this paper, the particle’s position is represented by a vector which consists of two parts (take Table7, e.g.). The first part represents the sequence of the operations (O1,1,O2,1,O3,1,O3,2,O1,2,O1,3,O2,2,O2,3). The second part represents the machines on which the operations in Table 7 are processed; take Figure 2 for example, 1000 represents O1,1 is processed on M1 and 0001 represents O1,2 is processed on M4. The length of the vector is equal to ∑i=1nni(1+m). The advantage of this encoding method is that it is easy to apply crossover and mutation on operation part and machine part separately, while the disadvantage is the storage complexity.Table 7
Example of 3 jobs in 4 machines.
Job
Operation
M
1
M
2
M
3
M
4
J
1
O
11
1
3
4
1
O
12
3
8
2
1
O
13
3
5
4
7
J
2
O
21
4
1
1
4
O
22
2
3
9
3
O
23
9
1
2
2
J
3
O
31
8
6
3
5
O
32
4
5
8
1Figure 2
Encoding of a particle.


## 5.3. Swarm Initialization

The initial population has great influence on the performance of the algorithm. Here in this paper, a guided initialization method is used. In order to ensure the diversity of the population, 50% of the particles are initialized randomly, and the others are initialized according to the following rules.Guided InitializationStep
0:Initialize.It includes the following:(a)
Create an array for a random job order J (e.g., J4 J2 J3 J1).(b)
Assign the first operationOx,1 of each job to a suitable machine following the order O4,1O2,1O3,1O1,1. This machine is selected by calling Step 1(b); Ox,1 is assigned directly to the selected machine. If there is no operation assigned to the selected machine, Ox,1 starts from time 0. Otherwise, it starts from the stop time of the last operation on the selected machine.Step
1:Find a Suitable Machine to Process an Operation.It includes the following:(a)
Identify the machine with earliest stop time Ms and the last operationOi,j on Ms. If more than one machine is satisfied, a random machine of them is selected. Let t be the stop time of Ms.(b)
Find a suitable machine to processOi,j+1 by the following procedure:
(i)
Identify all the machines that can processOi,j+1: P(Oi,j+1).(ii)
Calculate the waiting time of each machineMk∈P(Oi,j+1): if Mk does not process any operation at time t, it is equal to processing time of Oi,j+1 on Mk. Otherwise, if it is processing an operation Oz,y, its waiting time is the total processing times of operations on Mk’s waiting list + (remaining time of Oz,y) + processing time of Oi,j+1 on machine Mk.(iii)
The machine with shortest waiting time is chosen to processOi,j+1. If this machine does not process any operation at time t, assign Oi,j+1 to it to be processed. Otherwise, add Oi,j+1 to the waiting list of this machine.Step
2:Find a Suitable Order of Operations on a Machine. from Step 1(a), Ms and Oi,j are identified, and then assign Oi,j+1 to a machine. Now an operation is needed to find on the waiting list to be processed on Ms. If there is more than one operation on the waiting list of Ms, select one of them depending on one of the following dispatching rules: shortest processing time, longest processing time, or first in first out.Step
3. Return to Step 1.


## 5.4. Crossover and Mutation

For combinational optimization problems, effective information exchanging is able to help find the better solution. The crossover operator on the operation part is shown in Figure3, in which the offspring C1 and C2 inherit some operations from the parents P1 ({1}) and P2 ({2,3}) directly, and the other operations are copied from another parent.Figure 3
Crossover on operation part.The crossover operator on the machine part is shown in Figure4, in which two positions are selected randomly, the same as that in GA.Figure 4
Crossover on machine part.The mutation of a particle is also divided into two steps; one is on operation part (Figure5), in which, two positions are randomly chosen, and the operations between them are reversed.Figure 5
Mutation on operation part.Another mutation is on machine part, but the operation to be mutated cannot be randomly chosen. Because the makespan and workload are determined by the critical path [13] in the scheduling sequence, the feasible mutation method to reduce the makespan is to choose a critical operation on the critical path, and then try to move it to another machine. Taking Figure 6, for example, the critical path is constructed by {O4,1,O2,1,O2,2,O2,3}. The operation O4,1 is moved from M1 to M4, and then the makespan is reduced from 12 to 11.Figure 6
The Gantt graph of moving operation.
(a)
(b)


## 5.5. Experimental Results

As the benchmark results analysis in Section4, QPSO with sigma value outperforms QPSO with preference order for smaller number of objectives. In this section, only three objectives are defined (makespan, max machine workload, and total workload), so QPSO with sigma value is adopted.To illustrate the performance of QPSO with sigma value, four representative examples based on practical data have been selected [8–11]: problem 4×5, problem 8×8, problem 10×10, and problem 15×10.The parameters are set as population sizeM=100; size of the external archive ND=100; dimensional size equals the total number of operations ∑i=1nni; the maximum number of iterations kmax=2000.From Table8, it is easy to notice that, for the problems of 4×5, 8×8, and 15×10, the results obtained by QPSO with sigma dominate other algorithms. For problem of 10×10, the result obtained by QPSO with sigma is not dominated by other algorithms. Therefore, QPSO with sigma value is competitive for solving multiobjective flexible job-shop scheduling problems.Table 8
Comparison of results in four problems.
Problem
Objective
AL + CGA
PSO + SA
GA
QPSO + Sigma
4
×
5
f
1
16
11
12
11
f
2
10
10
11
10
f
3
34
32
33
32
8
×
8
f
1
16
16
15
14
f
2
15
13
14
13
f
3
75
73
73
73
10
×
10
f
1
7
7
7
7
f
2
5
6
6
5
f
3
45
44
43
44
15
×
10
f
1
24
12
12
11
f
2
11
11
11
11
f
3
91
91
92
91Figures7–10 show the Gantt graph of the optimized scheduling sequence by QPSO with sigma.Figure 7
Gantt graph of problem4×5.Figure 8
Gantt graph of problem8×8.Figure 9
Gantt graph of problem10×10.Figure 10
Gantt graph of problem15×10.


## 6. Conclusion and Future Works

In this paper, QPSO with three elitist selection strategies are used to solve multiobjective optimization problems. The results show that QPSO with preference order has comparative performance with sigma value. When the number of objectives is small (e.g., 2, 3, 4, and 5), QPSO with sigma value performs better. However, when the number of objectives becomes larger (e.g., 6, 7, and 8), QPSO with preference order obtains solutions closer to the true pareto front but is very time-consuming. Therefore, in the future work, we will try to combine these two methods to achieve a balance between global search and local search.Moreover, we apply QPSO with sigma value to solve multiobjective flexible job-shop scheduling problems, the results of which demonstrate the competitive performance of the algorithm.



---

*Source: 940592-2015-08-10.xml*