Simheurísticas para o problema de flow shop permutacional com tempos de processamento aleatórios e buffers limitados. - Silva, Bruna Carvalho da (2025)
Um problema comum de ambientes de manufatura envolve determinar o sequenciamento de tarefas ideal em um conjunto de máquinas, considerando capacidades de buffer limitadas e tempos de processamento aleatórios. A presença de buffers limitados e tempos de processamento aleatórios aumenta significativamente a complexidade do problema, onde soluções analíticas não estão disponíveis, exceto para casos especiais. Esta tese aborda o Problema de Flow Shop Permutacional com Buffer Limitado e Tempos de Processamento Aleatórios para minimizar o Makespan Esperado (LBPFSP RPT E[Cmax]). Duas abordagens principais são propostas para o problema: (1) resolver o problema equivalente determinado e (2) aplicar simheurísticas, uma abordagem promissora para problemas estocásticos que combina simulação com metaheurísticas. A partir disso, três algoritmos baseados na Iterated Local Search (ILS), três na Iterated Greedy (IGA) e um de Busca Aleatória (RS) são apresentados. As eficiências dos algoritmos são comparadas em instâncias geradas aleatoriamente. Um projeto experimental com quatro configurações de máquina e tarefas, três níveis de variação para os tempos de processamento e cinco tamanhos de buffers é aplicado. Durante a calibração, uma simheurística não foi competitiva e foi descartada. Os resultados mostram que a simheurística SIGA1 é o algoritmo mais robusto em todos os cenários (configuração, cv e buffer) e pode ser recomendada para a maioria das situações, especialmente com alta variabilidade ou grandes instâncias. Seguindo a SIGA1, a simheurística SILS1 tem um bom desempenho em comparação com a simheurística SIGA2 e os algoritmos determinados. A SILS1 é uma opção barata, devido à sua estrutura simples, com poucos parâmetros para configurar, facilitando a implementação. A simheurística SIGA2 é menos eficaz ao lidar com buffers mais restritos. Os algoritmos determinados, DIGA e DILS, são alternativas viáveis para problemas maiores, de baixa variabilidade e com buffers mais restritos, oferecendo desempenho razoável a um custo computacional potencialmente menor. Como esperado, o método RS produz resultados inferiores, tornando-se menos competitivo à medida que os tamanhos das instâncias aumentam. As simheurísticas são algoritmos robustos, fáceis de implementar, com poucos parâmetros e capazes de lidar com incertezas, sem se limitar a uma distribuição de probabilidade, e que podem efetivamente tratar grandes instâncias de LBPFSP RPT E[Cmax] e PFSP RPT E[Cmax] com tempos computacionais razoáveis.