Implementación de un algoritmo de colonia de hormigas aplicado en el área de planificación de recursos

Abstract

Las metaheurísticas son las mejores técnicas para solucionar los problemas de optimización, entre las cuáles se destaca la Optimización basada en Colonia de Hormigas (OCH), que ha probado ser muy eficiente y efectiva en problemas de gran complejidad (NP-hard) en optimización combinatoria. En este trabajo de grado se describe la implementación de un algoritmo del modelo OCH conocido como Elitist Ant System (EAS), aplicado al problema de planificación de recursos denominado Job Shop Scheduling Problem (JSP). Se propone un método que busca reducir los retardos designando la operación disponible inmediatamente, pero teniendo en cuenta a las operaciones que les falta poco para estar disponibles y tienen una gran cantidad de feromona, porque son buenas candidatas. El desempeño del algoritmo fue evaluado para problemas de referencia en JSP, comparando la calidad de las soluciones obtenidas respecto a GRASP y a la mejor solución conocida para estos problemas. Las soluciones con OCH fueron de buena calidad (con 96% de aproximación a la mejor solución conocida), obtenidas con una destacable eficiencia al tener que realizar un número muy bajo de evaluaciones de la función objetivo. Por último, se planteó un escenario de aplicación del JSP en los sistemas distribuidos, donde se realizó la planificación de trabajos en los nodos de un clúster.