Parallel hybrid heuristics for the permutation flow shop problem

Martín Ravetti (), Carlos Riveros (), Alexandre Mendes (), Mauricio Resende () and Panos Pardalos ()

Annals of Operations Research, 2012, vol. 199, issue 1, 269-284

Abstract: This paper addresses the Permutation Flowshop Problem with minimization of makespan, which is denoted by Fm|prmu|C max . 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 several 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 (Eur. J. Oper. Res. 64:278–285, 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. Copyright Springer Science & Business Media, LLC 2012

Keywords: Metaheuristics; Memetic algorithms; Flowshop problem; Combinatorial optimization; Scheduling (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-011-1056-3 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:199:y:2012:i:1:p:269-284:10.1007/s10479-011-1056-3

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-011-1056-3

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().