Implementação de meta-heurísticas para o problema de sequenciamento de tarefas em uma máquina com penalidades por antecipação e atraso.

Abstract

Este trabalho apresenta a implementação e análise comparativa de meta-heurísticas aplicadas ao Problema de Sequenciamento de Tarefas em uma Máquina com Penalidades por Antecipação e Atraso ( PSUMAA ). Foram avaliadas estratégias de Busca Local (Busca Local com First Improvement (BL-FI ) e Busca Local com Best Improvement (BL-BI )), um Algoritmo Genético (Algoritmos Genéticos (AG)) clássico e versões híbridas combinando AG com Busca Local. O objetivo foi investigar a capacidade dessas técnicas em produzir soluções de alta qualidade considerando o custo total de penalidades e princípios Just-in-Time. Os experimentos abrangeram múltiplas instâncias do problema, permitindo análise do desempenho em termos de função objetivo, gap médio e tempo de execução. Os resultados indicaram que as abordagens híbridas superam consistentemente os métodos isolados, apresentando menor gap médio e maior robustez, embora com maior custo computacional. As estratégias de Busca Local isoladas mostraram eficiência temporal, mas tendência à estagnação em ótimos locais, enquanto o AG clássico apresentou maior variabilidade e escalabilidade limitada. Conclui-se que, considerando o contexto experimental estabelecido, a hibridização entre exploração global e intensificação local constitui estratégia eficaz para o PSUMAA , evidenciando o trade-off entre desempenho computacional e qualidade das soluções.