Automatic algorithm configuration for flow shop scheduling problems

• Ano de defesa: 2020
• Autor(a) principal: Brum, Artur Ferreira
• Orientador(a): Ritt, Marcus Rolf Peter
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Palavras-chave em Português: Configuração automática de algoritmos; Heurística; Algoritmos; Pesquisa operacional
• Palavras-chave em Inglês: Flow shop scheduling problem; Iterated local search; Iterated greedy algorithm
• Link de acesso: http://hdl.handle.net/10183/213705

Problemas de agendamento tem sido assunto de interesse para pesquisadores em otimização por muitos anos. Problemas de flow shop, em particular, são alguns dos problemas de agendamento mais amplamente estudados devido à sua aplicação em muitos ambientes de produção. Uma grande variedade de métodos de resolução pode ser encontrada na literatura e, visto que muitos problemas de flow shop são NP-difíceis, as abordagens mais frequentemente encontradas são métodos heurísticos. Métodos heurísticos de busca podem ser complexos e difíceis de projetar, requerendo uma significativa quantia de tempo e trabalho manual para realizar tal tarefa, que pode ser tediosa e propensa a viés humano. Configuração Automática de Algoritmos (CAA) compreende técnicas para automatizar o projeto de algoritmos, selecionando e calibrando componentes algorítmicos. Ela fornece uma abordagem mais robusta que pode contribuir para melhorar o estado da arte. Nesta tese apresentamos um estudo sobre os problemas de agendamento em flow shop permutacional e não-permutacional. Nós seguimos uma estratégia de CAA baseada em gramática para gerar buscas locais iteradas ou algoritmos gulosos iterados. Nós implementamos vários componentes algorítmicos da literatura em um solver parametrizado, e exploramos o espaço de busca definido pela gramática com uma estratégia baseada em corridas. Novos algoritmos eficientes são obtidos com esforço manual mínimo e são avaliados em benchmarks da literatura. Os resultados mostram que os algoritmos projetados de maneira automatizada podem melhorar o estado da arte em muitos casos, conforme evidenciado por abrangentes testes computacionais e estatísticos.