A simulated annealing algorithm for the unrelated parallel machine scheduling problem

The problem addressed in this paper is scheduling jobs on unrelated parallel machines with sequence-dependent setup times to minimize the maximum completion time (i.e., the makespan). This problem is NP-hard even without including setup times. Adding sequence-dependent setup times adds another dimension of complexity to the problem and obtaining optimal solutions becomes very difficult especially for large problems. In this paper a simulated annealing (SA) algorithm is applied to the problem at hand to reach near-optimum solution. The effectiveness of the simulated annealing algorithm is measured by comparing the quality of its solutions to optimal solutions for small problems. The results show that the SA efficiently obtained optimal solutions for all test problems.