Scheduling blocking flowshops with setup times via constraint guided and accelerated local search

• Published in: Computers & operations research 2019-09, Vol.109, p.64-76
• Main Authors: Newton, M.A. Hakim, Riahi, Vahid, Su, Kaile, Sattar, Abdul
• Format: Article
• Language: English
• Subjects: Acceleration; Algorithms; Blocking constraints; Cider; Combinatorial analysis; Flowshop; Industrial applications; Job shops; Local search; Operations research; Optimization; Permutations; Production scheduling; Scheduling; Search algorithms; Sequential scheduling; Setup times
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/j.cor.2019.04.024

•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. 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.