TECHNICAL UNIVERSITY OF CLUJ-NAPOCA ACTA TECHNICA NAPOCENSIS Series: Applied Mathematics, Mechanics, and Engineering Vol. XX, Issue xx, Month, 20xx A… [608879]

TECHNICAL UNIVERSITY OF CLUJ-NAPOCA
ACTA TECHNICA NAPOCENSIS
Series: Applied Mathematics, Mechanics, and Engineering
Vol. XX, Issue xx, Month, 20xx
A TABU SEARCH APPROACH FOR MAKESPAN MINIMIZATION IN A
PERMUTATION FLOW SHOP SCHEDULING
¶
Cristina Elena DODU
¶
¶
Abstract: Flow shop scheduling deals with the sequencing of a set of jobs that visit a set of machines in
the same order. In order to obtain better solutions in a reasonable time for this problem with the
makespan minimization criterion, in this paper is proposed an application of a Tabu Search with a
combination between the diversification and the intensification strategies over a swap-based perturbation
capable of searching the solution space economically and effectively.
Key words: flowshop, makespan minimisation, tabu search, metaheuristics;
¶
1. INTRODUCTION
¶
Permutation Flow Shop Scheduling (PFSP) can
be described as follows: each of n jobs from the
set J = {1,2,…,n} has to be processed on m
machines 1,2,…,m. A job processing
permutation π, π = (π(1), π(2),…, π(n)), where
π(j) denotes the element of J which is in
position j of π, is defined before the beginning
of the processing procedure, and then these jobs
are processed through every machine in the
same order of the permutation π. Let Π denote
the set of all such permutations. The makespan
minimization criterion(Cmax) means finding
π*, the optimal sequence of jobs that will
minimize the completion time (the difference
between the time of completion of the last job
and the starting time of the first job):

Cmax(π*) ≤ Cmax(π) π Π. (1) ∀ ∈
Let c(i, j) be the completion time, P(i, π(j)) the
processing time of the job i on the machine then
the completion time is calculated by
c(i, j) = max {c(i-1, j), c(i, j-1) + P(i, π(j))} (2)
where i=1,..n, j=1,…m
c(0, j) =0 for j=1,…m and
c(i, 0) =0 for i=1,..n

