Implementación de algoritmos bioinspirados para la solución del problema de planificación de trabajos

Abstract

El problema de Job shop Scheduling (JSP) o planificación de tareas, es un problema de gran interés para la industria que se encuentra distribuido en múltiples escenarios, como la gestión de proyectos, gestión de producción de bienes, gestión de sistemas computacionales distribuidos, telecomunicaciones entre otras. Una de sus principales características es su naturaleza combinatoria y su complejidad, NP-Hard, la cual implica altos costos computacionales. Por tanto, se hace necesario abordar este tipo de problemáticas por medio de métodos que a pesar de que no encuentren soluciones óptimas en la mayoría de los casos, produzcan aproximaciones competitivas, a este tipo de métodos se les denomina metaheurísticas. Éstas garantizan soluciones aproximadas, y reducen el consumo de recursos de cómputo. Para esta investigación se utilizaron metaheurísticas de inspiración biológica, como sistemas inmunes artificiales y los algoritmos de colonias de hormigas que parten de una serie de características y comportamientos de los seres vivos que son interesantes en el área computacional. El desempeño de los algoritmos fue caracterizado y evaluado para instancias de referencia del problema de job shop schedu-ling, comparando la calidad de las soluciones obtenidas respecto a la mejor solución conocida de los métodos más eficaces. Adicional se desarrolló una aproximación a un escenario real en el campo de planificación y gestión de los recursos de cómputo en clústeres de computadores Las soluciones fueron de buena calidad competitivas frente a la literatura y obtenidas con una destacable eficiencia al tener que realizar un número muy bajo de evaluaciones de la función objetivo.