Efficient heuristics for the hybrid flow shop scheduling problem with missing operations. (January 2018)

• Record Type: Journal Article
• Authors: Dios, Manuel; Fernandez-Viagas, Victor; Framinan, Jose M.
• Is Part Of: Computers & industrial engineering. Volume 115(2018)
• Page Start: 88
• Page End: 99
• Publication Date: 2018-01
• Subjects: Scheduling -- Hybrid flow shop -- Missing operations -- Manufacturing -- Heuristics; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2017.10.034
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: We address the HFS scheduling problem with missing operations (makespan objective). We carry out a hardness analysis of the problem to analyse its behaviour. We conduct a comprehensive evaluation of 56 heuristics. We propose a set of efficient improvement heuristics. We compare our proposal with the best-so-far algorithms for the problem. Abstract: In this paper, we address the hybrid flowshop scheduling problem for makespan minimisation. More specifically, we are interested in the special case where there are missing operations, i.e. some stages are skipped, a condition inspired in a realistic problem found in a plastic manufacturer. The main contribution of our paper is twofold. On the one hand we carry out a computational analysis to study the hardness of the hybrid flowshop scheduling problem with missing operations as compared to the classical hybrid flowshop problem. On the other hand, we propose a set of heuristics that captures some special features of the missing operations and compare these algorithms with already existing heuristics for the classical hybrid flowshop, and for the hybrid flowshop problem with missing operations. The extensive computational experience carried out shows that our proposal outperforms existing methods for the problem, indicating that it is possible to improve the makespan by interacting with the jobs with missing operations.