Solución del problema del "flow shop" híbrido (hfs) con máquinas paralelas no relacionadas, tiempos de alistamiento dependientes de la secuencia y "buffers" de tamaño limitado implementando dos algoritmos híbridos

Abstract

En la presente investigación se estudia el problema del flow shop hibrido con máquinas paralelas no relacionadas, tiempos de alistamiento dependientes de la secuencia y buffers de tamaño limitado, con el objetivo de minimizar el makespan; problema que ha sido clasificado como NP-hard debido a la complejidad computacional que representa. Con base en lo anterior, diversos autores han diseñado heurísticas y metaheurísticas, con el fin de encontrar buenas soluciones en tiempos computacionales razonables. Entre los métodos comúnmente utilizados se encuentran el algoritmo genético, recocido simulado, la búsqueda Tabú, metaheurísticas basadas en inteligencia artificial de enjambre, entre otras. Por ende, en este proyecto se diseñó un algoritmo genético híbrido, en el cual se genera la población inicial con base en los tiempos de alistamiento y procesamiento, y combina una búsqueda variable de la vecindad. Así mismo, se plantea un algoritmo híbrido basado en una colonia artificial de abejas, que involucra operadores de cruce y mutación del algoritmo genético, una búsqueda variable de la vecindad modificada y procedimientos de construcción y destrucción del algoritmo iterado codicioso. Los algoritmos se validaron mediante 20 instancias en lenguaje de programación Matlab® y los resultados se compararon con los hallados mediante la metaheurística basada en el algoritmo competitivo imperialista (ICA) y la solución obtenida por un método exacto, utilizando el software GAMS®. Los resultados muestran que, los algoritmos propuestos logran tener soluciones de buena calidad en tiempos computacionales razonables.