En el presente trabajo se estudio un algoritmo de Búsqueda de Entornos Variables (VNS) básico en el cual el ordenamiento o secuencia de las estructuras de entornos fueron provistas por el método de cuadrados latinos conocido como LHS y seleccionadas mediante un análisis estadístico basado en el ranking del test de Friedman. Dos variantes de VNS básico: VNS-R1 y VNS-R2 en los cuales las estructuras de entornos fueron basadas en un ordenamiento aleatorio para el problema de planificación (scheduling) de máquinas paralelas idénticas sin restricciones fueron contrastadas. Hemos estudiado tal problema a través de cuatro funciones objetivo: la máxima tardanza (Maximum Tardiness: Tmax), la tardanza media (Average Tardiness: Tavg), la tardanza pondera total (Total Weighted Tardiness :Twt) y el número ponderado de tareas tardías (Weighted Number of Tardy Jobs: Nwt). El conjunto de benchmarks usado se divide en ocho escenarios de 125 instancias cada uno. Tales instancias del problema se construyeron en base a datos seleccionados de la ORLibrary correspondientes a problemas de tardanza ponderada. Se obtuvieron los valores de los óptimos conocidos o benchmarks mediante la aplicación de reglas de despacho y heurísticas conocidas en la literatura.Eje: Agentes y Sistemas Inteligentes.Red de Universidades con Carreras en Informática (RedUNCI)