Information Technology Reference
In-Depth Information
heuristic typically getting with 3-4% to the optimal and the
variable-opt
algorithm
of [20] typically getting around 1-2%.
The objective for new emerging evolutionary systems is to find a guided approach to
TSP and leave simple local search heuristics to find better local regions, as is the case
for this chapter.
7.2.2
Flow Shop Scheduling Problem
A flow shop is a scheduling problem, typical for a manufacturing floor. The terminol-
ogy for this problem is typical of a manufacturing sector. Consider
n
number of jobs
j
(
i
= 1
,...
n
), and a number of machines
M
:
M
(
j
= 1
,....,
m
).
A job consists of
m
operation and the
j
th
of each job must be processed on machine
j
. So, one job can start on machine
j
if it is completed on machine
j-1
and if machine
j
is
free. Each job has a known processing time
p
i
,
j
. The operating sequence of the jobs is
the same on all the machines. If one job is at the
i
th
position on machine 1, then it will
be on the
i
th
position on all machines.
The objective function is then to find the minimal time for the completion of all the
jobs on all the machines. A job
J
i
is a sequence of operations, having one operation for
each of the
M
machines.
,where
O
ij
represents the
j
th
operation on
J
i
.
2.
O
ij
operation must be processed on
M
j
machine.
3. for each operation
O
ij
, there is a processing time
p
i
,
j
.
1.
J
i
=
{
O
i
1
,
O
i
2
,
O
i
3
,..,
O
iM
}
Now let a permutation be represented as
{
∏
1
,
2
,...,
}
. The formulation of the
∏
∏
N
i
,
j
),forthe
i
th
jobonthe
j
th
machine can be given as:
completion time for
C
(
∏
C
(
∏
1
,
1)=
p
∏
,
1
C
(
∏
1
,
1)=
C
(
∏
i
−
1
,
1)+
p
∏
,
1
,
i
= 2
,...,
N
(7.2)
∏
1
,
j
)=
C
(
∏
1
,
j
−
1)+
p
∏
1
,
j
,
i
= 2
,...,
M
C
(
∏
1
,
j
)=max
{
∏
i
−
1
,
1)
,
C
(
∏
1
,
j
−
}
+
p
∏
1
,
j
,
i
= 2
,...,
N
;
j
= 2
,..,
M
C
(
C
(
1)
The makespan or the completion time is given as the
C
(
∏
N
,
M
), as the completion
time of the
last
job in the schedule on the
last
machine.
7.2.3
2 Opt Local Search
A local search heuristic is usually based on simple tour modifications (exchange heuris-
tics). Usually these are specified in terms of the class of operators (exchanges/moves),
which is used to modify one tour into another. This usually works on a feasible tour,
where a
neighborhood
is all moves, which can be reached, in a single move. The tour
iterates till a better tour is reached.
Among simple local search algorithms, the most famous are 2
Opt. The
2-Opt algorithm was initially proposed by [2] although it was already suggested by [5].
This move deletes two edges, thus breaking the tour into two paths, and then reconnects
those paths in the other possible way as given in Fig 7.1.
−
Opt and 3
−
Search WWH ::
Custom Search