The application of the simulated annealing algorithm to the solution of the \(n/m/C_{\max}\) flowshop problem (Q909574)

The n-job, m-machine flowshop sequencing problem is one of the popular scheduling problems. In this problem, the n jobs must be processed in the same order by each of the m machines and the objective is to minimize the processing time. Since the problem is NP-complete, efforts are geared towards developing heuristic algorithms. The simulated annealing algorithm is a heuristic with iterative improvement derived by a natural analogy with the statistical mechanics of condensed matter physics. The algorithm generally accepts all solutions that improve the objective function, while those which do not result in improvements may be accepted with non-zero probabilities. However, with certain assumptions, the algorithm converges asymptotically with probability 1 to the global optimum. The authors propose a modified simulated annealing algorithm for the j- job, m-machine flowshop sequencing problem. Their computational experiences show that the modified algorithm finds the same good quality solution in less time than the original algorithm. Their experiences also show that in the same time the modified algorithm finds better solutions than the repeated iterative improvement algorithm.