Information Technology Reference
In-Depth Information
the three defining points of each TFN. It turns out that for any pair of TFNs
M
and
N
, the approximated sum
M
+
N
(
m
1
+
n
1
,m
2
+
n
2
,m
3
+
n
3
)coin-
cides with the actual sum of TFNs; this is not necessarily so for the maximum
max
≈
{
M, N
}≈
{
m
1
,n
1
}
,
max
{
m
2
,n
2
}
,
max
{
m
3
,n
3
}
(max
), although they have
identical support and modal value.
The membership function of a fuzzy number can be interpreted as a possibility
distribution on the real numbers. This allows to define its expected value [17],
given for a TFN
N
by
E
[
N
]=
4
(
n
1
+2
n
2
+
n
3
). It coincides with the neutral
scalar substitute of a fuzzy interval and the centre of gravity of its mean value [4].
It induces a total ordering
≤
E
in the set of fuzzy intervals [5], where for any two
fuzzy intervals
M, N M
≤
E
N
if and only if
E
[
M
]
≤
E
[
N
].
2.2 Fuzzy Open Shop Scheduling
If processing times of operations are allowed to be imprecise and such imprecision
or uncertainty is modelled using TFNs, the resulting schedule is fuzzy in the sense
that starting and completion times for each operation and hence the makespan
are TFNs. Each TFN can be seen as a possibility distributions on the values
that the time may take. Notice however that there is no uncertainty regarding
the task processing ordering given by the schedule.
An important issue with fuzzy times is to decide on the meaning of “optimal
makespan”. It is not trivial to optimise a fuzzy makespan, since neither the
maximum nor its approximation define a total ordering in the set of TFNs.
Using ideas similar to stochastic scheduling, we follow the approach taken for
the fuzzy job shop in [9] and use the total ordering provided by the expected
value and consider that the objective is to minimise the expected makespan
E
[
C
max
]. The resulting problem may be denoted
FuzO
||
E
[
C
max
].
3 Particle Swarm Optimization for the FOSP
Given the complexity of the open shop, different metaheuristic techniques have
been proposed to solve the general
m
-machine problem. Among these, [12] de-
scribes two heuristic methods to obtain a list of operation priorities later used
in a list-scheduling algorithm; [16] proposes a tabu search algorithm; [7] intro-
duces a genetic algorithm hybridised with local search; a genetic algorithm using
heuristic seeding is given in [20], and [23] proposes a solution based on particle
swarm optimisation. As mentioned in Section 1, among these only a genetic al-
gorithm [18] and its combination with local search [10] have been applied to the
case where durations are fuzzy numbers.
PSO is a population-based stochastic optimisation technique inspired by bird
flocking or fish schooling [13]. In PSO, each position in the search space cor-
responds to a solution of the problem and particles in the swarm cooperate to
find the best position (hence best solution) in the space. Particle movement is
mainly affected by three factors:
Search WWH ::
Custom Search