Un Algoritmo evolutivo híbrido para el problema de programación del taller de flujo permutado con restricciones de turno

Hybrid evolutionary algorithm for the permutation flow shop scheduling problem with shifts constraints

Un Flow Shop es un sistema de producción en el cual una serie de trabajos debe seguir un flujo unidireccional para ser procesada en varias estaciones de trabajo. En este artículo se introduce el Permutation FlowShop Scheduling Problem with Shifts Constraints (PFSSPSC), una variante del Permutation Flow ShopScheduling Problem (PFSSP) en donde se busca minimizar el tiempo en que se terminan de procesartodos los trabajos y se imponen restricciones sobre los turnos de procesamiento de los trabajos. Estasrestricciones consisten en que la ejecución de cada trabajo siempre debe terminar en el mismo turno enque empieza para evitar interrupciones. Además, en este artículo se introduce un algoritmo híbrido parahallar buenas soluciones al PFSSPSC. Éste consiste en un metaheurístico compuesto por un algoritmogenético y un algoritmo VNS (Variable Neighborhood Search). El algoritmo propuesto es probado con 120instancias del PFSSP disponibles en la literatura adaptadas para el PFSSPSC. Las soluciones obtenidasson comparadas con aquellas ofrecidas por tres algoritmos heurísticos en cuanto a tiempo de ejecucióny calidad de las soluciones obtenidas: un método constructivo, un método constructivo aleatorizado y unVND. La comparación entre los cuatro algoritmos muestra una superioridad de los algoritmos híbridoy VND en cuanto a la calidad de la solución, aunque el método constructivo y la búsqueda aleatoria son más rápidos. Entre el algoritmo híbrido y el VND no hay una gran diferencia en la calidad de la solución,pero el algoritmo híbrido es significativamente más rápido que el VND.

INTRODUCCIÓN

Un sistema productivo tipo "Flow Shop" es un ambiente en el que un conjunto de tareas debe seguir un flujo unidireccional para ser procesadas en múltiples estaciones de trabajo, donde cada estación consta de una sola máquina. En términos simples, se tienen n trabajos, los cuales han de pasar cada uno por todas las m máquinas del flujo, estación por estación. Cada máquina puede procesar un solo trabajo a la vez y no se puede interrumpir una tarea después de iniciada, de manera que no puede comenzar a realizar una tarea sin haber acabado la anterior. Los trabajos solo pueden pasar por una máquina a la vez, de modo que, para que una máquina inicie la ejecución de un trabajo se debe esperar a que la máquina anterior haya terminado el procesamiento de dicho trabajo. La ejecución de cada trabajo en cada máquina es caracterizada por su tiempo de procesamiento. La operación del Flow Shop implica elegir el orden en que se procesan los trabajos, más no sobre el orden en que éstos pasan por las máquinas. Así, el "Flow Shop Scheduling Problem" (FSSP) es el problema de optimización que busca encontrar un orden en el cual realizar los trabajos que minimice el tiempo de terminación de todos los trabajos.

El "Permutation Flow Shop" es un sistema de producción en el cual, además de las condiciones antes mencionadas, los trabajos son realizados por todas las máquinas en el mismo orden.