Algoritmo Iteração Gulosa com Busca Local em Soluções Parciais e Algoritmo Busca do Macaco Híbrida Aplicados ao Problema Flow Shop Permutacional

Abstract

This work refers to the Permutation Flow Shop Problem (PFSP) with the objective function of minimizing the makespan. Makespan is a performance measure that calculates the completion of the last that leaves the system. The PFSSP aims to find a permutation of n works which the processing order of tasks of this permutation is the same the whole set of machines, so that all tasks go through all machines. A systematic review of the PFSP literature was developed in this paper and the two following methods were chosen to be analyzed and compared: the heuristic Iterated Greedy with Optimization of Partial Solutions (IG_OPS) and the metaheuristic Hybrid Monkey Search (HMS). In order to generate the initial population in both algorithms, NEH heuristics were used, because it quickly found satisfactory results for the PFSSP. The benchmark chosen for the computational experiments was the develped by Taillard. Results show that IG_OPS is efficient because it can find good solutions with a low runtime. In other hand, HMS has found solutions slightly worse compared to IG_OPS, but the main negative point of this method was that it had a very high execution time when finding solutions, thus making it inefficient and unfeasible. So, the IG_OPS has a cost-benefit ratio that is broadly superior to the HMS to solve the PFSP minimizing the makespan.