Particle Swarm Optimisation for Open Shop Problems with Fuzzy Durations - Foundations on Natural and Artificial Computation - page 365

while Ω = ∅ do
f ∗ ← min o ij ∈Ω {E [ f ij ] } .
s ∗ ←

.
Identify the conflict set O ←{o ij : E [ s ij ] <s ∗ + δ × ( f ∗ − s ∗ ) ,o ij ∈ Ω} .
Choose the operation o ij from O with smallest x ij .
Schedule the operation o ∗ .
Ω ← Ω −{o ∗ } .

min o ij ∈Ω {E [ s ij ] }

Alg. 2: The pF G & T algorithm

Decodification of a particle may be done in different ways. For the crisp job
shop and by extension for the open shop, it is common to use the

algo-
rithm [6], which is an active schedule builder. A schedule is active if one task
must be delayed for any other one to start earlier. Active schedules are good in
average and, most importantly, the space of active schedules contains at least an
optimal one, that is, the set of active schedules is dominant . For these reasons
it is worth to restrict the search to this space. In [7] a narrowing mechanism
was incorporated to the G&T algorithm in order to limit machine idle times by
means of a delay parameter δ

G&T

[0 , 1], thus searching over the space of so-called
parameterised active schedules. In the deterministic case, for δ< 1thesearch
space is reduced so it may no longer contain optimal schedules and, at the ex-
treme δ = 0 the search is constrained to non-delay schedules, where a resource
is never idle if a requiring operation is available. This variant of G&T has been
applied in [23] to the deterministic OSP, under the name “parameterized active
schedule generation algorithm”.
In Algorithm 2 we propose an extension of parameterised G&T to the case
of fuzzy processing times, denoted pF G & T . It should be noted that, due to
the uncertainty in task durations, even for δ = 1, we cannot guarantee that
the produced schedule will indeed be active when it is actually performed (and
tasks have exact durations). We may only say that the obtained fuzzy schedule
is possibly active . Throughout the algorithm, Ω detones the set of the operations
that have not been scheduled, X k the priority matrix, s ij the starting time of
the operation o ij and f ij the completion time of the operation o ij .
Notice that the pF G & T algorithm may change the task processing order given
by the particle position. Therefore the PSO does not record in gbest and pbest
the best positions found so far, but rather the best operation sequences of the
schedules generated by the decoding operator.

∈

3.2 Particle Movement and Velocity

Particle velocity is traditionally updated depending on the distance to gbest and
pbest . Instead, this PSO only considers whether the position value x ij is larger
or smaller than pbest ij ( gbest ij ). For any particle, its velocity is represented by
an array of the same length as the position array where all the values are in the
set . Updating is controlled by the inertia weight w at the beginning of

each iteration as follows. For each particle k and operation o ij

{− 1 , 0 , 1 }

(in the following,