Desenvolvimento de uma hiper-heurística aplicada ao escalonamento em problemas de job shop

Resumo

O job shop scheduling problem (JSSP) é um problema complexo de otimização combinatória pertencente à classe de problemas NP-Hard, que representa o escalonamento de um sistema de manufatura. Para encontrar escalonamentos otimizados para o JSSP, uma das técnicas que têm sido utilizadas é a meta-heurística, como os algoritmos genéticos e colônia de formigas. Entretanto, trabalhos recentes da literatura indicam uma boa alternativa com o uso de hiper-heurísticas, que é uma abordagem para controle e seleção de heurísticas. A vantagem das hiper-heurísticas diante de outras heurísticas/meta-heurísticas é sua capacidade de operar com um bom desempenho em diferentes configurações de um problema, o que é uma das principais complexidades do JSSP. Dentre estas heurísticas, o Modified Choice Function (MCF) demonstrou efetividade quando aplicada como uma hiper-heurística de seleção sobre problemas combinatórios (Knapsack), porém ainda não há trabalhos na literatura que indicam o uso em JSSP. O objetivo deste trabalho é propor o uso do MCF no JSSP, gerenciando um algoritmo genético por meio da alternância de seus operadores para a redução do makespan. Conclui-se que o algoritmo proposto obteve bons resultados em todos os datasets, atingindo resultado superior do que próximo ao melhor algoritmo aplicado.