Minimizing makespan for flow shop scheduling by combining simulated annealing with sequencing knowledge

The present paper reports on a new approach to applying simulated annealing, an analogy between statistical mechanics and combinatorial optimization, to the flow shop scheduling problem. This approach incorporates the simulated annealing methodology with a problem specific knowledge, which is given in a form of index in a ‘Move Desirability for Jobs’ table. Using this index an annealing scheme is proposed where the number of control parameters to be tuned are decreased so that fine tuning of parameters is not required to get high quality solutions. In order to evaluate the proposed method, performance of this method is compared with those of traditional heuristics as well as another simulated annealing scheme developed for the flow shop scheduling problem. From the computational results, it is shown that solutions obtained by the proposed method are superior to those of traditional heuristics and that this method can derive optimum or near-optimum solutions at considerably less computational time than that of the other simulated annealing scheme.