Aplicación de un algoritmo ACO al problema de taller de flujo de permutación con tiempos de preparación dependientes de la secuencia y minimización de makespan

An ant colony algorithm for the permutation flowshop with sequence dependent setup times and makespan minimization

En este trabajo se estudió el problema de secuenciamiento de trabajos en el taller de flujo de permutacióncon tiempos de preparación dependientes de la secuencia y minimización de makespan. Para ello se propuso un algoritmo de optimización mediante colonia de hormigas (ACO), llevando el problema original a una estructura semejante al problema del vendedor viajero TSP (Traveling Salesman Problem) asimétrico,utilizado para su evaluación de problemas propuestos en la literatura y se compara con una adaptaciónde la heurística NEH (Nawaz-Enscore-Ham). Posteriormente se aplica una búsqueda en vecindad a la solución obtenida tanto por ACO como NEH.

INTRODUCCIÓN

En un sistema de manufactura, la disposición de la maquinaria define el tipo de configuración productiva necesaria para realizar el proceso de transformación. Las necesidades de los clientes se traducen en órdenes de trabajo que se liberan y "transforman" en trabajos con fecha de entrega asociada. La programación de producción se preocupa de la asignación de recursos limitados a tareas productivas, y debe realizarse de manera detallada para mantener la eficiencia y el control de las operaciones dentro del sistema productivo y así constituir una ventaja competitiva difícil de imitar (ver, por ejemplo, [1-2]).

Los distintos productos requieren en su fabricación de distintas operaciones, las que se realizan en un orden y configuración productiva determinada, dependiendo del tipo de producto, su volumen de producción, la variedad de productos que se produce en la misma línea, etc. El taller de flujo consiste de m máquinas dispuestas en serie, donde se procesan trabajos de flujo unidireccional que requieren m operaciones, cada una en una máquina distinta y siguiendo el mismo orden, esto es, primero en la máquina 1, después en la máquina 2, y así sucesivamente. Si la secuencia de trabajos permanece constante para todas las máquinas, el problema recibe el nombre de taller de flujo de permutación.

Para resolver el taller de flujo de permutación existen diferentes métodos exactos y heurísticos, constructivos o de mejora. Para el caso de dos máquinas, el clásico algoritmo de Johnson [3] obtiene la solución óptima del problema de taller de flujo de permutación con minimización de makespan  (intervalo de tiempo en el que se procesa la totalidad de los trabajos) y denotado por ^Cmax. Cuando se tienen tres o más máquinas se han desarrollado métodos heurísticos constructivos que entregan soluciones factibles, entre las que se destacan las conocidas heurísticas de Palmer, Gupta, MPS, CDS, RA y NEH diseñadas con el objetivo de minimización de makespan en el problema sin setup. Esta última, propuesta por Nawaz, Enscore y Ham en 1983 [4].