Departamento de Computación

Los problemas de planificación de recursos son muy importantes en el mundo real. Se puede decir que se emplean en todos lados, de ahí la importancia de que éstos sean óptimos, de forma que se puedan ahorrar recursos que están asociados al problema. En esta tesis se propone un algoritmo inspirado en el sistema inmune artificial para resolver el problema denominado Job Shop Scheduling (JSSP). El algoritmo propuesto se basa en el principio de selección clonal y utiliza expansión clonal así como hipermutación somática. También se incorpora un mecanismo que permite explorar la vecindad de la mejor solución, con lo que se logra una mejora significativa de resultados. El algoritmo propuesto utiliza una codificación basada en permutaciones con repeticiones. Esta es una representación muy sencilla y compacta, para la cual se diseñó un operador de mutación ad-hoc. El uso de esta codificación distingue a este trabajo de otros en los que tradicionalmente se han utilizado codificaciones basadas en grafos, permutaciones simples y llaves aleatorias, entre otras. Se hace un análisis detallado de los resultados obtenidos, comparando el algoritmo propuesto en esta tesis con respecto a otras heurísticas reportadas en la literatura especializada. Se hacen comparaciones con respecto a un algoritmo genético simple (AG), un algoritmo genético híbrido (HGA), un procedimiento de búsqueda miopealeatoria y adaptativa (GRASP) en dos versiones y una búsqueda tabú. Los resultados obtenidos indican que el algoritmo propuesto en esta tesis es una alternativa viable para resolver el JSSP, dada la calidad de las soluciones obtenidas, así como su costo computacional respectivo. Su unico contendiente serio (de entre las heurísticas comparadas) es la búsqueda tabú.