Este documento investiga un problema de programación de máquinas paralelas uniformes para la minimización del tiempo de finalización. Debido a la NP-dificultad del problema, se ha dirigido mucho esfuerzo de los investigadores hacia la propuesta de algoritmos heurísticos y metaheurísticos que puedan encontrar una solución óptima o casi óptima en un tiempo razonable. Este trabajo propone dos versiones de un algoritmo de búsqueda de vecindario variable con cinco estructuras de vecindario, que difieren en su estrategia de generación de soluciones iniciales. La primera utiliza la regla del tiempo de procesamiento más largo, mientras que la segunda introduce un elemento novedoso al utilizar una regla de tiempo de procesamiento más largo aleatorizada. Las estructuras de vecindario para ambas versiones fueron modificadas de la literatura para tener en cuenta los tiempos de procesamiento variables en máquinas paralelas uniformes. Evaluamos el rendimiento de ambas versiones utilizando un ejemplo numérico, comparándolas con un algoritmo genético y una búsqueda tabu de la literatura existente. Los resultados mostraron que los algoritmos propuestos eran competitivos y obtuvieron la solución óptima con mucho menos esfuerzo. Además, evaluamos el rendimiento de los algoritmos en instancias generadas aleatoriamente. Para instancias de tamaño pequeño, comparamos su rendimiento con respecto a la solución óptima obtenida de una formulación matemática y con respecto a los límites inferiores derivados de la literatura para instancias más grandes. Los resultados computacionales mostraron que la versión con la regla aleatorizada como solución inicial superó a la que tenía la regla como solución inicial. Además, encontró la solución óptima en el 90.19% de las instancias pequeñas y produjo un margen relativo promedio de aproximadamente 0.15% para todos los casos.