Information Technology Reference
In-Depth Information
-
Inertia: Velocity of the particle in the latest iteration.
-
pbest
: The best position found by the particle.
-
gbest
: The best position found by the swarm so far (the best
pbest
).
The potential solutions or particles fly through the problem space changing their
position and velocity by following the current optimum particles
pbest
and
gbest
.
1. generate and evaluate the initial swarm.
2. compute gbest and pbest for each particle.
while
no termination criterion is satisfied
do
for
each particle
k
do
for
each dimension
d
do
3. update velocity
v
d
.
4. update position
x
d
.
5. evaluate particle
k
.
6. update pbest and gbest values.
return
the schedule from the best particle evaluated so far;
Alg.
1: A generic PSO algorithm
Algorithm 1 describes the structure of a generic PSO algorithm. First, the
initial swarm is generated and evaluated. Then the swarm evolves until a termi-
nation criterion is satisfied and in each iteration, a new swarm is built from the
previous one by changing the position and velocity of each particle towards its
pbest
and
gbest
locations.
In [23], a PSO algorithm was proposed to solve the deterministic OSP which
improved the best published results. Here we shall extend this algorithm to the
fuzzy framework and test it compared to the state-of-the-art methods.
3.1 Position Representation and Evaluation
Following [23], we use a priority-based representation for particle positions. Thus
a schedule is encoded as a priority matrix
X
k
=(
x
ij
)
i
=1
...m,j
=1
...n
,where
x
ij
denotes the priority of operation
o
ij
,thetaskofjob
j
processed on machine
i
.
An operation with smaller
x
ij
has a higher priority to be scheduled.
If we represent an OSP solution as a task processing order
S
,whichisa
permutation of tasks, we can transfer this permutation to a priority matrix and
viceversa. For instance, given the following solution:
S
=
o
11
o
13
o
23
o
12
o
31
o
33
o
21
o
23
o
22
a particle in the space can be obtained by randomly setting
x
ij
in the interval
(
p
0
.
5
,p
+0
.
5) where
p
is the location of
o
ij
in
S
. Therefore, the operation
with smaller
x
ij
has higher priority to be scheduled. The above permutation list
can be transferred to:
−
⎛
⎞
1
.
24
.
01
.
7
6
.
69
.
42
.
7
5
.
37
.
96
.
4
X
k
=
⎝
⎠
Search WWH ::
Custom Search