A revised simulated annealing algorithm for obtaining the minimum total tardiness in job shop scheduling problems

This paper applies a revised configuration generation mechanism of the Simulated Annealing (SA) algorithm to obtain the minimum total tardiness in job shop scheduling problems. In addition to always generating feasible configurations, this revised mechanism can also exclude some cost non-decreasing configurations in advance. The revised SA method is also compared with a more tailored algorithm (MEHA) and two other SA approaches. Computational results indicate that the solution quality of the SA approaches outperform MEHA. Among the three SA approaches, the revised SA has the best performance. Moreover, the SA approaches differ insignificantly in terms of computational time.