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

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: In order to obtain better solutions in a reasonable time for Permutation Flow Shop scheduling
problem with the makespan minimization criterion, in this paper is proposed an application of a Tabu
Search over a swap-based perturbation of the current solution that searches in the solution space
economically and effectively. The performance of the algorithm is measured based on Taillard's
benchmark instances.
Key words: flowshop, makespan minimisation, tabu search, metaheuristics;
1. INTRODUCTION
Permutation Flow Shop Scheduling (PFSP)
deals with the processing of a set of jobs
operated following the same order through
each machine from a predefined production
system In advance of starting the first operation
is defined the unique place of each job in the
processing sequence and it will remain
unchanged. The makespan minimization
criterion attached to PFSP means finding the
optimal processing sequence of jobs that will
minimize the total time of all jobs consumed on
the production system known as the completion
time. For more than two machines PFSP is
recognized to be NP-complete and very
competitive heuristic approaches have been
suggested over the years. The development of
these heuristic solutions has in common tree
typical steps independent one from each other:
index development , solution construction and
solution improvement. Palmer[1], Campbell,
Dudek and Smith[2], Gupta[3] and
Dannenbring[4] has been obtained notable
results for the constructive algorithms and
Nawaz, Enscore and Ham[5] for the insertion
heuristic algorithms. The improvement
approaches are classified into descending local
searches and metaheuristics. The main dificulty
of the heuristic technique is that it’s not able to
continue the search upon becoming stuck-ed ina local optimum. The metaheuristic overwhelm
these imperfections of heuristic introducing
single point and population based search types.
Single point is concentrated on modifying and
improving a single candidate solution of the
local search and is utilized in Tabu Search and
Simulated Annealing. Population based type
works with multiple candidate solutions and the
population characteristics play a very important
role within the search method in order to
preserves and later improves the candidat: [anonimizat].
2. METHODOLOGY REVIEW
In 1988 Fred Glover[6], [7] elaborated the
description of the basic navigation algorithm of
Tabu Search(TS) and examinated various
aspects. Tabu Search initiates the local search
from an initial solution and based on the local
search strategies uses well-defined rules applied
on the candidat: [anonimizat][6] showed two ways for stopping the
algorithm: when no enhancement is discovered
between two consecutive iterations or is
counted the predefined number of iterations.
The search for the global optimum isn’t
interrupted as a result of TS’s escaping from

the trap of finding a local optimum. TS avoids
the moves that bring it back to an old visited
solution keeping for a specified number of
iterations the attributes related with the
disallowed moves in the Tabu List(TL). TL
can be used as a long term memory to keep the
history of all the navigation or as a short term
memory saving the latest visited movements.
The potential of the algorithm is given by the
local search. Reeves et al. [8] noticed the big
valley phenomenon (BV) related with the
distribution of the hight solutions in the
neighborhood means height solutions are alike
and concentrated in some promising parts of the
solution’s neighborhood. Several researchers
such as Widmer and Hertz[9], Taillard[10],
Nowicki and Smutnicki[11], Ben-Daya and Al-
Fawzan[12], Eksioglu et al [12] added their
contribution to improve tabu search algorithm.
3. PROPOSED METHODOLOGY
The main idea of this paper is to improve the
local search approach of TS by introducing a
maximal distance D in order to limit the non-
local moves from the current solution. It
conducts to re-intensification of the local search
around previously high-quality solutions
already encountered. The proposed approach
starts from the current solution S using the
swap random move operator between the job
positions. The following rules applied on the
solution space triage the local solutions and the
valid neighbors denoted with N are added to the
NH(S):
Cmax(N)≠Cmax(S) (4)
Cmax(N)≤Cmax(S)+D (5)
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 working solution is replaced by the
best solution from the temporary memory not in
the tabu list and the temporary memory is
clean. 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 working solution
and the collection of the 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*

3
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 locatednearest 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.07
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

Fig.1 Cmax and AD for Taillards 20 jobs benchmark
Fig.2 Cmax and AD for Taillards 50 jobs Fig.3 Cmax and AD for Taillards 100 jobs
Fig.4 Cmax and AD for Taillards 200 and 500 jobs

5
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 java
1.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 it drives the
search into new regions of the best forbidden
solution space which may be considered 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. Adequate
search diversification is possibly the key in the
design of TS heuristics. 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-learningapproach, 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