Cmax(π) = c(m, n) (3) In the past decades, the research on flow shop
scheduling problem has attracted much
attention and different approaches have been
proposed since the problem is known to be
NP-complete for more than two machines . The
development of a heuristic algorithm may
consist of one or more of these phases: index
development, solution construction and solution
improvement that are, in general, independent
one from each other. In the literature, many
algorithms can be found from known
constructive algorithms given by Palmer[1],
Campbell, Dudek and Smith[2], Gupta[3] and
Dannenbring[4], the insertion heuristic
algorithms given by Nawaz, Enscore and
Ham[5] to the iterative algorithms used to
improve the quality of a constructive solution.
Usually, the improvement approaches are
classified into descending local searches and
metaheuristics. The main disadvantage of
heuristic method is that it is not able to continue
the search upon becoming trapped in a local
optimum. The metaheuristic algorithms
overcome these disadvantages of heuristic
using two types of search procedures: single
point (focus on modifying and improving a
single candidate solution: TabuSearch,
Simulated Annealing) and population based
search (maintain and improve multiple
candidate solutions using population
characteristics to guide the search: Ant Colony

Optimization, Particle Swarm Optimization,
Evolution Algorithm and Artificial Bee Colony
Algorithm).
The remainder of this paper is organized as
follows: Section 2 contains a review of tabu
search approach, Section 3 considers the
proposed approach while Section 4 shows the
results of solving benchmark problems by the
proposed approach. Discussion and conclusion
are presented in Section 5 and 6
¶
2. METHODOLOGY REVIEW
¶
A comprehensive examination of the Tabu
Search(TS) methodology can be found in the
books by Glover [6], [7] including the basic
tabu navigation algorithm, the flow chart and
the description of various aspects of TS. Tabu
search approach consists of several elements
called the move, neighborhood, initial solution,
search strategy, memory, aspiration function
and stopping rules and is considered to be an
extent of the local search strategies moving
from a solution to another one in its
neighborhood, according to some well-defined
rules. Starting from an initial solution, TS
generates a new alternative s* in the
neighborhood of the original alternative s with
a function f that transforms s into s*. For any
solution s, a subset of moves to s is applicable
and generates a subset of solution NH(s), called
the neighborhood of s. The best solution in the
neighborhood of the current solution is chosen
to be a new current solution. TS starts from an
initial solution and iteratively moves from the
current solution s to the best solution s* in
NH(s), even if s* is worse than the current
solution s until reaching a maximum iteration
number. This makes a TS escape from a local
optimum in its search for the global optimum.
In order to prevent cycling, moves which bring
it back to a recently visited solution should be
forbidden for a certain number of iterations.
This is accomplished by keeping the attributes
of the forbidden moves in a list, called a tabu
list. The size of the tabu list must be large
enough to prevent cycling.
An application of TS is generally described by
several factors. They are:
– Initial solution methods- Neighborhood generation methods providing
a set of possible moves applicable to the current
solution. The solution’s neighborhood and the
move defining are the most important elements
because the ability of the algorithm to search
efficiently the solution space depends on it.
Reeves et al. [8] detected a phenomenon called
the big valley (BV), which means that the good
solutions are similar and they are concentrated
in some promising parts of the solution space.
After TS obtains a good solution, the algorithm
searches through their neighborhoods to find a
better one and the neighborhood local search
plays a very important role.
– Definition of tabu moves with the tabu list
size. Typically there are two kinds of tabu lists,
a long term memory maintaining the history
through all the exploration process as a whole
and a short term memory to keep the most
recently visited tabu movements.
– Termination condition(s). Glover[6] showed
that there are two ways for making the
algorithm stop: when there is no improvement
between two consecutive iterations or the
algorithm will stop when it arrives to maximum
number of iterations.
Several researchers have added features that
enrich the basic tabu search algorithm.
One of the early applications of the tabu search
in scheduling is due to Widmer and Hertz[9]
who developed a tabu search method for the
solution of the permutation flow shop
problems. Taillard[10] also presented a similar
procedure to that of Widmer and Hertz where a
Tabu Search technique is applied to a schedule
generated by an improved NEH heuristic.
Taillard tested various types of neighbourhoods
and the neighbourhood resulting from changing
the position of one job proved to be the best.
Nowicki and Smutnicki[11] proposed a Tabu l
instances. Experimental findings of Nowicki
and Smutnicki[11] showed that few insertions
in the adjacent blocks can be more promising
than other positions. Ben-Daya and Al-
Fawzan[12] implemented a tabu search
algorithm with some extra features such as
intensification and diversification schemes that
provide better moves in the tabu search process.
The algorithm proposed provides similar results
as the of Taillard [10]. Eksioglu et al [12] for
the proposed algorithm start with initial

