A robust simulated annealing heuristic for flow shop scheduling problems

The flow-shop scheduling problem is one of the most well-known problems in the area of scheduling. The objective of minimising the makespan is often employed as a criterion for flow shop scheduling since Johnson’s work on the subject. The problem is strongly NP-hard and therefore many approximation algorithms have been developed to provide a good solution in reasonable run times. In this research, a mechanism that records the good solution’s characteristics is designed and introduced into simulated annealing to make the searching procedure more robust. Computational experiments show that simulated annealing with a designed mechanism can make the solution quality more robust than it is without the mechanism. In addition, the proposed simulated annealing procedure is also compared with some previously published algorithms in regard to performance. Results show that the proposed simulated annealing procedure performs well with respect to solution and efficiency.