Iterated Greedy Algorithm With Optimization of Partial Solutions and Hybrid Monkey Search Algorithm Applied to the Permutation Flow Shop Problem

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.UFU - Universidade Federal de UberlândiaTrabalho de Conclusão de Curso (Graduação)Este trabalho se refere ao Problema Flow Shop Permutacional (PFSP) com a função objetivo de minimizar o makespan. Makespan é uma medida de desempenho que calcula o tempo de conclusão do último trabalho a sair do sistema. O PFSP objetiva encontrar uma permutação de n trabalhos nos quais a ordem de processamento dos trabalhos dessa permutação é a mesma em todo o conjunto das m máquinas, de modo que todos os trabalhos passem por todas as máquinas. Neste trabalho foi realizada uma revisão sistemática da literatura na área do PFSP e a partir desta dois métodos foram escolhidos para serem analisados e comparados: a heurística Iteração Gulosa com Busca Local em Soluções Parciais (IG_BLSP) e a meta-heurística Busca do Macaco Híbrida (BMH). Para gerar a população inicial nos dois algoritmos, foi utilizada a heurística NEH, pelo fato de encontrar de maneira rápida resultados satisfatórios para o PFSP. O benchmark escolhido para os experimentos computacionais foi o desenvolvido por Taillard. Os resultados mostram que o IG_BLSP é eficiente, pois consegue encontrar boas soluções com um tempo de execução baixo. O BMH por sua vez encontrou soluções um pouco piores em comparação ao IG_BLSP, mas o principal ponto negativo deste método foi que ele apresentou um tempo de execução muito elevado ao encontrar as soluções, tornando-se assim ineficiente e inviável. Sendo assim, o IG_BLSP possui um custo-benefício amplamente superior ao BMH para resolver o PFSP minimizando o makespan