Minimising Total Flowtime in a No-Wait Flow Shop (NWFS) using Genetic Algorithms

Minimizar el tiempo de flujo total en un Flow shop sin escalas (NWFS) utilizando algoritmos genéticos

Este documento considera un problema de secuenciación de líneas de flujo sin espera (NWFS), donde el objetivo es minimizar el tiempo de flujo total. Proponemos un algoritmo genético (GA) que se implementa en un entorno de hoja de cálculo. El GA funciona como un complemento en la hoja de cálculo. Se demuestra que, con el enfoque propuesto, cualquier criterio puede optimizarse sin modificar la rutina del GA o el modelo de hoja de cálculo. Además, el método propuesto para resolver este problema de clase es de propósito general, ya que se puede personalizar fácilmente agregando o eliminando tareas y máquinas. Varios problemas de referencia ya publicados en la literatura se usan para demostrar la capacidad de resolución de problemas del enfoque propuesto. El conjunto de problemas de la evaluación tiene un rango que varía desde pequeños (7 trabajos, 7 máquinas) hasta grandes (100 trabajos, 10 máquinas). El rendimiento del GA se compara con diferentes técnicas meta-heurísticas utilizadas en la literatura anterior. El análisis experimental demuestra que las soluciones obtenidas en esta nueva búsqueda ofrecen igual calidad que los algoritmos ya desarrollados para el problema NWFS.

Introducción

La programación es un aspecto importante de cualquier empresa de fabricación. No se puede negar la importancia de una función de programación eficiente, ya que garantiza el envío a tiempo de los productos al mercado antes que los competidores, obteniendo así mayores beneficios. El objetivo principal de cualquier problema de programación es asignar eficientemente los trabajos a las máquinas disponibles y determinar la hora de inicio y finalización de cada operación, de forma que se minimice o maximice una determinada función objetivo. La programación desarrollada también debe satisfacer varias restricciones de producción. Por ello, para lograr una producción de alta eficiencia, los algoritmos/esquemas de programación eficientes se consideran un factor clave.

La programación del taller de flujo es uno de los modelos más estudiados en el entorno de la fabricación. En un problema general de programación de taller de flujo, hay n trabajos que deben ser programados en m máquinas para minimizar el tiempo total de finalización o makespan. Todos los trabajos siguen el mismo orden de procesamiento. El problema de programación del taller de flujo ha recibido una atención considerable desde su introducción en 1954 (Johnson, 1954). A lo largo de los años, varios investigadores han propuesto numerosas técnicas y meta-heurísticas eficientes. Gupta et al. (2006) ha dado un estudio detallado de la investigación sobre la programación de la tienda de flujo. Tyagi et al. (2013) también presentan un estudio de la evolución de los problemas de programación de tiendas de flujo y posibles enfoques para su solución.