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

Abstract

En el presente trabajo se utilizaron metaheurísticas de inspiración biológica como sistemas inmunes artificiales y algoritmos de colonias de hormigas, basados en características y comportamientos de los seres vivos, aplicables en el área computacional. Se presenta una evaluación de soluciones bioinspiradas para el problema de optimización combinatoria de planificación de trabajos, denominado Job shop Scheduling, cuyo objetivo es encontrar una configuración o secuencia de trabajos que requiera la menor cantidad de tiempo para ser ejecutada en las máquinas disponibles. El desempeño de los algoritmos fue caracterizado y evaluado para instancias de referencia del problema de Job Shop Scheduling, comparando la calidad de las soluciones obtenidas respecto a la mejor solución conocida (BKS por sus siglas en inglés) de los métodos más eficaces. Las soluciones fueron valoradas en dos aspectos: en calidad, tomando como referente el makespan, que corresponde al tiempo que tardan en realizarse todos los trabajos, y en cuanto métrica de desempeño, se consideró el número de evaluaciones que realiza el algoritmo para obtener la mejor solución.

Keywords

• algoritmos bioinspirados
• job shop scheduling
• metaheurísticas
• optimización combinatoria
• planificación de tareas