El problema investigado en este trabajo es la programación en máquinas paralelas uniformes, teniendo en cuenta que las máquinas pueden estar periódicamente no disponibles durante el horizonte de planificación. El objetivo es determinar la planificación del procesamiento de trabajos de manera que el makespan sea mínimo. El problema se sabe que es NP-duro. Se desarrolló un nuevo modelo cuadrático. Debido a la limitación del modelo mencionado en términos de tamaños de problemas, se desarrolló un algoritmo novedoso para abordar instancias de gran tamaño. Esto consta principalmente de dos fases. La primera fase genera horarios utilizando un procedimiento basado en el Tiempo de Procesamiento más Grande modificado. Luego, estos horarios están sujetos a una mejora adicional durante la segunda fase. Esta mejora se obtiene aplicando simultáneamente intercambios de trabajos por pares entre máquinas. El algoritmo propuesto y el modelo cuadrático fueron implementados y probados en problemas de varios tamaños. Los resultados computacionales mostraron que el modelo cuadrático desarrollado podría resolver óptimamente instancias de problemas de tamaño pequeño a mediano. Sin embargo, el algoritmo propuesto pudo resolver óptimamente problemas de gran tamaño en un tiempo razonable.