Parallel hybrid heuristics for the
permutation flow shop problem
M.G. Ravetti, C. Riveros, A. Mendes, M.G.C.
Resende, and P.M. Pardalos
Annals of Operations Research, vol. 199, pp. 269-284, 2012
ABSTRACT
This paper addresses the Permutation Flowshop Problem with minimization of makespan, which is denoted by F|prmu|Cmax.
In the permutational scenario, the sequence of jobs has to remain the
same in all machines. The Flowshop Problem (FSP) is known to be NP-hard
when more than three machines are considered. Thus, for medium and
large scale instances, high quality heuristics are needed to find good
solutions in reasonable time. We propose and analyse parallel hybrid
search methods that fully use the computational power of current
multi-core machines. The parallel methods combine a memetic algorithm
(MA) and severa iterated greedy algorithms (IG) running
concurrently. Two test scenarios were included, with short and long CPU
times. The tests were conducted on the set of benchmark instances
introduced by Taillard in 1993, commonly used to assess the performance
of new methods. Results indicate that the use of the MA to manage a
pool of solutions is highly effective, allowing the improvement of the
best known upper bound for one of the instances.
PDF file of full paper
Go back
Mauricio G.C. Resende's Home Page
Last modified: 19 November 2012
Copyright Notice