Análise de estruturas de vizinhança para o problema de sequenciamento de máquinas paralelas não relacionadas com tempos de preparação

Abstract

Local search heuristics are usually employed in the optimization of parallel machine scheduling problems, particularly those in which setup times are considered. Neighborhood structures represent a central aspect of these heuristics, enabling them to adequately explore the search space. This work presents an exploratory statistical analysis of six neighborhood structures commonly used for the unrelated parallel machine scheduling problem with sequence dependent setup times, in which the main objective is the minimization of the makespan. The neighborhood structures are equipped on a specific implementation of Simulated Annealing that is considered state-of-the-art for this particular problem, and are explored at different stages of the search. The results indicate the superiority of one neighborhood concerning the others. Besides, the results obtained are used to fit a regression model capable of providing quantitative guidelines for the selection of each structure at different stages of the search. The resulting model is used to devise a modified version of the Simulated Annealing in which an adaptive approach for neighborhood selection is employed when solving instances belonging to this particular problem class. The results obtained with the modified Simulated Annealing overcome the original one. From the experiment, the proposition of new heuristics based on local search can take advantage of the analysis performed in this paper to prioritize the choice of neighborhoods and when to use them.