Minimización de la tardanza para el flowshop flexible con setup utilizando heurísticas constructivas y un algoritmo genético

Tardiness minimization for the flexible flowshop with setup using constructive heuristics and a genetic algorithm

En este trabajo se considera el problema de programar n trabajos en un flowshop flexible de k etapas, condiferente número de máquinas idénticas por etapa considerando tiempos anticipatorios de preparacióndependientes de la secuencia (SDST) y minimización de la tardanza. Se comparan los resultados deheurísticas constructivas y un algoritmo genético estándar. La evaluación de los métodos se realiza enforma experimental sobre un conjunto de problemas de prueba generados aleatoriamente. Los resultadosmuestran que el algoritmo genético supera a alguna de las heurísticas comparadas pero no a todas.

INTRODUCCIÓN

La programación de la producción se entiende como la asignación de los recursos productivos a la ejecución de tareas productivas en un horizonte de corto plazo. En un entorno de manufactura moderna la programación de la producción es una tarea compleja y difícil de resolver en forma eficiente. Actualmente, tanto la rapidez como el cumplimiento de entregas a clientes constituyen una ventaja estratégica para la competitividad de los sistemas productivos. En tal sentido, lograr secuencias de producción que minimicen atrasos en la entrega es de vital importancia. Asociado a lo anterior se presenta el problema de la reducción de lotes de producción, originando frecuentes preparaciones de las instalaciones incurriendo en costosos tiempos de preparación, cuya relevancia en la programación se manifiesta en una amplia gama de configuraciones productivas [1].

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.

El flowshop flexible (FFS) es una generalización del problema clásico de flowshop de una máquina por etapa, en el que se dispone de máquinas en paralelo en cada etapa. Esta configuración se encuentra frecuentemente en la industria textil, cerámica y del plástico, entre otras. En adelante nos referiremos a setup como concepto equivalente al de tiempos (anticipatorios) de preparación dependientes de la secuencia.

Dado que el problema de programar un flowshop flexible con diferentes objetivos es un conocido problema NP-completo [2] en la literatura se han propuesto principalmente algoritmos heurísticos y metaheurísticos.

Si bien para el problema FFS con tiempos de setup y minimización del makespan existen numerosos trabajos en la literatura [3-7], no es así para el caso de la minimización de la tardanza o de alguna de sus variantes.