A variant of simulated annealing to solve unrestricted identical parallel machine scheduling problems

Abstract

In this paper we propose a modification to the Simulated Annealing (SA) basic algorithm that includes an additional local search cycle after finishing every Metropolis cycle. The added search finishes when it improves the current solution or after a predefined number of tries. We applied the algorithm to minimize the Maximum Tardiness objective for the Unrestricted Parallel Identical Machines Scheduling Problem for which no benchmark have been found in the literature. In previous studies we found, by using Genetic Algorithms, solutions for some adapted instances corresponding to Weighted Tardiness problem taken from the OR-Library. The aim of this work is to find improved solutions (if possible) to be considered as the new benchmark values and make them available to the community interested in scheduling problems. Evidence of the improvement obtained with proposed approach is also provided.