Modified simulated annealing algorithms for the flow-shop sequencing problem

In this paper, two simulated annealing algorithms with a modified generation mechanism are proposed and applied to the m-machine and n-job flow shop sequencing problem with the objective of minimizing the makespan. The generation mechanism is modified in order to obtain robust performance with respect to the choice of a cooling schedule. By computer simulations on randomly generated test problems, it is shown that the performance of the proposed algorithms is less sensitive to the choice of a cooling schedule than that of the standard simulated annealing algorithm. The proposed algorithms are also compared with other heuristics such as two multi-start descent algorithms, two tabu search algorithms and a random sampling technique.