第1页 / 共22页
第2页 / 共22页
第3页 / 共22页
第4页 / 共22页
第5页 / 共22页
第6页 / 共22页
第7页 / 共22页
第8页 / 共22页
改进的NSGA-II算法解决多目标地流流水车间调度问题.pdf
Abstract
1. Introduction
2. LSFS scheduling problem
3. The proposed NSGA-II algorithm
3.1 Initialising population
3.2 Generate the offspring
3.2.1 EDA
3.2.2 Mutation
3.3 Environmental selection
3.4 Restart strategy
3.5 Summarising the proposed algorithm
4. Evolution metric
4.1 The number of non-dominated solutions, N(Sj)N({S_j})
4.2 The ratio of non-dominated solutions, R(Sj)R({S_j})
4.3 The average distance between the Pareto-optimal front and solution set Sj{S_j}
4.4 The spread of non-dominated solutions
5. Experiments
5.1 Experimental setting
5.2 Experimental results
5.2.1 Performance of initialisation strategies
5.2.2 Performance of proposed mutation operator
5.2.3 Performance of INSGA-II, NSGA-II, DHS and TA algorithms
5.2.4 Wilcoxon two-sided rank sum test
5.2.5 Sensitivity study on parameter pc
6. Conclusions
Funding
References
This article was downloaded by: [yuyan han]
On: 05 May 2014, At: 05:34
Publisher: Taylor & Francis
Informa Ltd Registered in England and Wales Registered Number: 1072954 Registered office: Mortimer House,
37-41 Mortimer Street, London W1T 3JH, UK
International Journal of Production Research
Publication details, including instructions for authors and subscription information:
http://www.tandfonline.com/loi/tprs20
An improved NSGA-II algorithm for multi-objective lot-
streaming flow shop scheduling problem
Yu-Yan Hana, Dun-wei Gonga, Xiao-Yan Suna & Quan-Ke Panb
a School of Information and Electrical Engineering, China University of Mining and
Technology, Xuzhou, China;
b School of Computer Science, Liaocheng University, Liaocheng, China
Published online: 22 Oct 2013.
To cite this article: Yu-Yan Han, Dun-wei Gong, Xiao-Yan Sun & Quan-Ke Pan (2014) An improved NSGA-II algorithm for multi-
objective lot-streaming flow shop scheduling problem, International Journal of Production Research, 52:8, 2211-2231, DOI:
10.1080/00207543.2013.848492
To link to this article: http://dx.doi.org/10.1080/00207543.2013.848492
PLEASE SCROLL DOWN FOR ARTICLE
Taylor & Francis makes every effort to ensure the accuracy of all the information (the “Content”) contained
in the publications on our platform. However, Taylor & Francis, our agents, and our licensors make no
representations or warranties whatsoever as to the accuracy, completeness, or suitability for any purpose of the
Content. Any opinions and views expressed in this publication are the opinions and views of the authors, and
are not the views of or endorsed by Taylor & Francis. The accuracy of the Content should not be relied upon and
should be independently verified with primary sources of information. Taylor and Francis shall not be liable for
any losses, actions, claims, proceedings, demands, costs, expenses, damages, and other liabilities whatsoever
or howsoever caused arising directly or indirectly in connection with, in relation to or arising out of the use of
the Content.
This article may be used for research, teaching, and private study purposes. Any substantial or systematic
reproduction, redistribution, reselling, loan, sub-licensing, systematic supply, or distribution in any
form to anyone is expressly forbidden. Terms & Conditions of access and use can be found at http://
www.tandfonline.com/page/terms-and-conditions
International Journal of Production Research, 2014
Vol. 52, No. 8, 2211–2231, http://dx.doi.org/10.1080/00207543.2013.848492
An improved NSGA-II algorithm for multi-objective lot-streaming flow shop
scheduling problem
Yu-Yan Hana, Dun-wei Gonga*, Xiao-Yan Suna and Quan-Ke Panb
aSchool of Information and Electrical Engineering, China University of Mining and Technology, Xuzhou, China; bSchool of
Computer Science, Liaocheng University, Liaocheng, China
(Received 7 May 2013; accepted 19 September 2013)
Crossover and mutation operators in NSGA-II are random and aimless, and encounter difficulties in generating offspring
with high quality. Aiming to overcoming these drawbacks, we proposed an improved NSGA-II algorithm (INSGA-II)
and applied it to solve the lot-streaming flow shop scheduling problem with four criteria. We first presented four variants
of NEH heuristic to generate the initial population, and then incorporated the estimation of distribution algorithm and a
mutation operator based on insertion and swap into NSGA-II to replace traditional crossover and mutation operators.
Last but not least, we performed a simple and efficient restarting strategy on the population when the diversity of the
population is smaller than a given threshold. We conducted a serial of experiments, and the experimental results demon-
strate that the proposed algorithm outperforms the comparative algorithms.
Keywords: NSGA-II; lot-streaming flow shop; multi-objective optimisation; heuristic rule; estimation of distribution
algorithm; restarting strategy
1. Introduction
The lot-streaming flow shop (LSFS) scheduling problem, one representative branch of traditional flow shop schedule
problems, is a simplified model of various real schedule problems, such as manufacturing systems, assembly lines, infor-
mation service facilities, as well as chemical, textile, plastics and semiconductor industries (Pan, Pan, and Sang 2010).
The main goal of the LSFS scheduling problem is to determine either the best allocation of sub-lots or the size of each
sub-lot so as to minimise some given performance measures. Thus, developing effective and efficient methods to solve
the above problems is of significance in theory and applications (Pan and Ruiz 2012). Different from traditional flow
shops, LSFS splits a given job into several sub-lots, and each is transferred to the downstream machine after it is com-
pleted in the current one, thereby reducing the production cycle and waiting time, accelerating the manufacturing pro-
cess and enhancing the production efficiency.
In the development of solving LSFS scheduling problem with single objective, efforts of some significant research
of meta-heuristics have been made, such as genetic algorithm (GA), harmony search (HS), artificial bee colony (n) and
estimation of distribution algorithm (EDA). Defersha and Chen (2012) proposed a method for solving the flexible LSFS
scheduling problem with several jobs in multi-stage consisting of unrelated parallel machines. In this work, the authors
constructed a mathematical model using integer programming and designed a parallel GA to solve the above model.
The experimental results showed that the parallel implementation extremely improved the computational performance.
Kim and Jeong (2009) presented an adaptive GA for the flexible LSFS scheduling with no-wait. In this study, the
authors adopted four methods, that is, position-based crossover, local search-based mutation, iterative hill-climbing and
adaptive regulation of GA parameters to improve the algorithm’s performance, and the experimental results showed the
proposed algorithm outperformed other GAs. Pan et al. (2010) designed a novel discrete HS algorithm for scheduling
LSFS to minimise the makespan objective. To improve the algorithm’s exploitation ability, the authors applied a local
search into discrete HS algorithm, and the effectiveness and efficiency of the proposed algorithm were demonstrated by
comparing with the existing composite ones, GA, ant colony optimisation (ACO) and the threshold accepting (TA)
algorithm. Karaboga (2005) firstly proposed the ABC algorithm for continuous function optimisation. Given the above
algorithm is of simple structure, strong convergence, more and more researchers have applied it to solve the flow shop
scheduling problem. Lei and Guo (2013) adopted a modified ABC algorithm to solving the job shop with LSFS
*Corresponding author. Email: dwgong@vip.163.com
© 2013 Taylor & Francis
Downloaded by [yuyan han] at 05:34 05 May 2014
2212
Y.-Y. Han et al.
scheduling problem. In this work, employed and onlooker bees adopted the swap and insertion operators to produce
new solutions, and the proposed algorithm adopted the elite solution to replace with the worst ones without considering
the scouts. Recently, Pan and Ruiz (2012) developed an EDA for the LSFS problem with sequence-dependent set-up
time. The experimental results showed that the proposed EDA was more effective than discrete ABC algorithm (Pan
et al. 2011), ACO (Marimulthu, Ponnambalam, and Jawahar 2009), discrete particle swarm optimisation (Tseng and
Liao 2008) and hybrid GA (Yoon and Ventura 2002).
However, production managers concern not only the scheduling problem with only one objective, but also the one
with several objectives, such as makespan, tardiness time, earliness time, the total flow time and idle time of machines
in various real-world applications. LSFS with single objective is insufficient; thus, multi-objective LSFS plays a key role
in practical scheduling problems (Zhang et al. 2010). The well-known NSGA-II algorithm, firstly presented by Deb
(2000), is one of effective evolutionary algorithms for multi-objective optimisation problems whose three main operators
are fast non-dominated sorting, fast crowded distance estimation and simple crowded-based comparison Deb et al.
(2002). In the light of its simplicity, good convergence and diversity, NSGA-II has caused much attention and a wide
range of successful applications, such as customer churn prediction in telecommunications (Huang, Buckley, and
Kechadi 2010), expansion planning (Murugan, Kannan, and Baskar 2009), economic and emission dispatch (Dha-
nalakshmi et al. 2011), estimation of prediction intervals of scale deposition rate in oil and gas equipments (Ronay et al.
2013), shape optimisation of axisymmetric cavitators in supercavitating flows (Shafaghat et al. 2011) and flow shop
scheduling problems (Tseng and Liao 2008). The existing NSGA-II for solving the flow shop scheduling problems is
commonly improved through modifying the non-dominated sorting or selection strategy. Zhang et al. (2010) designed
an improved non-dominated sorting NSGA-II for the multi-objective flexible job shop scheduling problem, which is
effective when both the rank and the crowed distance of the current two individuals are equal. Liu and Huang (2013)
developed a new pre-selection method to obtain the minimal overall outsourcing cost and supply risk probability, which
reduces the probability of design change at the stage of product production. However, the above algorithms did not con-
sider the modification of the crossover and mutation operators, which guide the population towards the Pareto front, and
thus decrease their effectiveness. In addition, to the best of our knowledge, there is few published work dealing with the
multi-objective flow shop scheduling problem, especially the LSFS one, by using NSGA-II. So, it is considerably neces-
sary to design an improved NSGA-II for the multi-objective LSFS problem.
EDA proposed by Muhlenbein and Paass (1996) has been widely studied by experts in evolutionary computation
(Jarboui, Eddaly, and Siarry 2009). Because of its effectiveness, the EDA has been successfully applied to solve the per-
mutation flow shop scheduling problem (Jarboui, Eddaly, and Siarry 2009; Zhang and Li 2011), the global continuous
optimisation problem (Sun, Zhang, and Edward 2005), the nurse scheduling problem (Aickelin and Li 2007), LSFS
problems (Pan and Ruiz 2012) and so on. The basic EDA mainly includes the following four steps (Larraaga and
Lozano 2002). First, select PS promising solutions from the original population according to their fitness and then put
them into a candidate population, ½gi;jPSn. Second, build a probability distribution model, ½ni;jnn, based on the above
population. Third, generate a new offspring, pnew, through learning and sampling from the constructed probabilistic
model, and evaluate its fitness. Last, update the original population as follows: if pnew is better than the worst one of
the original population, denoted as pw, then replace pw with pnew. In the multi-objective LSFS scheduling problem,
EDA can take full advantage of valuable information of non-dominated solutions to construct a probabilistic model and
then estimate the probability distribution of good chromosomes to generate promising offspring. So, we embedded EDA
into NSGA-II instead of traditional crossover operator so as to lead the population towards the Pareto-optimal front.
Due to the LSFS problem has such characteristics as constraint conditions, dynamic nature, large scale, complex
computation, studies on the LSFS problem with multiple objectives are relatively less than the one with single objective.
Several objectives must be simultaneously considered in practical problems; therefore, it is necessary to design an
algorithm for the LSFS scheduling problem with four objectives. Three main contributions of the proposed algorithm
are drawn. First, the variants of NEH (Nawaz, Enscore, and Ham 1983) heuristics are adopted to construct four initial
individuals with good performance Secondly, EDA is embedded in the NSGA-II algorithm to generate good offspring.
Finally, the restart strategy is employed to avoid the proposed algorithm trapping in local optima.
The rest of this paper is organised as follows. After this brief introduction, in Section 2, the LSFS scheduling
problem is stated. Section 3 describes the proposed algorithm. In Section 4, the evolutionary metrics are introduced, and
the experimental results are provided in Section 5. Finally, the paper ends with some conclusions in Section 6.
2. LSFS scheduling problem
are nðp ¼
The LSFS scheduling problem can be
fpð1Þ; pð2Þ; . . .; pðnÞgÞ jobs and m machines. Each job pðiÞ 2 p is processed on each of m machines in the same series.
(Pan and Ruiz 2012). There
formulated as
follows
Downloaded by [yuyan han] at 05:34 05 May 2014
Illustration of notations.
Table 1.
pðiÞ
pj
m
lpðiÞ
e
ppðiÞ;t
p0e; t
CpðiÞ;t;e
SpðiÞ;t;e
di
f1
f2
f3
f4
International Journal of Production Research
2213
The ith job of sequence p with jobs being indexed by i ¼ 1; 2; . . .; n
The jth job sequence or the jth individual with job sequences being indexed by j ¼ 1; 2; . . .; PS
The total number of machines with each being indexed by t ¼ 1; 2; . . .; m
The total number of sub-lots of job pðiÞ
The eth sub-lot with each being indexed by e ¼ 1; 2; . . .; lpðiÞ
The processing time of job i on machine t (t 2 f1; 2; . . .; mg)
The processing time of the eth sub-lot on machine t
The completion time of the eth sub-lot of job i on machines t
The start time of the eth sub-lot of job i on machines t
The due date of job i
Makespan
The total flow time
The idle time of all machines
The earliness time
Each job can be split into several sub-lots, and each sub-lot has different processing time on different machines. The
constraints of the LSFS scheduling problem can be described below. (1) The job can be processed at the jth machine
only when all sub-lots of the forgoing job are completed at the machine; (2) At any time, each machine can process at
most one sub-lot, and each sub-lot can be processed on at most one machine at the same time; (3) All sub-lots of the
same job pðiÞ 2 p should be continuously processed. Any two adjacent sub-lots of job j allow idle time at the same
stage. Both the set-up time and the sub-lot transportation time are included in the processing time. In order to clearly
describe the LSFS scheduling problem and well explain the mathematical model, Table 1 illustrates the meaning of all
notations.
Figure 1 shows a Gantt comparison between traditional flow shop and LSFS with 2 jobs and 3 machines. Suppose
that jobs 1 and 2 contain 3 and 2 sub-lots, respectively, and the processing time of each sub-lot is as follows.
3
5
i
h
P0
e;t
23
¼ p0
1;1
p0
2;1
¼ 1 5
1 5
2
2
p0
1;2
p0
2;2
p0
1;3
p0
2;3
2
4
i
h
P0
e;t
¼
33
3
5 ¼
2
4
2
2
2
4
4
4
3
3
3
p0
1;1
p0
2;1
p0
3;1
p0
1;2
p0
2;2
p0
3;2
p0
1;3
p0
2;3
p0
3;3
As shown in Figure 1, the process of traditional flow shop scheduling problem is illustrated by an instance with two
jobs and three machines with their job processing time of {6, 12, 9} and {2, 10, 4}, respectively. If none of these jobs
is split into sub-lots, the completion time will be 32. Whereas, when each of these jobs is split into some sub-lots of
equal size, the completion time is reduced to 26. Thus, in this example, lot-streaming can reduce the manufacturing time
by about 19%.
While evaluating the performance of the LSFS scheduling problem, a manager often considers the following four
objectives, that is, the makespan, the total flow time, idle time of all machines and the earliness time. The makespan
intuitively reflects the completion time produced by different schedulings under some constraints. The total flow time
Figure 1. Gantt comparison between traditional flow shop and LSFS.
Downloaded by [yuyan han] at 05:34 05 May 2014
2214
Y.-Y. Han et al.
Figure 2. Computation of makespan, idle time and total flow time.
embodies the strict requirement for the whole flow time of all jobs, whereas the earliness time expresses the user require-
ment for ahead of schedule. The idle time reflects whether the machines can take full advantage of resource or not.
Hence, in view of practical production, this study formulates the LSFS scheduling problem as an optimisation one
with the above four objectives. These objectives can be calculated as follows, and a Gantt for calculating the makespan,
the total flow time and idle time is illustrated in Figure 2.
Let a job permutation p ¼ fpð1Þ; pð2Þ; . . .; pðnÞg represent the sequence of jobs to be processed, and the start time
of the first sub-lot of the first job on the first machine be equal to zero, that is, Spð1Þ;1;1 ¼ 0.
Spð1Þ;1;1 ¼ 0
Cpð1Þ;1;1 ¼ Spð1Þ;1;1 þ ppð1Þ;1
Spð1Þ;t;1 ¼ Cpð1Þ;t 1;1
Cpð1Þ;t;1 ¼ Spð1Þ;t;1 þ ppð1Þ;t
t ¼ 2; 3; . . .; m
Spð1Þ;1;e ¼ Cpð1Þ;1;e 1
Cpð1Þ;1;e ¼ Spð1Þ;1;e þ ppð1Þ;1
e ¼ 2; 3; . . .; lpð1Þ
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
8<
:
Spð1Þ;t;e ¼ maxfCpð1Þ;t 1;e; Cpð1Þ;t;e 1g
Cpð1Þ;t;e ¼ Spð1Þ;t;e þ ppð1Þ;t
e ¼ 2; 3; . . .; lpð1Þ; t ¼ 2; 3; . . .; m
SpðiÞ;1;1 ¼ Cpði 1Þ;1;lpði 1Þ
CpðiÞ;1;1 ¼ SpðiÞ;1;1 þ ppð1Þ;1
i ¼ 2,3,. . .; n
SpðiÞ;t;1 ¼ maxfCpðiÞ;t 1;1; Cpði 1Þ;t;lpði 1Þg
CpðiÞ;t;1 ¼ SpðiÞ;t;1 þ ppðiÞ;t
i ¼ 2; 3; . . .; n; t ¼ 2; 3; . . .; m
SpðiÞ;1;e ¼ CpðiÞ;1;e 1
CpðiÞ;1;e ¼ SpðiÞ;1;e þ ppðiÞ;1
i ¼ 2; 3; . . .; n; e ¼ 2; 3; . . .; lpðiÞ
SpðiÞ;t;e ¼ maxfCpðiÞ;t 1;e; CpðiÞ;t;e 1g
CpðiÞ;t;e ¼ SpðiÞ;t;e þ ppðiÞ;t
i ¼ 2; 3; . . .; n; e ¼ 2; 3; . . .; lpðiÞ; t ¼ 2; 3; . . .; m
!
min f 1ðpÞ ¼ min CmaxðpÞ
Xm
CpðnÞ;t;lpðnÞ
Þ ¼ CpðnÞ;m;lpðnÞ
Xn
XlpðiÞ
ð
ppðiÞ;t
i¼1
l 1
min f2ðpÞ ¼ min IdlemaxðpÞ
ð
Þ ¼
t¼1
Downloaded by [yuyan han] at 05:34 05 May 2014
International Journal of Production Research
min f3ðpÞ ¼ min TFTmaxðpÞ
ð
min f4ðpÞ ¼ max 0; di CpðiÞ;m;lpðiÞ
Xn
Þ ¼ TFT1 þ TFT2 ¼
i¼1
CpðiÞ;m;lpðiÞ
2215
(11)
(12)
Figure 3. Flowchart of the proposed algorithm.
Figure 4. Pseudo code of the initializing population.
Downloaded by [yuyan han] at 05:34 05 May 2014
2216
Y.-Y. Han et al.
for i = 1 to PS
if( rand() < pc )
Perform EDA to generate the offspring
else
Take out a parent individual and perform the mutation operation based on the insertion and
swap operators
end if
end for
Figure 5. Pseudo code of the generating offspring.
3. The proposed NSGA-II algorithm
Although individuals comparison, non-dominated sorting and selection operator of the exiting NSGA-II algorithms for
multi-objective flow shop problem have been modified and showed the superiority to generate a good offspring, two
critical operators, that is, crossover and mutation, have not been further researched. Traditional crossover and mutation
operators are of randomness and aimlessness and cannot guarantee to generate offspring with a high quality, which
reduces the convergence rate and influences the algorithm’s efficiency. Therefore, an improved NSGA-II algorithm
imbedding EDA is adopted in this paper to enhance the diversity, speed up the convergence of the population and to
seek for a Pareto-optimal set U to minimise the above four objectives in the LSFS scheduling problem. The flowchart
of the proposed algorithm is illustrated in Figure 3, and its detailed process is stated as follows.
3.1 Initialising population
Good seeds can generate candidates of the optimisation problem with high quality, which improves the efficiency of the
whole algorithm. A rapid convergence can be obtained if a candidate makes one of the objectives minimal in an initial
population for solving the multi-objective optimisation problem. Therefore, the above idea is employed in this study,
that is, four variants of well-known NEH heuristics, called vNEH, are adopted to minimise makespan, the total flow
time, the idle time of machines and the earliness time, respectively. It is worth noting that candidates in the proposed
algorithm are represented as discrete job permutations. Let PS be the population size. Four solutions, p1; p2; p3; p4, can
be yielded by performing the proposed vNEH, and the rest PS-4 individuals in the search space are randomly generated.
The details of vNEH are stated in Figure 4.
To simply illustrate the aforementioned steps, an example for generating good seeds is given here. Suppose that
there are six jobs, denoted as pðiÞ ¼ i; i ¼ f1; 2; . . .; 6g, whose numbers of associated sub-lots are f6; 5; 6; 3; 6; 6g,
respectively. These jobs are processed on three machines, and their processing time is f12; 8; 9g, f29; 1; 26g,
f23; 12; 28g, f14; 31; 24g, f16; 7; 10g and f6; 29; 4g, respectively.
(1) The total processing time of each job can be calculated as f169; 318; 353; 238; 216; 364g according to
Equations (1)–(8); then, the sequence in the descendant order is p ¼ f6; 3; 2; 4; 5; 1g.
(2) The first two jobs in p, that is, 6 and 3, are first taken; and their two possible permutations, that is, {3, 6} and
{6, 3}, are evaluated with the first objective, named makespan, as f1ðf3; 6gÞ ¼ 328, f 1(f6, 3g) = 360. The
subsequence with a smaller makespan is selected as the current sequence, p, and therefore, p ¼ f3; 6g.
(3) Let k = 3, the third job in p, that is, 2, is taken and three possible permutations, that is, f2; 3; 6g, f3; 2; 6g
f 1ðf3; 2; 6gÞ ¼ 467
and
and
f1ðf3; 6; 2gÞ ¼ 458, and the best subsequence is chosen as the current one, p, and therefore, p ¼ f3; 6; 2g:
p ¼
(4) Similarly, the rest jobs are yielded as follows:
f 1ðf2; 3; 6gÞ ¼ 473,
Þ ¼ 500; f1 f3; 4; 6; 2g
Þ ¼ 553; f1 f3; 6; 4; 2g
Þ ¼ 571; f1 f3; 6; 2; 4g
f1 f4; 3; 6; 2g
ð
evaluated with
f3; 6; 2g,
Þ ¼ 530.
objective
k = 4,
are
f1
as
ð
ð
f1({4, 3, 5, 6, 2}) = 591,
f1({4, 3, 6, 5, 2}) = 563,
f1({5, 4, 3, 6, 2}) = 596,
f4; 3; 6; 2g;
k = 5,
f1({4, 3, 6, 2, 5}) = 560, p ¼ f4; 3; 6; 2; 5g;
618, f1({4, 3, 6, 2, 1, 5}) = 614, f1({4, 3, 6, 2, 5, 1}) = 614, p ¼ f4; 3; 6; 2; 1; 5g;
p ¼ f4; 3; 6; 2; 1; 5g.
f1({4, 1, 3, 6, 2, 5}) = 632,
f1({1, 4, 3, 6, 2, 5}) = 632,
f1({4, 5, 3, 6, 2}) = 596,
sequence with the
complete
Lastly,
k = 6,
the
smallest makespan is obtained,
f1({4, 3, 1, 6, 2, 5}) = 628,
ð
f1({4, 3, 6, 1, 2, 5}) =
and therefore, p1 ¼
Downloaded by [yuyan han] at 05:34 05 May 2014
International Journal of Production Research
2217
(5) Set j = 2, 3, 4, respectively. The rest good seeds with the smallest total flow time, the idle time and the
is, p2 ¼ f6; 5; 1; 3; 4; 2g, p3 ¼ f4; 1; 5; 3; 6; 2g and
are generated,
respectively,
earliness
p4 ¼ f4; 1; 5; 2; 3; 6g.
time
that
3.2 Generate the offspring
Crossover and mutation operators play an important role, whose contribution is that the offspring inherits from the
excellent farther chromosomes. Due to the multi-objective optimisation problem has many non-dominated solutions with
a high quality, taking full advantage of the valuable information of non-dominated solutions will lead the population
towards the Pareto-optimal front. The merit of EDA lies in that
it can utilise the information of non-dominated
solutions to construct a probabilistic model and then estimate the probability distribution of good chromosomes to build
M offspring. To this end, EDA is adopted to generate offspring instead of the traditional crossover operator in this
paper.
In addition, Insertion, swap and inverse operators are commonly used to produce a promising neighbouring solution,
which can enhance the exploitation of an algorithm by slightly disturbing the current solution. Given the insertion and
swap operators are superior to the inverse one (Wang and Zheng 2003), the former two are considered as the mutation
operators in this paper. The detailed process is illustrated in Section 3.2.2.
To sum up, in the light of the performance of EDA in exploration and that of the insertion and swap operators in
exploitation, EDA with the probability of pc and the insert and swap operators with 1 – pc probability are employed to
generate the offspring, with the purpose of leading the population towards the Pareto-optimal front during the evolution.
The general framework of generating the offspring is given as follows (Figure 5).
3.2.1 EDA
The detailed description of EDA for LSFS scheduling problem is given as follows (Pan and Ruiz 2012):
Select PS promising solutions to put into the candidate population ½gi;jPSn. All non-dominated solutions obtained at
each iteration are considered as the candidate individuals. If the number of non-dominated solutions, Q, is equal to PS,
then put all these non-dominated solutions into ½gi;jPSn; if Q is less than PS, then the rest PS – Q individuals are
selected by using tournament selection with size 2 to conduct the candidate population as well as Q non-dominated
solutions.
Build a probabilistic model ½ni;jnn whose aim is to improve the algorithm’s efficiency and effectiveness for optimis-
ing the LSFS scheduling problem (Pan and Ruiz 2012). The probabilistic model obtained by Han et al. (2012) is
Figure 6. Pseudo code of the generating elements of two matrixes.
Downloaded by [yuyan han] at 05:34 05 May 2014
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
