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

and due dates, in [18] a genetic algorithm is proposed to solve the open shop
with fuzzy durations, and in [10] this genetic algorithm is combined with a local
search method.
In the following, we consider the fuzzy open shop problem with expected
makespan minimisation, denoted FuzO

E [ C max ] and propose a bio-inspired
technique to solve it. The rest of the paper is organized as follows. In
Section 2 we formulate the problem and introduce the notation used across
the paper. Then, in Section 3, we describe the main components of the PSO
algorithm. Section 4 reports results from the experimental study. Finally, in
Section 5 we summarise the main conclusions and propose ideas for future work.

||

2 Open Shop Scheduling with Uncertain Durations

The open shop scheduling problem ,or OSP in short, consists in scheduling a
set of n jobs J 1 ,...,J n to be processed on a set of m physical resources or
machines M 1 ,...,M m . Each job consists of m tasks or operations, each requiring
the exclusive use of a different machine for its whole processing time without
preemption, i.e. all operations must be processed without interruption. In total,
there are mn operations, . A solution to this problem is a

schedule -an allocation of starting times for all operations- which is feasible ,
in the sense that all constraints hold, and is also optimal according to some
criterion. Here, the objective will be minimising the makespan C max ,thatis,
the time lag from the start of the first operation until the end of the last one, a
problem often denoted O

{ O k , 1 ≤ k ≤ mn }

|| C max in the literature.

2.1 Uncertain Durations

In real-life applications, it is often the case that it is not known in advance
the exact time it will take to process one operation and only some uncertain
knowledge is available, for instance, an interval of possible durations, or a most
likely duration with a certain error margin. Such knowledge can be modelled
using a triangular fuzzy number or TFN, given by an interval [ n 1 ,n 3 ] of possible
values and a modal value n 2 in it. For a TFN N , denoted N =( n 1 ,n 2 ,n 3 ), the
membership function takes the following triangular shape:

⎨

x−n 1
n 2 −n 1

: n 1 n 2

≤ x ≤

x−n 3
n 2 −n 3

: n 2 <x n 3 μ N ( x )= ≤ (1)

⎩

: x<n 1 or n 3 <x 0

In the open shop, we essentially need two operations on processing times (fuzzy
numbers), the sum and the maximum. These are obtained by extending the cor-
responding operations on real numbers using the Extension Principle . However,
computing the resulting expression is cumbersome, if not intractable. For the
sake of simplicity and tractability of numerical calculations, we follow [5] and
approximate the results of these operations, evaluating the operation only on