MetaheurIstica greedy randomized adaptive search procedure (gras-procedimiento de búsqueda codiciosa aleatorizada y adaptativa) aplicada al job shop scheduling problem (jssp)

Abstract

La presente investigación tiene como propósito diseñar un algoritmo para dar solución al Job Shop Scheduling Problem tradicional bajo el objetivo de minimización del makespan teniendo como punto de partida la metaheurística GRASP, para ello se realiza una revisión de literatura que incluye el problema, el método de solución y la combinación de estos dos como base para la investigación. Seguido a esto, se diseña el algoritmo teniendo como resultado un hibrido compuesto por GRASP y Algoritmo Genético, el cual inicia con la construcción de la población inicial por medio de GRASP y los operadores genéticos utilizados son selección aleatoria, un operador de cruce propuesto por Park et. al. y mutación swap. El algoritmo diseñado y es validado a través de instancias estudiadas en la literatura variando algunos de los parámetros seleccionados. Adicionalmente, se realiza un diseño factorial para cada una de las instancias probadas con el fin de identificar los factores significativos en la variable respuesta makespan. Finalmente, se presentan los resultados obtenidos y se comparan con otros algoritmos propuestos.