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


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