Metaheurística basada en el algoritmo competitivo imperialista (ica) aplicada a la solución del problema de "flow shop" hibrido (hfs) con máquinas paralelas no relacionadas

Abstract

En la presente investigación se estudia el problema de flow shop híbrido con máquinas paralelas no relacionadas con el propósito de minimizar el makespan, el cual es considerado un problema de optimización combinatoria y clasificado como NP-hard debido a su complejidad computacional representada en el tiempo y memoria requerida para encontrar una solución óptima. Diversos autores han implementado métodos heurísticos y metaheurísticos para resolver este problema, los cuales si bien no garantizan una solución óptima, permiten obtener una respuesta aproximada en un tiempo computacional razonable. Entre los métodos de solución comúnmente utilizados se encuentran el algoritmo genético, recocido simulado y combinación de reglas de secuenciación tales como la fecha de entrega más cercana y el tiempo de procesamiento más corto. En este trabajo se propone una metaheurística basada en el algoritmo competitivo imperialista para la minimización del makespan, considerando tiempos de alistamiento dependientes de la secuencia y de la máquina. En varias de las etapas del algoritmo competitivo imperialista se utilizan operadores caracteristicos del algoritmo genético (mutación y cruce). La eficiencia de la metaheurística se mide mediante doce instancias generadas por los autores y validadas en lenguaje de programación Matlab® y se compara con la solución obtenida por un método exacto utilizando el software GAMS®. Los resultados muestran que el algoritmo propuesto logra obtener soluciones de mejor calidad que las obtenidas mediante el método exacto para algunas de las instancias al combinar en sus niveles altos dos de los parámetros considerados en el diseño experimental. 1