A competitive variable neighbourhood search algorithm for the blocking flow shop problem. (1st January 2013)

• Record Type: Journal Article
• Authors: Ribas, Imma; Companys, Ramon; Tort-Martorell, Xavier
• Is Part Of: European journal of industrial engineering. Volume 7:Number 6 (2013)
• Page Start: 729
• Page End: 754
• Publication Date: 2013-01-01
• Subjects: heuristics -- scheduling -- flow shop -- blocking -- makespan -- variable neighbourhood search -- VNS; Industrial engineering -- Europe -- Periodicals; 658.50094
• Languages: English
• ISSNs: 1751-5254

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.