New efficient constructive heuristics for the hybrid flowshop to minimise makespan: A computational evaluation of heuristics. (30th December 2018)

• Record Type: Journal Article
• Authors: Fernandez-Viagas, Victor; Molina-Pariente, Jose M.; Framinan, Jose M.
• Is Part Of: Expert systems with applications. Volume 114(2018)
• Page Start: 345
• Page End: 356
• Publication Date: 2018-12-30
• Subjects: Scheduling -- Hybrid flowshop -- Heuristics -- Makespan -- Computational evaluation -- HFS -- Memory-based constructive heuristics; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2018.07.055
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: We address the hybrid flow shop to minimise makespan. We propose two memory-based constructive heuristics. We propose two constructive heuristics based on Johnson's algorithm. We conduct a comprehensive evaluation of a total of 20 heuristics. Abstract: This paper addresses the hybrid flow shop scheduling problem to minimise makespan, a well-known scheduling problem for which many constructive heuristics have been proposed in the literature. Nevertheless, the state of the art is not clear due to partial or non homogeneous comparisons. In this paper, we review these heuristics and perform a comprehensive computational evaluation to determine which are the most efficient ones. A total of 20 heuristics are implemented and compared in this study. In addition, we propose four new heuristics for the problem. Firstly, two memory-based constructive heuristics are proposed, where a sequence is constructed by inserting jobs one by one in a partial sequence. The most promising insertions tested are kept in a list. However, in contrast to the Tabu search, these insertions are repeated in future iterations instead of forbidding them. Secondly, we propose two constructive heuristics based on Johnson's algorithm for the permutation flowshop scheduling problem. The computational results carried out on an extensive testbed show that the new proposals outperform the existing heuristics.