Algoritmos evolucionarios aplicados al problema de secuenciamiento de Flow Shop

Abstract

Los algoritmos de Estimación de Distribuciones (EDAs - Estimation of Distribution Algorithms) son una clase de algoritmos basados en el paradigma de Computación Evolutiva (CE) que sustituyen los mecanismos de variación (cruce y mutación) utilizados tradicionalmente por Algoritmos Evolutivos (AEs). La población de nuevas soluciones se genera a través de la simulación de una estimación de probabilidad producida por la información de las soluciones generadas en iteraciones pasadas Por su parte, el problema de secuenciamiento de Flow Shop y conocido como FSSP (Flow Shop Sequencing Problem) ha convocado la atención de muchos investigadores en los últimos años. En FSSP, un conjunto de tareas deben seguir el mismo orden en una rutina de procesamiento para un conjunto de máquinas con el objetivo de optimizar alguna variable de performance (makespan, tardiness, lateness). En el caso de makespan, se trata de minimizar el tiempo de salida de la última tarea en la última máquina. Para máquinas mayores e iguales a tres el problema se transforma en NP-hard, conforme se incrementa el número de tareas. Este trabajo propone la exploración de distintos tipos de algoritmos evolucionarios aplicados a la resolución del problema de secuenciamiento de Flow Shop.