A beam-search-based constructive heuristic for the PFSP to minimise total flowtime. (May 2017)

• Record Type: Journal Article
• Authors: Fernandez-Viagas, Victor; Framinan, Jose M.
• Is Part Of: Computers & operations research. Volume 81(2017)
• Page Start: 167
• Page End: 177
• Publication Date: 2017-05
• Subjects: Scheduling -- Flowshop -- Heuristics -- Flowtime -- PFSP -- Beam search -- Total completion time; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2016.12.020
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: In this paper we present a beam-search-based constructive heuristic to solve the permutation flowshop scheduling problem with total flowtime minimisation as objective. This well-known problem is NP-hard, and several heuristics have been developed in the literature. The proposed algorithm is inspired in the logic of the beam search, although it remains a fast constructive heuristic. The results obtained by the proposed algorithm outperform those obtained by other constructive heuristics in the literature for the problem, thus modifying substantially the state-of-the-art of efficient approximate procedures for the problem. In addition, the proposed algorithm even outperforms two of the best metaheuristics for many instances of the problem, using much lesser computation effort. The excellent performance of the proposal is also proved by the fact that the new heuristic found new best upper bounds for 35 of the 120 instances in Taillard's benchmark.