3
solution for which constructive approach is
used, and then the move strategy determines the
way in which neighbors are visited and the tabu
list is used to prevent cycling and guide the
search toward unexplored regions of the
solution space. The neighborhood of a solution
is generated using a combination of three
different exchange mechanisms called 3XTS.
¶
3. PROPOSED METHODOLOGY
¶
The main idea of this paper is to modify the
tabu search approach by introducing a maximal
distance D in order to limit the non-local moves
from the current solution and re-intensification
of search around previously encountered high-
quality solutions. Starting from the current
solution s uses the swap random move operator
between the job positions. Only the solutions N
with the conditions:
Cmax(N)≠Cmax(S) (4)
Cmax(N)≤Cmax(S)+D (5)
are added to the NH(S). The non-local solutions
are ordered and saved into the temporary
memory between the iterations and forbidden
until no local solutions are available for the
current solution. In this situation the current
solution is replaced by the best solution from
the temporary memory not in the tabu list
cleaning the temporary memory. The proposal
approach stimulates the exploration of any
subarea concentrated around a chosen current
solution by increasing the distance D.
Notations:
k – the iteration number
maxIterNumber – the number of iterations
S – the current solution in the kth iteration
NH(S) – the neighborhood of S
S* – the optimal solution
F – Cmax of S*
TL – tabu list
tMemory – temporary memory used to keep the
forbidden solutions
N – neighbor, N NH(S) ∈
N* – best solution from NH(S) means N is the
solution with the best makespan:
Cmax(N*) = min{Cmax(N) | N NH(S)} ∈
T – forbidden temporary solution, T tMemory ∈T* – best solution from tMemory means T is
the solution with the best makespan:
Cmax(T*) = min{Cmax(T) | T tMemory} ∈
D – the distance between the current solution
and the collection of elite solutions
step – tuning parameter for the distance D
Alghoritm TSA
Step 1.
generate an initial solution s using
NEH[5] algorithm;
set k = 1,
set S = s, S*=s, F = Cmax(s);
set D = 1; step = 1;
set maxIterNumber=2000;
Step 2.1
add S to TL;
add S to tMemory;
Step 2.2
while the size of NH(S) has not been
reached executes Step 2.3
Step 2.3
generate randomly two jobs positions
(i, j) from the current solution obtaining
the solution N;
if Cmax(N) != Cmax(S) and
Cmax(N)<=Cmax(S)+D
then add N to NH(S)
otherwise add N to tMemory
Step 3.
order NH(S) by Cmax values
Step 4.
if NH(S) is not empty then
choose the best local solution N*
set S=N
otherwise
choose the best solution T*
if T TL then ∈
repeat find the best solution T*
and T* is not in TL
clean tMemory;
set S = T
set D = D + step;
Step 6.
if Cmax(S)< F then set S*=S
Step 7.
if maxIterNumber has not been
reached then
k = k+1;
go to Step 2.1 ¶

4. RESULTS
¶
The proposed algorithm has been tested on the
following on 120 instances from Taillard’s [14]
datasets. For each dataset instance i is
calculated Di and AD – the average of the
distances for each benchmark set using
Di=Cmaxi−UBi
UBi⋅100% (6)
AD=1
I∑i=1I
Distancei (7)
where
UBi is the upper bound (UB) of problem
instance no I , Cmaxi is the makespan of the
euristic solution of problem instance no I and
I is the number of problem instances.
The goodness of fit of the best solutions in all
iterations is measured by the Standard
Deviation (SD) of the makespan population and
the Score (the number of SD between Mean
and Cmax). A low SD indicates that solutions
are generally close to the Mean (the distribution
will be taller) and a high SD indicates higher
dispersion from the Mean or greater variability
of the solutions (the distribution will be flatter
and wider). The score(S) measures where the
optimal solution is located compared to the
average of the makespans (S = 1 means Cmax
the is located nearest to the Mean) in Fig1-Fig4 .
To complete comparison the proposed
algorithm(called here TSA) is refer to the TS
with pure swap random between the job
positions (called here TS) and to the best
solutions extracted from the paper of
Agarwal[15] (called here ALA) in Table1
Table 1
The average of the distances for Taillard’s
benchmark problems
Taillard’s set TSATS ALA
200.33649401.07612650.26
500.94684401.15944742.62
1000.81620782.84587622.04
200;5000.69648981.13262652.07Fig.1 Makespans and the average of the distance for
Taillards 20 jobs benchmark problems .
Fig.2 Makespans and the average of the distance for
Taillards 50 jobs benchmark problems .

