232
Y.
Han
et
al.
/
Applied
Soft
Computing
42
(2016)
229–245
Fig.
1.
The
flowchart
of
the
proposed
algorithm.
strategy
for
multi-objective
optimization
has
been
proposed
that
uses
the
ideal
point
for
selecting
solutions
generated
by
mutation
operators.
The
main
steps
of
the
proposed
evolutionary
optimization
algo-
rithm
are
as
follows:
Step
1:
Set
the
values
of
the
parameters.
Step
2:
Initialize
the
population
using
solutions
generated
by
the
heuristic
and
random
method.
Step
3:
Evaluate
the
initial
solutions
and
put
all
the
non-dominated
solutions
into
the
external
archive.
Step
4:
Repeat
the
following
steps,
until
the
termination
condition
has
been
fulfilled.
Step
4.1:
Generate
a
temporary
population
by
employing
a
crossover
operator
that
can
utilize
valuable
information
provided
by
both
non-dominated
solutions
and
the
differences
among
parents;
Step
4.2:
Mutate
the
temporary
population
using
the
insert
and
swap
operators
proposed
in
[2];
Step
4.3:
Choose
solutions
with
a
certain
probability
from
the
temporary
population,
keep
the
better
ones
based
on
their
distances
to
the
ideal
point;
Step
4.4:
Merge
the
temporary
population
with
the
parent
populations
into
a
combined
population,
per-
form
non-dominated
sorting
and
calculate
the
crowding
distance.
Select
the
better
individuals
based
on
the
Pareto
dominance
and
the
crowded
distance
to
form
the
parent
population
of
the
next
generation
in
which
all
the
non-dominated
solutions
are
used
to
dynamically
update
the
external
archive.
Refer
to
[24]
for
details
about
non-dominated
sorting
and
crowding
distance
calculation.
Fig.
1
provides
a
flowchart
of
the
proposed
algorithm
in
which
the
three
new
components
are
highlighted.
The
details
of
these
strategies
are
described
in
the
following
subsections.
3.1.
Population
initialization
The
combination
of
MM
(MinMax)
with
NEH
(Nawaz,
Enscore
and
Ham),
termed
MME,
proposed
by
Ronconi
et
al.
is
often
used
for
population
initialization
when
solving
a
scheduling
problem
using
meta-heuristics,
with
the
purpose
of
reducing
blocking
time
of
a
job
on
machines
by
utilizing
the
shortest
critical
path.
MME
has
shown
to
perform
better
than
other
heuristics
when
optimizing
makespan
of
a
blocking
flow
shop
scheduling
problem
[25].
To
efficiently
pro-
duce
multiple
solutions
for
the
multi-objective
scheduling
problem
considered
in
this
study,
a
variant
of
MME,
denoted
as
vMME,
is
designed
to
generate
individuals
for
initializing
a
part
of
the
population.
To
maintain
the
diversity
of
the
population,
the
rest
individuals
are
randomly
generated
in
the
neighborhood
of
these
individuals.
The
following
algorithm
shows
the
detailed
steps
of
vMME,
in
which
p
(j),t
is
the
average
sample
value
of
process
time
of
job
(j)
on
machine
t.
Algorithm
1.
The
vMME
heuristic
Input:
the
number
of
jobs,
n;
a
unscheduled
sequence
S,
S
=
{1,
2,
.
.
.,
n}.
Output:
num
non-dominated
solutions.
1:
Set
=
∅,
*
=
∅;
2:
Set
(1)
=
arg
min
(j)
∈
S
p
(j),1
;
S
=
S
\
(1);
3:
Set
(n)
=
arg
min
(j)
∈
S
p
(j),m
;
S
=
S
\
(n);
4:
k
=
2;
5:
while
k
<
n
do
6:
Compute
(j)
=
ϕ
m−1
t=1
|p
(j),t
−
p
(k−1),t+1
|
+
(1
−
ϕ)
m
q=1
p
(j),q
,
(j)
∈
S
7:
Set
(k)
=
arg
min
(j)
∈
S
(j)
8:
S
=
S
\
(k);
9:
k
=
k
+
1;
10:
end
while
11:
Pick
the
first
2
jobs
of
;
form
two
subsequences,
i.e.
1
=
{(1),
(2)}
and
2
=
{(2),
(1)},
and
select
the
one
with
the
minimal
value
of
0.5
*
F
1
+
0.5
*
F
2
as
the
current
sequence,
*;
12:
Set
k
=
3;
13:
while
k
≤
n
−
1
do
14:
Pick
the
kth
job
from
,
obtain
k
subsequences
by
inserting
it
into
the
current
sequence,
*,
at
k
possible
positions,
and
select
the
subsequence
with
the
minimal
value
of
0.5
*
F
1
+
0.5
*
F
2
as
the
current
sequence,
*.
15:
k
=
k
+
1;
16:
end
while
17:
/*There
is
no
following
statements
for
MME.*/
18:
Insert
(n)
into
the
current
sequence
*
at
n
possible
positions,
simultaneously
evaluate
two
objectives,
F
1
and
F
2
.
Denote
the
n
complete
sequences
as
TS;
19:
Set
C
=
∅
and
TS
←
TS;
20:
while
|C|
<
num
do
21:
Seek
non-dominated
solutions
in
TS
→
D
based
on
the
Paeto
dominance
relation;
22:
Set
k
=
|D|.
23:
if
k
≥
(num
−
|C|)
then
24:
Randomly
select
num
−
|C|
non-dominated
solution(s)
from
D
→
E.
25:
C
=
C
E.
26:
else
27:
Set
C
=
C
D
and
TS
=
TS
\D.
28:
end
if
29:
end
while
30:
Output
C.
To
clearly
demonstrate
the
process
of
generating
multiple
solu-
tions
using
vMME
heuristic,
the
example
used
in
Section
2.2
is
provided
here.
First,
the
average
sample
value
of
each
job
on
each
machine
is
yielded
according
to
the
sample
values
of
3
times
obtained
in
Section
2.2,
which
is,
p
4×3
=
[4,
7,
5,
5,
7,
5,
5,
7,
3,
6,
7,
6]
Suppose
that
the
unscheduled
sequence
and
the
number
of
generated
solutions
are
S
=
{1,
2,
3,
4}
and
num
=
3,
respectively.
Processing
time
of
job
1
on
the
first
machine
is
the
shortest,
i.e.,
1,
we
will
arrange
job
1
at
the
first
position
of
.
On
this
circumstance,
(1)
=
1,
and
S
=
S
\
(1)
=
{2,
3,
4}.
Following
that,
processing
time
of
job
3
on
the
last
machine
is
the
shortest,
we
will
arrange
job
3
at
剩余16页未读，继续阅读
weixin_38576561
- 粉丝: 4
- 资源: 903
我的内容管理
展开
最新资源
- OptiX传输试题与SDH基础知识
- C++Builder函数详解与应用
- Linux shell (bash) 文件与字符串比较运算符详解
- Adam Gawne-Cain解读英文版WKT格式与常见投影标准
- dos命令详解：基础操作与网络测试必备
- Windows 蓝屏代码解析与处理指南
- PSoC CY8C24533在电动自行车控制器设计中的应用
- PHP整合FCKeditor网页编辑器教程
- Java Swing计算器源码示例：初学者入门教程
- Eclipse平台上的可视化开发：使用VEP与SWT
- 软件工程CASE工具实践指南
- AIX LVM详解：网络存储架构与管理
- 递归算法解析：文件系统、XML与树图
- 使用Struts2与MySQL构建Web登录验证教程
- PHP5 CLI模式：用PHP编写Shell脚本教程
- MyBatis与Spring完美整合：1.0.0-RC3详解
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
