VNS Variant Approach Metaheuristics for Parallel Machines Scheduling Problem

VNS (Variable Neighborhood Search) is a trajectory metaheuristic that uses different neighborhood structures following some pre-established criteria to perform the search. In this work, variants of the standard VNS (or simply VNS) are proposed to improve its performance by introducing changes in the order of their application, neighborhood sequences used, and/or exploration mechanisms considering the Parallel Machines Scheduling Problem to minimize the Maximum Tardiness. The proposed variants are VNS+R (VNS Random) with random neighborhood selection; VNS+LHS (VNS Latin Hypercube Sample) with pre-selection of neighborhoods through Latin Squares; VNS+E (VNS Exploratory) which intensifies the exploration of the search space and finally, VNS+ER (VNS Exploratory &Random) which combines functional aspects of both VNS+R and VNS+E. The results show that the variants that intensify the exploration in the search space, and the variant with the scheme of Latin squares, improve the performance of VNS.