Tema da Tese: Auto-Parametrização de Meta-Heurísticas para Problemas de Escalonamento em Ambiente Industrial

Autor: André Borges Guimarães Serra e Santos

Orientadores: Maria Leonilde Rocha Varela, Ana Maria Madureira Pereira

Data: 20/06/2020

Programa Doutoral em Engenharia Industrial e de Sistemas

Abstract:  Há uma série de Problemas de Otimização que pela sua complexidade, não podem ser resolvidos, pelo menos de forma eficiente. Entre os problemas que são demasiados complexos para serem resolvidos à otimalidade há inúmeros Problemas de Escalonamento. É normal recorrer a Meta-Heurísticas para abordar os Problemas de Escalonamento. As Meta-Heurísticas não encontram sempre as soluções ótimas, mas são capazes de encontrar soluções satisfatórias em pouco tempo computacional. Embora a comunidade científica tenha demonstrado muito interesse na análise do comportamento das Meta-Heurísticas, a análise da sua parametrização têm merecido pouca atenção. É a parametrização que vai adequar a Meta-Heurística ao problema, no entanto ainda é feita, maioritariamente, de uma forma empírica. Há múltiplos métodos de parametrização, no entanto, ou são morosos, requerendo um esforço considerável, ou não aproveitam os benefícios das Meta-Heurísticas que vão parametrizar. De maneira a abordar e a simplificar a parametrização de Meta-Heurísticas, neste trabalho, é proposto um modelo de auto-parametrização que usa uma Meta-Heurística na parametrização. Isto vai permitir automatizar a parametrização, como se se tratasse de um Problema de Otimização, evitando que o utilizador despenda tempo em ensaios de parametrização. O modelo vai automatizar o processo de parametrização através de duas Meta-Heurísticas: uma Meta-Heurística do Espaço de Soluções e uma Meta-Heurística do Espaço de Parâmetros. A Meta-Heurística do Espaço de Parâmetros vai fazer uma pesquisa por soluções de parametrização e a Meta-Heurística do Espaço de Soluções é executada para avaliar o desempenho das soluções de parametrização. Para analisar o desempenho o modelo, foi implementado um protótipo de auto-parametrização. O protótipo foi comparado e analisado através de um Problema de Escalonamento e através do TSP (Traveling Salesman Problem). O protótipo encontrou, no caso do Problema de Escalonamento, soluções de melhor qualidade que as do protótipo de parametrização manual, embora as diferenças não tenham sido expressivas. Já no caso do TSP, foi mais eficaz, desta vez, com diferenças estatisticamente expressivas.

Palavras-Chave: Auto-Parametrização; Parametrização por Pesquisa; Meta-Heurísticas; Problema de Escalonamento.