Flexible Flowshop problem minimizing total flow time and makespan using Evolutionary Algorithm
Luis E. Ramirez Polo
Vanessa P. Manotas Niño
Abstract:
Scheduling on many stations, with a variable number of machines on each station (Flexible Flowshop), looking to minimize multiple objectives as makespan and total flow time is not a new problem, but it is a low investigated area which has non-optimal solutions for all the cases. Our objective in the problem we’ve approached was to develop a meta-heuristic based on Strength Pareto Evolutionary Algorithm (SPEA) that give us solutions to the problem described before and be applied through an algorithm to see the sequence, the values of the objectives [Pareto optimal solutions (Cmax, Cprom)] for each station and verify the effectiveness. We are analyzing a making decision problem on the C C FF Max C , scenario, this mean that we have a flexible flowshop with k stations that has (M k ) identical machines. The algorithm was executed 120 times with a maximum number of generations equal to 4. It was obtained a group of elitist members of each running, and it was applied dominance criterion to get the final group of non dominated solutions.
In Spanish:
La programación de operaciones en varias estaciones, con diversos números de maquinas en cada estación (Flowshop flexible), buscando minimizar múltiples objetivos como makespan y tiempo total de flujo no es un problema nuevo, pero si uno con poco trabajo desarrollado y el cual no presenta una solución óptima en todos los casos. Nuestro objetivo fue plantear una meta-heurística basada en Strength Pareto Evolutionary Algorithm (SPEA) que diera una solución al problema anteriormente descrito y aplicarla mediante un algoritmo que arrojara una secuencia óptima y sus respectivos valores de respuesta [frente pareto (Cmax, Cprom)] para cada estación teniendo en cuenta las respectivas máquinas y a partir de ahí verificar la efectividad. Estamos analizando un problema de toma de decisiones en el escenario C C FF Max C , , esto significa que tenemos un Flowshop Flexible con k estaciones que tiene (M k ) maquinas idénticas. El algoritmo fue ejecutado 120 veces con un número máximo de generaciones igual a 4. Se obtuvo obtuvo un grupo de miembros elitistas de cada corrida, y se aplicó criterio de dominancia para obtener el último grupo de soluciones no dominadas.