Estudio comparativo de métodos heurísticos para programación de trabajos a gran escala sobre máquinas heterogéneas en paralelo

Abstract

En este trabajo, se compara el desempeño de dos algoritmos heurísticos para la programación de trabajos a gran escala sobre máquinas no idénticas en paralelo (Parallel Machine Scheduling - PMS). Se presenta de forma genérica la evolución, tanto del problema de scheduling como de los métodos aplicados para su solución. Se revisan una serie de trabajos recientes sobre PMS principalmente de algoritmos heurísticos. Actualmente, la globalización de la economía y la tendencia de los clientes a individualizarse, han generado un escenario de lotes de producción más pequeños con múltiples variantes del producto, lo que se traduce en la necesidad cada vez mayor de casos de scheduling de gran escala, con cientos o miles de trabajos por programar. Por tanto, el problema de obtener soluciones aceptables en tiempos razonables, se torna crítico para que las empresas puedan ajustar y modificar, cada vez con mayor frecuencia, sus programas de producción. En este contexto, en este trabajo, se revisan e implementan a nivel experimental, el algoritmo Greedy Iterativo de Ying-Cheng y el algoritmo Genético de Savas. Se analiza como varía la calidad de la solución a medida que la carga de trabajos se incrementa desde 100 hasta 5000 trabajos. La variable aplicada para representar la calidad de la solución es el Atraso Máximo. El estudio realizado revela que el algoritmo Greedy Iterativo de Ying-Cheng se desempeña con ventaja cuando el número de trabajos tiende a ser mucho mayor. La investigación realizada evidencia que existe un amplio campo de estudio sobre temas de scheduling.