Parameter analysis of variable neighborhood search applied to multiprocessor scheduling with communication delays

Abstract

When dealing with hard, real-life optimization problems, metaheuristic methods are considered a very powerful tool. If designed properly, they can provide high-quality solutions in reasonable running times. We are specially interested in Variable neighborhood search (VNS), a very popular metaheuristic for more than 20 years with many successful applications. Its basic form has a small number of parameters, however, each particular implementation can involve a problem-dependent set of parameters. This makes parameter analysis and performance assessment a challenging task. Contribution of this work is twofold: we develop a new variant of the VNS algorithm for the considered optimization problem and simplify the methodology for experimental analysis of metaheuristic algorithms. We conclude three stages of the parameter analysis: parameter definition, deciding the most influential parameters and analysis of their relationship. The analysis contributes to the design of VNS as a search problem in the space of its parameters. We apply the sophisticated approach that equally relies on visual as well as on the statistical and machine learning methods that have become standard practice for parameter tuning and experimental evaluation of metaheuristic algorithms. The obtained results are presented and discussed in this study.