Avaliação de heurísticas para um algoritmo branch e bound para minimizar o makespan em um flowshop com bloqueio

摘要

Este trabalho tem o objetivo de avaliar o uso de diferentes métodos heurísticos para obtenção de uma solução inicial para um algoritmo branch e bound, tendo como objetivo minimizar o makespan em um ambiente flowshop com buffer zero. Como o problema é conhecido por ser NP-Hard, o algoritmo branch e bound pode necessitar de elevado tempo computacional para encontrar a melhor solução. A utilização de uma solução inicial pode reduzir o tempo de processamento, proporcionando um limite superior inicial. Neste trabalho, a eficiência da utilização de uma solução inicial para o algoritmo branch e bound foi avaliada com a comparação dos algoritmos. O algoritmo branch e bound utilizado, bem como o limitante inferior foram propostos por Ronconi (2005). Cinco métodos heurísticos foram avaliados (MM, PF, wPF e PW) utilizando um conjunto de problemas teste composto de 180 problemas. Os resultados mostraram que a utilização da heurística para obter uma solução inicial para o algoritmo branch e bound reduz significativamente o tempo computacional.