An efficient configuration generation mechanism to solve job shop scheduling problems by the simulated annealing algorithm

This paper uses the simulated annealing algorithm to solve job shop scheduling problems, thereby minimizing the total tardiness. Also presented here is a configuration generation mechanism capable of excluding all of the infeasible configurations before-hand. Doing so allows us to increase the efficiency of the annealing process. In addition, the simulated annealing algorithm is compared with a more tailored algorithm (MEHA), indicating that the solution quality of the former significantly outperforms the latter. Moreover, the simulated annealing algorithm, although using more computational time than MEHA, has a high solution quality and can be easily implemented.