Solución al "flexible job shop problem" con tiempos de alistamiento dependientes de la secuencia mediante un algoritmo híbrido genético

Abstract

En la presente investigación se aborda el problema de programación de operaciones que involucra la secuenciación y asignación de máquinas, denominado en la literatura como Flexible Job Shop Problem con Tiempos de Alistamiento Dependientes de la Secuencia (SDST-FJSP), este problema es considerado NP.Hard. Es uno de los problemas que tiene gran relevancia porque se aproxima a ambientes reales de producción donde es necesario tener en cuenta que después de una determinada operación se requiera realizar un ajuste de herramientas, trasladar un producto, limpieza, entre otras actividades de alistamiento. Para dar solución a este problema se diseñó un Algoritmo Hibrido Genético donde parte de la población inicial se generó mediante la metaheurística Recocido Simulado, el criterio de selección utilizado fue la selección por torneo, se utilizaron dos tipos de operadores de cruce uno que modifica la secuencia de las operaciones, cruce POX (Precedence Preserving Order-based )y otro para la asignación de las máquinas, cruce de dos puntos y por último el operador de mutación que modifica la secuencia de las operaciones respetando las restricciones de precedencia PPS (Precedence Preserving Shift). Se realizó un diseño de experimentos 23 con el fin de determinar cómo influyen los factores en la variable respuesta Makespan dando como resultado que el factor tamaño de población tenía efecto significativo sobre el Makespan. Finalmente se validó el algoritmo propuesto con 20 instancias de la literatura y se comparó con diferentes metodologías propuestas por diversos autores, dando como resultado buenas soluciones en las instancias de menor tamaño. Sin embargo para las instancias de mayor tamaño el algoritmo presenta dificultad para encontrar buenas soluciones comparado con la mejor solución encontrada.