Una variante colaborativa de la búsqueda de vecindarios variables para el problema de planificación de máquinas paralelas

Abstract

VNS (Variable Neighborhood Search) es una metaheurística de trayectoria que usa diferentes estructuras de vecindarios siguiendo algún criterio preestablecido para realizar la búsqueda. En este trabajo se propone una variante del esquema básico de VNS estándar (o simplemente VNS) para mejorar su desempeño introduciendo un cambio en la secuencia de aplicación de las estructuras de vecindarios y/ o mecanismos de exploración, considerando el Problema de Planificación de Máquinas Paralelas. La variante propuesta consiste en una Búsqueda de Vecindarios Colaborativa: VNS+C, en la cual existen dos algoritmos VNS que cooperan en la búsqueda del óptimo global. Los resultados muestran que la variante colaborativa VNS+C, mejora el desempeño de VNS para los conjuntos de instancias del estudio experimental.