Implementación de un algoritmo inmune artificial aplicado en el área de planificación de recursos

Abstract

Los algoritmos inmunes constituyen un área de investigación en continuo desarrollo y han probado ser de utilidad en la resolución de problemas de calendarización de tareas. El presente trabajo caracteriza el problema de Job Shop Scheduling y muestra la implementación de dos metaheurísticas como respuesta al problema: Enfoque inmune y Enfoque estocástico. En primer lugar se implementó el algoritmo inmune Clonalg, el cual se basa en los mecanismos que generan anticuerpos para la defensa contra los antígenos. Por otra parte se implementó el algoritmo estocástico llamado GRASP que utiliza una fase de construcción de solución factible al que luego se le aplica una fase de búsqueda local con el fin de mejorar la solución. Para obtener los resultados se llevó acabo primero un análisis de sensibilidad, el cual permitió hallar los valores de entrada de cada uno de los algoritmos que permitiera tener un mejor desempeño con respecto al makespan, es decir, que el tiempo que tardaran en terminarse todas las operaciones del calendario estuviera cerca al BKS (Best Known Solution o Mejor Solución Conocida) hallados en la literatura. Adicionalmente, se compararon los resultados obtenidos de los algoritmos, y se concluyó que de dichos resultados, los obtenidos del algoritmo de Clonalg presentan una menor dispersión y a su vez los resultados del makespan se acercan más al BKS en Clonalg que en GRASP. Finalmente, se planteó un escenario que permite optimizar el proceso de prueba para instancias de Lawrence del algoritmo Clonalg.