Automatic algorithm configuration for flow shop scheduling problems

Abstract

Scheduling problems have been a subject of interest to the optimization researchers for many years. Flow shop problems, in particular, are one of the most widely studied scheduling problems due to their application to many production environments. A large variety of solution methods can be found in the literature and, since many flow shop problems are NP-hard, the most frequently found approaches are heuristic methods. Heuristic search methods are often complex and hard to design, requiring a significant amount of time and manual work to perform such a task, which can be tedious and prone to human biases. Automatic algorithm configuration (AAC) comprises techniques to automate the design of algorithms by selecting and calibrating algorithmic components. It provides a more robust approach which can contribute to improving the state of the art. In this thesis we present a study on the permutation and the non-permutation flow shop scheduling problems. We follow a grammar-based AAC strategy to generate iterated local search or iterated greedy algorithms. We implement several algorithmic components from the literature in a parameterized solver, and explore the search space defined by the grammar with a racing-based strategy. New efficient algorithms are designed with minimal manual effort and are evaluated against benchmarks from the literature. The results show that the automatically designed algorithms can improve the state of the art in many cases, as evidenced by comprehensive computational and statistical testing.

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.