Scheduling blocking flowshops with setup times via constraint guided and accelerated local search. (September 2019)

• Record Type: Journal Article
• Authors: Newton, M.A. Hakim; Riahi, Vahid; Su, Kaile; Sattar, Abdul
• Is Part Of: Computers & operations research. Volume 109(2019)
• Page Start: 64
• Page End: 76
• Publication Date: 2019-09
• Subjects: Scheduling -- Flowshop -- Setup times -- Blocking constraints -- Local search; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2019.04.024
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: Studying mixed blocking flowshop scheduling problems with sequence-dependent setup times (PFSP-BS). A new acceleration method to compute makespan for each solution in the insertion neighbourhood. A constraint-guided local search algorithm to solve PFSP-BS instances. Comprehensive numerical and statistical tests to evaluate the proposed methods. Abstract: Permutation flowshop scheduling problem (PFSP) is a classical NP-Hard combinatorial optimisation problem. Existing PFSP variants capture different realistic scenarios, but significant modelling gaps still remain with respect to many real-world industrial applications. Inspired by the cider industry, in this paper, we propose a new PFSP variant that generalises over simultaneous use of several types of blocking constraints and various settings of sequence-dependent setup times. We also present a computational model for makespan minimisation of the new variant and show that solving this variant remains NP-Hard. For this PFSP variant, we then present an acceleration method to compute makespan efficiently and thus evaluate the neighbourhoods generated by insertion operators. We develop a new constructive heuristic taking both blocking constraints and setup times into account. We also develop a new local search algorithm that uses a constraint guided intensification method and a random-path guided diversification method. Our comprehensive experimental results on a set of benchmark instances demonstrate that our proposed algorithms significantly outperform several state-of-the-art adapted algorithms.