Resumen
Variable neighbourhood search (VNS) and all its variants have been successfully proved in hard combinatorial optimization problems. However, there are only few works concerning parallel VNS algorithms, compared with the amount of works devoted to sequential VNS design. In this paper, we propose different parallel designs for the VNS schema. We illustrate the performance of these general strategies by parallelizing a new VNS variant called variable formulation search (VFS). Specifically, we propose six different variants which differ in the VNS stages to be parallelized as well as in the communication mechanisms among processes. We group these variants into three different templates. The first one is oriented to parallelize the whole VNS method. The second one parallelizes the shake and the local search procedures. Finally, the third one explores in parallel the set of predefined neighbourhoods. We test the resulting designs on the cutwidth minimization problem (CMP). Experimental results show that the parallel implementation of the VFS outperforms previous methods in the state of the art for the CMP. This fact is also confirmed by non-parametric statistical tests.
Abraham Duarte
Catedrático de Universidad
Mi carrera investigadora se ha centrado en el desarrollo de nuevos algoritmos y técnicas de Inteligencia Computacional (metaheurísticas) y su aplicación a diferentes problemas en Ciencia e Ingeniería desde que me incorporé a la Universidad Rey Juan Carlos (URJC) en el octubre del año 2000.
Eduardo García Pardo
Catedrático de Universidad
Miembro fundador del grupo de investigación GRAFO, cuya línea de investigación principal es el desarrollo de algoritmos para abordar problemas de optimización, temática sobre la que versa la Tesis Doctoral del investigador y en la que se enmarcan sus publicaciones más destacadas.
Jesús Sánchez-Oro
Profesor Titular de Universidad
Profesor Titular del Departamento de Informática, siendo uno de los investigadores principales del Grupo de Investigación de Algoritmos para la Optimización GRAFO.