Information Technology Reference
In-Depth Information
Particle Swarm Optimisation for Open Shop
Problems with Fuzzy Durations
Juan Jose Palacios 1 ,Ines Gonzalez-Rodr ıguez 2 ,
Camino R. Vela 1 , and Jorge Puente 1
1 A.I. Centre and Department of Computer Science,
University of Oviedo, Spain
{puente,crvela}@uniovi.es
http://www.di.uniovi.es/tc
2 Department of Mathematics, Statistics and Computing,
University of Cantabria, Spain
ines.gonzalez@unican.es
Abstract. In this paper we confront a variation of the open shop prob-
lem where task durations are allowed to be uncertain and where uncer-
tainty is modelled using fuzzy numbers. We propose a particle swarm
optimization (PSO) approach to minimise the expected makespan using
priorities to represent particle position, as well as a decoding algorithm
to generate schedules in a subset of possibly active ones. Finally, the per-
formance of the PSO is tested on several benchmark problems, modified
so as to have fuzzy durations, compared with a memetic algorithm from
the literature.
1
Introduction
The open shop scheduling problem, with an increasing presence in the literature,
is a problem with clear applications in industry—consider for instance testing
facilities, where units go through a series of diagnostic tests that need not be
performed in a specified order and where different testing equipment is usually
required for each test [19]. Given its NP-hardness for a number of machines
m ≥
3 [19], practical approaches to solving it usually involve heuristic strategies:
simulated annealing [1], tabu search [16], genetic algorithms with local search [7],
ant colony optimization [2], etc.
To enhance the range of applications of scheduling, part of the research is
devoted to model the uncertainty and vagueness pervading real-world situations.
The approaches are diverse and, among these, fuzzy sets have been used in a
wide variety of ways [4]. Incorporating uncertainty usually requires a significant
reformulation of the problem and solving methods, in order that the problem can
be precisely stated and solved eciently and effectively. Some heuristic methods
have so far been proposed for fuzzy flow and job shop problems, where uncertain
durations are modelled via fuzzy intervals, e.g. [11], [15], [24], [21]. However, to
the best of our knowledge, the open shop problem has received little attention
in the fuzzy framework: in [14] fuzzy sets are used to represent flexible job start
 
Search WWH ::




Custom Search