Un algoritmo memetico para la minimización del makespan en el problema de job shop scheduling

Abstract

El problema del Job Shop Scheduling se aborda en la presente investigación con el objetivo de minimizar el makespan. Es considerado un problema de optimización combinatoria catalogado de tipo NP-hard debido a su complejidad computacional y que actualmente ocupa un importante lugar en el secuenciamiento de operaciones en la industria para lograr la minimización de un recurso significativo como el tiempo. Para la solución de este problema se han implementado diversos métodos heurísticos y metaheurísticos que resultan ser muy eficientes, aunque no garantizan la obtención de resultados óptimos, arrojan soluciones aproximadas y en un tiempo computacional razonable. Un algoritmo memético es propuesto para minimizar el makespan, aprovechando las características del algoritmo genético mediante la aplicación del operador de cruce JOX, la representación basada en operaciones y un método de búsqueda local modificado, basado en la estrategia de Nowicki y Smutnicki. El algoritmo fue ejecutado en 17 problemas del benchmark extraídos de la OR-Library para su validación en el lenguaje de programación Matlab® y comparado con un algoritmo genético simple (GA). Los resultados obtenidos muestran que el algoritmo memético propuesto es más eficiente al encontrar mejores soluciones que el GA. El buen rendimiento del MA se ve reflejado al encontrar las mejores soluciones conocidas de instancias de baja y media complejidad y soluciones aproximadas en instancias de alta complejidad. 1