Tese de Doutorado de Artur Ferreira Brum

DEFESA DE TESE DE DOUTORADO

Aluno: Artur Ferreira Brum
Orientador: Prof. Dr. Marcus Rolf Peter Ritt

Título: Automatic Algorithm Configuration for Flow Shop Scheduling Problems.
Linha de Pesquisa: Algoritmos e Otimização

Data: 11/08/2020
Horário: 15h

Esta banca ocorrerá excepcionalmente de forma totalmente remota. Interessados em assistir a defesa poderão acessar a sala virtual através do link: https://mconf.ufrgs.br/webconf/00273515

Banca Examinadora:
– Prof. Dr. Daniel Alejandro Rossit (UNS)
– Prof. Dr. Hélio Yochihiro Fuchigami (UFG)
– Profª. Drª. Luciana Salete Buriol (UFRGS)

Presidente da Banca: Prof. Dr. Marcus Rolf Peter Ritt

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.

Keywords: flow shop; heuristics; automatic algorithm configuration;