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
Local: Prédio 43412 – Sala 215 (sala de videoconferência) do Instituto de Informática
– Prof. Dr. Daniel Alejandro Rossit (UNS – por videoconferência)
– Profª. Drª. Luciana Salete Buriol (UFRGS)
– Prof. Dr. Marcelo Seido Nagano (USP – por videoconferência)
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 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. Since many scheduling 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 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 proposal we present a study on the permutation flow shop scheduling problem, following a grammar-based strategy to generate iterated local search or iterated greedy algorithms, and implementing several algorithmic components from the literature. A parameterized solver implements the components, and the search space defined by the grammar is explored with a racing-based strategy. We also present the current state of our ongoing work on the non-permutation flow shop scheduling problem. Our main objective in this work is to develop a single solver that integrates components from the literature, supports different variants of flow shop problems, and is able to find and instantiate algorithms that are competitive with the state-of-the-art methods via automated techniques.
Keywords: flow shop scheduling problem, automatic algorithm configuration, iterated local search, iterated greedy algorithm.