Article: A competitive variable neighbourhood search algorithm for the blocking flow shop problem Journal: European Journal of Industrial Engineering (EJIE) 2013 Vol.7 No.6 pp.729 - 754 Abstract: This paper analyses the performance of two variable neighbourhood search (VNS) methods for the Fm | block | C<SUB align="right"><SMALL>max</SMALL></SUB> problem. The main difference between both is the strategy used to change the neighbourhood in the improvement phase. The first strategy, named parallel version, randomly chooses between swap and insertion neighbourhoods to improve the solution. The second strategy, named serial version, begins the search in one of the neighbourhoods and continues the search in the other one. Additionally, we have analysed and improved the effectiveness of several NEH-based procedures to generate the initial solution. Moreover, we have tested each VNS strategy with two types of local search which led us to define four procedures that were tested with the Taillard benchmark and with a test-bed created ad hoc. The computational evaluation showed that these algorithms and especially the serial VNS which uses PW/PWE2 to generate the initial solution would be very competitive. [Received 3 July 2011; Revised 28 November 2011; Revised 14 April 2012; Accepted 29 April 2012] Inderscience Publishers - linking academia, business and industry through research

Title: A competitive variable neighbourhood search algorithm for the blocking flow shop problem

Authors: Imma Ribas; Ramon Companys; Xavier Tort-Martorell

Addresses: Departamento de Organización de Empresas, Universidad Politécnica de Catalunya BarcelonaTech, Avda, Diagonal, 647, planta 7, 08028 Barcelona, Spain ' Departamento de Organización de Empresas, Universidad Politécnica de Catalunya BarcelonaTech, Avda, Diagonal, 647, planta 7, 08028 Barcelona, Spain ' Departamento de Estadística y Investigación Operativa, Universidad Politécnica de Catalunya BarcelonaTech, Avda, Diagonal, 647, planta 6, 08028 Barcelona, Spain

Abstract: This paper analyses the performance of two variable neighbourhood search (VNS) methods for the Fm | block | C_max problem. The main difference between both is the strategy used to change the neighbourhood in the improvement phase. The first strategy, named parallel version, randomly chooses between swap and insertion neighbourhoods to improve the solution. The second strategy, named serial version, begins the search in one of the neighbourhoods and continues the search in the other one. Additionally, we have analysed and improved the effectiveness of several NEH-based procedures to generate the initial solution. Moreover, we have tested each VNS strategy with two types of local search which led us to define four procedures that were tested with the Taillard benchmark and with a test-bed created ad hoc. The computational evaluation showed that these algorithms and especially the serial VNS which uses PW/PWE2 to generate the initial solution would be very competitive. [Received 3 July 2011; Revised 28 November 2011; Revised 14 April 2012; Accepted 29 April 2012]

Keywords: heuristics; flow shop scheduling; blocking flow shops; makespan; variable neighbourhood search; VNS.

DOI: 10.1504/EJIE.2013.058392

European Journal of Industrial Engineering, 2013 Vol.7 No.6, pp.729 - 754

Published online: 28 Feb 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article

Title: A competitive variable neighbourhood search algorithm for the blocking flow shop problem

Keep up-to-date