MINIMIZING MAKESPAN FOR FLOW-SHOP SCHEDULING BY COMBINING SIMULATED ANNEALING WITH SEQUENCING KNOWLEDGE

The present paper reports on a new approach to applying simulated anne aling, an analogy between statistical mechanics and combinatorial opti mization, to the flow shop scheduling problem. This approach incorpora tes the simulated annealing methodology with a problem specific knowle dge, which is given in a form of index in a 'Move Desirability for Job s' table. Using this index an annealing scheme is proposed where the n umber of control parameters to be tuned are decreased so that fine tun ing of parameters is not required to get high quality solutions. In or der to evaluate the proposed method, performance of this method is com pared with those of traditional heuristics as well as another simulate d annealing scheme developed for the flow shop scheduling problem. Fro m the computational results, it is shown that solutions obtained by th e proposed method are superior to those of traditional heuristics and that this method can derive optimum or near-optimum solutions at consi derably less computational time than that of the other simulated annea ling scheme.