Un algoritmo de búsqueda de ardilla discreto aplicado al problema Job Shop con operadores calificados

Abstract

La complejidad de algunos problemas de optimización motiva el uso de métodos de solución alternativos; que brinden soluciones de alta calidad cuando se aborden problemas de gran tamaño. En este orden de ideas, se propone adaptar una metaheurística para solucionar el problema Job Shop con operadores calificados o Job Shop Scheduling With Operators (JSSO); esta, considera el movimiento de las ardillas al buscar alimento y se conoce como el Algoritmo Búsqueda De Ardillas o Squirrel Search Algorithm (SSA) propuesta en (Jain, Singh, & Rani, 2019). Es una metaheurística bioinspirada, clasificada dentro del grupo de los algoritmos de inteligencia de enjambres o Swarm Intelligence (SI).El problema JSSO, es una extensión del problema clásico de programación de producción Job Shop, en donde, los trabajos siguen una relación de precedencias, cada trabajo dispone tanto de un recurso maquina como de mano de obra, para que sea ejecutada en un periodo de tiempo definido, con el objetivo de minimizar el tiempo de terminación total de los trabajos o Makespan. Es un problema de optimización combinatoria complejo catalogado como NP - HARD.