A computational evaluation of constructive and improvement heuristics for the blocking flow shop to minimise total flowtime. (1st November 2016)

• Record Type: Journal Article
• Authors: Fernandez-Viagas, Victor; Leisten, Rainer; Framinan, Jose M.
• Is Part Of: Expert systems with applications. Volume 61(2016)
• Page Start: 290
• Page End: 301
• Publication Date: 2016-11-01
• Subjects: Scheduling -- Flowshop -- Blocking -- Heuristics -- PFSP -- Total flowtime -- Computational evaluation -- Beam search; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2016.05.040
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: We address the blocking flow shop to minimise total flowtime. We conduct a comprehensive evaluation of a total of 35 heuristics. We propose an efficient constructive heuristic using a beam-search-based approach. We compare the proposal with the best-so-far algorithms for the problem. Abstract: This paper focuses on the blocking flow shop scheduling problem with the objective of total flowtime minimisation. This problem assumes that there are no buffers between machines and, due to its application to many manufacturing sectors, it is receiving a growing attention by researchers during the last years. Since the problem is NP-hard, a large number of heuristics have been proposed to provide good solutions with reasonable computational times. In this paper, we conduct a comprehensive evaluation of the available heuristics for the problem and for related problems, resulting in the implementation and testing of a total of 35 heuristics. Furthermore, we propose an efficient constructive heuristic which successfully combines a pool of partial sequences in parallel, using a beam-search-based approach. The computational experiments show the excellent performance of the proposed heuristic as compared to the best-so-far algorithms for the problem, both in terms of quality of the solutions and of computational requirements. In fact, despite being a relative fast constructive heuristic, new best upper bounds have been found for more than 27% of Taillard's instances.