Algoritmo genético para calendarización en un casco especial del flujo de tareas con dos etapas

Abstract

En este trabajo aplicamos la computación como una herramienta poderosa para resolver problemas en el área de Investigación de Operaciones (IO). Uno de los problemas de gran interés en la IO es el problema de flujo de tareas, conocido en inglés como Flexible Flow Shop problem (FFS), en donde uno de los criterios a optimizar ha sido minimizar los tiempos globales de manufactura de productos, como lo muestra Gupta (1988) en un problema de calendarización con dos etapas. La programación de operaciones y particularmente la optimización del tiempo de secuenciación de las tareas que conllevan los procesos de esas operaciones, es el tema en el que nos enfocamos en este trabajo. Esta no es una tarea fácil si tenemos en cuenta una serie de aspectos como las múltiples soluciones sub-óptimas que puede generar el problema y lo difícil que es llegar a obtener el óptimo global del mismo, como se ve en el trabajo de Sriskandarajah y Sethi (1989), quienes abordan el problema de flujo híbrido de tareas con dos etapas: una máquina en la primera etapa y múltiples máquinas en la segunda etapa, dicho trabajo es importante porque allí se establecen cotas inferiores para diferentes heurísticas. Una adecuada programación de tareas permite el buen funcionamiento de cualquier sistema, manteniendo la eficiencia y el control sobre las operaciones, por lo que en este trabajo se plantea como problema de investigación, encontrar una secuencia óptima de n tareas, de tal forma que el retraso total (T, tardiness) o el tiempo de finalización de todas las tareas (Cmax, makespan) sea el mínimo posible, en un ambiente de flujo de tareas flexible (FFS). En nuestro sistema FFS de interés, las máquinas están configuradas de la forma 1+m , es decir, dos etapas sucesivas de máquinas en donde la primera etapa tiene sólo una máquina y la segunda etapa tiene m máquinas idénticas que trabajan en paralelo. El número de tareas n debe ser mayor al número m de máquinas. El problema planteado se clasifica como NP-difícil (NP-Hard), en base al análisis presentado en (Gupta., 1988). Desde el punto de vista de optimización combinatoria, el problema de flujo de tareas consiste en encontrar una permutación de las n tareas que permita minimizar algún criterio que mida la calidad del calendario. Este es un problema típico de secuenciación de tareas, y para encontrar el calendario óptimo nos apoyamos en los Algoritmos Genéticos (AG), dados a conocer por Holland (1975), padre de dicha heurística.