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

TECHNICAL UNIVERSITY OF CLUJ-NAPOCA
ACTA TECHNICA NAPOCENSIS
Series: Applied Mathematics, Mechanics, and Engineering
Vol. XX, Issue xx, Month, 2019
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.
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 solution
for which constructive approach is used, and

3
then the move strategy determines the way in
which neighbors are visited and the tabu list is
used to prevent cycling and guides 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(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
Algorithm 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 =2 000;
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 5.
if Cmax(S) < F then set S* = S
Step 6.
if maxIterNumber has not been
reached then

set k = k+1;
go to Step 2.1
4. RESULTS
The proposed algorithm has been tested on the
120 instances from Taillard’s [14]. Di and AD,
the average of the distances are calculated for
each data-set instance i:
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
heuristic solution of problem instance number 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 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) refers TS with pure swap random
between the job positions (called here TS) and
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
Cmax and AD for Taillards 20 jobs benchmark

5
Fig.2 Cmax and AD for Taillards 50 jobs benchmarkFig.3 Cmax and AD for Taillards 100 jobs benchmark

Fig.4 Cmax and AD for Taillards 200 and 500 jobs
Table2
The average of the distances for Taillard’s
benchmark problems
Taillard’s set HGATSAH
20 x 50.040.258434807.7
50 x 100.030.3401564910.
61
20 x 200.030.410890848.7
6
50 x 50.010.076034074.0
9
50 x 100.730.9921394110.
96
50 x 201.181.7723609812
100 x 50.010.157136702.8
8
100 x 100.260.733010577.6
4
100 x 201.631.5584761510.
53
200 x 100.230.626033815.3
2
200 x 201.541.216205479.4
500 x 20-0.943720066.2
9
5. DISCUSSION
TSA approach was used to improve TS with
pure swap random between the jobs positions
with an intensive exploration over the elitist
solutions on 2000 iterations, f or all Taillard’s
[14] data sets. TSA compared well with the
best known upper bounds, TS and ALA,
especially for the larger benchmark (Table1).
Upon analysis of the results, it can be seen in
Table2 TSA performs competitively with the
other heuristics proposed by Eskenasi[16]
marked here as HGA and Gupta[17] – called
here H. The SD measures 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 benchmarks
and low values of Score are obtained for 50,
100, 200, 500 sets. TSA has been coded in java1.8 and run on a PC with INTEL® Core (TM)-
i5 CPU @ 2.30 GHz processor, 16 GB.The
CPU of each problem vary in the size of the
jobs and the machines from 5 sec to 30 min.
6. CONCLUSION
The proposed approaches is seeded with the
initial permutation provided by NEH[5] and
continuously modifies the 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 interchanges between
job positions that conducts to the lower
solutions. When no more elites can be
generated from the current solution drives 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 based on
previously good solutions. To verify the
performance of TSA the experiments are
conducted on Taillard's benchmarks. Proper
search diversification is possibly the most
critical issue in the design of TS heuristics and
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.

7
[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 flowshopscheduling 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
[16] Eskenasi M., Mehrandezh M., The
Permutation Flow-Shop Scheduling Using a
Genetic Algorithm-based Iterative Method .
Ind Eng Manage 5: 191. doi:10.4172/2169-
0316.1000191, 2016
[17] Gupta A., Chauhan S., A heuristic
algorithm for scheduling in a flow shop
environment to minimize makespan ,
International Journal of Industrial
Engineering Computations, 6(2), 173-184,
2015
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, 0040-722-233482