5
Fig.3 Makespans and the average of the distance for
Taillards 100 jobs benchmark problems .
Fig.4 Makespans and the average of the distance for
Taillards 200 and 500 jobs benchmark problems . ¶ 5. DISCUSION
¶
The TSA approach was used to improve TS
with pure swap random between the job
positions. For all Taillard’s[14] datasets TSA
compared well with the best known upper
bounds, TS and TSA especially for the larger
benchmark set (Table1). T he Standard
Deviation values measure how far from the
initial solution was conducted the search after
successive local explorations. High values of
SD are counted on the 200 and 500 benchmark
sets and small Scores (1 and 2 values) when
Cmax is located nearest the Mean are obtained
for 50,100,200 and 500 sets. The proposed
approach is coded in java 1.8 and was running
on 2.30 Ghz with 16 GB PC. The computation
times of each problem vary in the size of the
jobs and the machines from 5 seconds to 30
minutes.
¶
6. CONCLUSION
¶
Proper search diversification is possibly the
most critical issue in the design of tabu search
heuristics. The proposed approaches are seeded
with one initial permutation provided by NEH
algorithm and continuously modifies the
current permutation until the maximum number
of iterations are met. The main idea of this
paper is to modify the tabu search approach by
introducing an intermediate memory for the
forbidden generated interchanges between job
positions that conducts to the lower solutions.
When no more elite solutions can be generated
from the current solution then drive the search
into new regions of the best forbidden solution
space which may be viewed as a form of
diversification. The long-term memory is used
to construct the global optimum solution based
on previously good solutions. Future research
can further try to find better non-deterministic
local neighborhood search.

7. REFERENCES
¶
[1] Palmer, D. S., Sequencing jobs through a
multistage process in the minimum total
time: a quick method of obtaining a near-
optimum, Operational Research Quarterly ,
16, 101-107, 1965
[2] Campbell, H. G., Dudek, R. A. and Smith,
M. L., A heuristic algorithm for the n-job,
m-machine, sequencing problem .
Management Science, 16, B630-B637, 1970
[3] Gupta, J.N.D., A functional heuristic for the
flow-shop scheduling problem , Operational
Research Quarterly, 22, 39-47, 1971
[4] Dannenbring, D. G., An evaluation of flow-
shop sequence heuristics. Management
Science, 23, 1174-1182, 1977.
[5] Nawaz, M., Enscore, E. E., and Ham, I., A
heuristic algorithm for the m-machine, n-job
flow-shop sequencing problem . OMEGA,
11, 91-95, 1983.
[6] Glover F., Tabu search-Part I , ORSA
Journal on Computing, vol. 1, no. 3, 190-
206, 1989.
[7] Glover F., Tabu search-Part II , ORSA
Journal on Computing, vol. 2, no. 3, 4-32,
1990.
[8] Reeves CR., Yamada T. Genetic
algorithms, path relinking and the flowshop
sequencing problem., Evol Comput 6(1),
230–234, 1998
[9] Widmer, M. and Hertz, A. A new heuristic
method for the flow shop sequencing
problem., European Journal of Operational
Research, vol. 41(2), 186-193, 1989[10] Taillard, E., Some efficient heuristic
methods for the flow-shop sequencing
problem, European Journal of Operational
Research, 47:65-74, 1990
[11] Nowicki, E., and Smutnicki, C., A fast
tabu search algorithm for the permutation
flow-shop problem , European Journal of
Operational Research , 91, 160-175, 1996.
[12] Ben-Daya, M. and Al-Fawzan, M., A tabu
search approach for the flow shop
scheduling problem., Eur. J. Oper. Res., 109,
88–95, 199 .
[13] Eksioglu, B., Eksioglu S. D. and Jain P., A
tabu search algorithm for the flowshop
scheduling problem with changing
neighborhoods, Computers & Industrial
Engineering.54, 1- 11, 2008.
[14] Pararach S., A tabu search approach for
makespan minimization in a permutation
flowshop scheduling problems , International
Conference on Industrial Engineering and
Operations Management, pp. 300-305,
Kuala Lumpur, Malaysia, 2011.
[14] Taillard E., Benchmarks for basic
scheduling problems , European Journal of
Operational Research 64, 278-285, 1993.
[15] Agarwal A., Colak S, Eryarsoy E.
Improvement heuristic for the flow-shop
scheduling problem: An adaptive-learning
approach, European Journal of Operational
Research 169, 801–815 , 2006
¶
Algoritm Tabu Search pentru problema de tip flow shop cu minimizarea timpului de executie
¶
Cristina Elena Dodu Ph.D student, Faculty of Engineering, Technical University of Cluj-
Napoca, Department of Manufacturing Engineering, c_dodu@yahoo.com, Aleea Uranus, nr.15,
Cluj-Napoca, 0040722233482,