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

- if the makespan of the particle solution is equal to any pbest solution, replace
that pbest solution with the new particle solution;
- if the makespan of the particle solution is less than the worst pbest solution
and different from all pbest solutions, set the worst pbest solution equal to
the particle solution.

4 Experimental Results

For the experimental study we use the test bed given in [10], where the authors
follow [5] and generate a set of fuzzy problem instances from well-known bench-
mark problems from [3]. Given a crisp problem instance, each crisp processing
time t is transformed into a symmetric fuzzy processing time p ( t ) such that its
modal value is p 2 = t and p 1 , p 3 are random values, symmetric w.r.t. p 2 and gen-
erated so the TFN's maximum range of fuzziness is 30% of p 2 .Bydoingthis,the
optimal solution to the crisp problem provides a lower bound for the expected
makespan of the fuzzified version [5]. The original problem instances consist of
6 families, denoted J3, J4,. . . , J8, of sizes 3 8, containing 8 or 9

instances each. From each crisp problem instance 10 fuzzy versions were gener-
ated, so in total there are 520 problem instances. The obtained benchmarks for
the fuzzy open shop are available at http://www.di.uniovi.es/tc .
In [10], the authors propose a neighbourhood structure which combined with
the GA from [18] provides a MA that not only obtains better solutions but is
also more “reliable” in the sense that there is less variability in quality solution
across different executions. In this experimental study we compare our PSO with
this MA.
For the PSO we take the best values for each parameter obtained after a
parameter analysis in [23]: swarm size N = 60, C 1 =0 . 7, C 2 =0 . 1, and inertia
weight w linearly decreasing from 0 . 9to0 . 3. The number of iterations has been
adapted for each problem size so as to obtain similar running times to the MA.
Regarding the filtering mechanism of the search space given in the schedule
generator, the eciency of this reduction depends of the problem size [8], in
fact our experimentation suggest taking δ = 1 (no reduction) in small instances
(families J3 and J4) and δ =0 . 25 in larger ones.
To evaluate its performance, we run the proposed PSO 30 times for each
problem instance, recording the best, average expected makespan values across
these 30 runs. Table 1 shows a summary of the results, with average values
across 30 executions on each the 80-90 instances of the same size (detailed
results for each problem would require 520 rows). It contains three columns for
each method, PSO and MA, showing the Average of the Best values ( AoB ), the
Average of the Average values ( AoA ), and the Average CPU Times in seconds
( Time ). We can see that both the PSO and the MA perform equally well on
the small (3

× 3, 4 × 4,...,8 ×

4) problems (the AoA value of PSO is slightly worse in
the J4 family). As the problem size increases, also does increase the difference in
solution quality between the PSO and the MA, with the former obtaining better
results.

× 3, 4 ×