In this paper the authors present their experience in using both heuristic and randomly generated solutions as initial seeds to a simulated annealing optimisation process which they propose for solving (approximately) the n-job, m-machine flowshop scheduling problem with minimum completion time (makespan) as the measure of performance. Two neighbourhood search routines are employed as perturbation schemes and the authors compare their performance. They show that for the proposed simulated annealing algorithm, the choice of a perturbation technique affects the quality of the final solution. In particular, a neighbourhood search technique that yields a large neighbourhood will perform better than one with a smaller neighbourhood. The proposed simulated annealing process is shown to provide as good quality solutions as the conventional (Metropolis) scheme (where the acceptance probability depends on the change in objective function); however it does this in less computation time. Finally, the authors compare the performance of the proposed annealing process with a repetitive iterative improvement algorithm to investigate the benefits since it has been shown that both algorithms asymptotically converge to global optima. It is found that the proposed simulated annealing algorithm provides better solutions than repeated iterative improvement algorithm, for a fixed total computational time.
