A novel hybrid meta-heuristic algorithm for a no-wait flexible flow shop scheduling problem with sequence dependent setup times

Abstract

In this paper, we contemplate the problem of scheduling a set of n jobs in a no-wait flexible flow shop manufacturing system with sequence dependent setup times to minimising the maximum completion time. With respect to NP-hardness of the considered problem, there seems to be no avoiding application of metaheuristic approaches to achieve near-optimal solutions for this problem. For this reason, three novel metaheuristic algorithms, namely population based simulated annealing (PBSA), adapted imperialist competitive algorithm (AICA) and hybridisation of adapted imperialist competitive algorithm and population based simulated annealing (AICA + PBSA), are developed to solve the addressed problem. Because of the sensitivity of our proposed algorithm to parameter's values, we employed the Taguchi method as an optimisation technique to extensively tune different parameters of our algorithm to enhance solutions accuracy. These proposed algorithms were coded and tested on randomly generated instances, then to validate the effectiveness of them computational results are examined in terms of relative percentage deviation. Moreover, some sensitive analyses are carried out for appraising the behaviour of algorithms versus different conditions. The computational evaluations manifestly support the high performance of our proposed novel hybrid algorithm against other algorithms which were applied in literature for related production scheduling problems.

Keywords:

• no-wait
• flexible flow shop
• ICA
• PBSA
• Taguchi

Acknowledgements

We express our warmest thanks to John Middle, Editor-in-Chief, for communicating the paper, and his useful suggestions. We also are grateful for the valuable comments and suggestions from the anonymous reviewers which have enhanced the quality of our paper. The authors would like to acknowledge the financial support of the University of Tehran for this research under grant number 8109003/1/06.