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

More detailed results are presented in Table 2, where each row corresponds to
one set of ten fuzzy versions of one of the crisp instances of size 8 8. It shows

relative makespan errors w.r.t. a lower bound for the expected makespan, which
is 1000 for all problem instances. As expected, the PSO compares favourably
with MA in all instances. Notice as well that the relative errors for the best ( B )
and average ( A ) solution do not differ greatly, suggesting that the PSO is quite
stable. Figure 1 illustrates the reduction of the makespan error in average for
each set of fuzzy problems; we can observe this is higher for mean values, which
are more significant in stochastic algorithms.

×

5 Conclusions and Future Work

We have considered an open shop problem with uncertain durations modelled as
triangular fuzzy numbers, FuzO

E [ C max ], and have proposed a particle swarm
optimization technique to solve this problem. The PSO has obtained good results
both in terms of relative makespan error and also in comparison to a memetic al-
gorithm from the literature. These promising results suggest directions for future
work. First, the PSO should be tested on more dicult problems, fuzzy versions
of other benchmark problems from the literature. Also, the PSO provides a solid
basis for the development of more powerful hybrid methods, in combination
with local search techniques, an already successful approach in fuzzy job shop
problems [22].

||

Acknowledgments

This work is supported by the Spanish Ministry of Science and Education under
research grant MEC-FEDER TIN2010-20976-C02-02.

References

1. Andresen, M., Brasel, H., Morig, M., Tusch, J., Werner, F., Willenius, P.: Simulated
annealing and genetic algorithms for minimizing mean flow time in an open shop.
Mathematical and Computer Modelling 48, 1279-1293 (2008)
2. Blum, C.: Beam-ACO—hybridizing ant colony optimization with beam search: an
application to open shop scheduling. Computers & Operations Research 32(6),
1565-1591 (2005)
3. Brucker, P., Hunrink, J., Jurisch, B., Wostmann, B.: A branch & bound algorithm
for the open-shop problem. Discrete Applied Mathematics 76, 43-59 (1997)
4. Dubois, D., Fargier, H., Fortemps, P.: Fuzzy scheduling: Modelling flexible con-
straints vs. coping with incomplete knowledge. European Journal of Operational
Research 147, 231-252 (2003)
5. Fortemps, P.: Jobshop scheduling with imprecise durations: a fuzzy approach. IEEE
Transactions of Fuzzy Systems 7, 557-569 (1997)
6. Gier, B., Thompson, G.L.: Algorithms for solving production scheduling prob-
lems. Operations Research 8, 487-503 (1960)