Scheduling blocking flowshops with setup times via constraint guided and accelerated local search. (September 2019) - Newton, M.A. Hakim; Riahi, Vahid; Su, Kaile; Sattar, Abdul
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.