/TAREA_2-METAHEURISTICAS

TAREA_2-METAHEURISTICAS

Primary LanguageC++MIT LicenseMIT

Procedimientos de Búsqueda Local Aplicados a Problemas de Secuenciación de Máquinas

Julio Mario Daza-Escorcia [jm.dazae@uniandes.edu.co], David Álvarez Martinez [d.alvarezm@uniandes.edu.co]

Universidad de los Andes Carrera 1 Este No. 19A – 40, Bogotá, Colombia

Resumen

Este artículo presenta dos heurísticos de búsqueda local para el problema de secuenciación de máquinas, denominado Flow Shop Scheduling Problem (FSSP). Estos heurísticos establecen dos vecindarios para el FSSP que se combinan estratégicamente para lograr buenas soluciones. El primer heurístico de búsqueda local se basa en el conocido 2opt, mientras que el segundo se basa en un intercambio aleatorio. Los experimentos sobre las instancias de referencia de la literatura muestran que nuestros algoritmos se encuentran cercanos a los Best Know Solutions (BKS’s) pre-sentes en la literatura, obteniendo dos nuevos BKS’s que mejoran el makespan en un 0.81% y 1.06% respectivamente.