Un algoritmo genético para el problema de Job Shop Flexible

A genetic algorithm for the Flexible Job Shop problem

En este estudio se propone e implementa computacionalmente un algoritmo genético secuencial pararesolver el problema del Job Shop Flexible (existente en la Gestión de Operaciones), el cual es parte dela familia de los problemas de programación de tareas o trabajos (Scheduling) en un taller que funcionaa pedido. Surge como una generalización del problema del Job Shop y permite optimizar el uso de losrecursos (máquinas) con mayor flexibilidad, ya que cada máquina puede realizar más de una operación. Esteproblema ha sido estudiado por numerosos autores, los que han propuesto diversos modelos matemáticosy enfoques heurísticos. Debido a la naturaleza combinatoria, los métodos exactos que resuelven modelosmatemáticos encuentran soluciones sólo para instancias pequeñas o simples del problema mencionado.Los resultados muestran la efectividad del algoritmo propuesto para entregar buenas soluciones en tiemposcomputacionales razonables en más de 130 instancias encontradas en la literatura.

INTRODUCCIÓN

En la programación de la producción de las industrias manufactureras se debe decidir sobre la asignación de los recursos a las tareas o trabajos para optimizar, uno o más objetivos en el corto plazo. Para apoyar estas decisiones tradicionalmente se utiliza el modelo de Job Shop, el cual considera un conjunto de máquinas y un conjunto de trabajos compuestos por una secuencia ordenada de operaciones que se deben procesar en las máquinas con el objetivo de minimizar, entre otros, el tiempo de completación de la última operación, makespan.

El problema de Job Shop Flexible es una generalización del problema de Job Shop. Considera que las operaciones pueden ser procesadas por un grupo de máquinas, razón por la cual también se requiere decidir sobre cuáles de las máquinas procesan cada operación.

Por ejemplo, consideremos un taller metal-mecánico, en el que se reciben dos trabajos compuestos por una secuencia fija de tres operaciones a realizar en tres máquinas. El primero requiere las operaciones de perforar, ranurar y pulir, mientras el segundo trabajo requiere cortar, limar y perforar. El taller dispone de un torno, que puede realizar las operaciones de perforar, pulir y cortar; una fresadora que puede perforar, ranurar, pulir y limar; y un taladro que puede perforar, ranurar y cortar. Los tiempos de las operaciones varían en las distintas máquinas, entonces, es necesario decidir cuál máquina realiza cada operación y en qué orden, con el objetivo de minimizar el tiempo total de completación de todos

los trabajos.

Este problema pertenece a la clase de problemas denominados de NP-Difíciles, para los cuales aún no se disponen de algoritmos de resolución eficientes que los ejecuten en tiempos computacionales razonables, sobre todo para instancias grandes y/o complejas.