VNS (Variable Neighborhood Search) es una metaheurística de trayectoria y usa diferentes estructuras de vecindarios siguiendo algún criterio pre-establecido para realizar la búsqueda. En este trabajo se proponen variantes de VNS estándar (o simplemente VNS) para mejorar su desempeño introduciendo cambios en las secuencias de vecindarios utilizadas y/o mecanismos de exploración considerando el problema de Planificación de Máquinas Paralelas. Las variantes propuestas son: VNS+R (VNS Random) con selección de vecindario aleatoria; VNS+LHS (VNS Latin Hypercube Sample) con preselección de vecindarios a través de Cuadrados Latinos; VNS+E (VNS Exploratory) que intensifica la exploración del espacio de búsqueda y por último, VNS+ER (VNS Exploratory&Random) que combina aspectos funcionales de VNS+R y VNS+E. Los resultados muestran que las variantes que intensifican la exploración en el espacio de búsqueda con selección aleatoria de estructuras de vecindario, mejoran al desempeño de VNS, variante representada por el algoritmo VNS+ER.XXIII Workshop agentes y sistemas inteligentes (WASI)Red de Universidades con Carreras en Informática