Applying a hybrid simulated annealing and tabu search approach to non-permutation flowshop scheduling problems

Abstract

Researchers have indicated that a permutation schedule can be improved by a non-permutation schedule in a flowshop with completion time-based criteria, such as makespan and total completion time. This study proposes a hybrid approach which draws on the advantages of simulated annealing and tabu search for the non-permutation flowshop scheduling problem, in which the objective function is the makespan of the schedule. To verify the effectiveness of the proposed hybrid approach, computational experiments are performed on a set of well-known non-permutation flowshop scheduling benchmark problems. The result shows that the performance of the hybrid approach is better than that of other approaches, including ant colony optimisation, simulated annealing, and tabu search. Further, the proposed approach found new upper bound values for all benchmark problems within a reasonable computational time.

Keywords:

• scheduling
• non-permutation flowshop
• hybrid approach
• simulated annealing
• tabu search

Acknowledgements

The authors are grateful to Ebru Demirkol, Sanyay Mehta, and Reha Uzsoy for making their benchmark problems available for this study. The authors also thank the anonymous referees for their valuable suggestions and comments.