GVNS e GRASP com Path-relinking aplicado à solução do problema de sequenciamento em projetos com restrição em recursos e múltiplos modos de execução
Carregando...
Data
2026-02-20
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Centro Federal de Educação Tecnológica de Minas Gerais
Resumo
Esta dissertação aborda a resolução do Multi-mode Resource-Constrained Project Scheduling Problem (MRCPSP), um problema que consiste em sequenciar e programar todas as atividades de um projeto, relacionadas por restrições de precedência e de recursos limitados. Cada atividade pode ser executada em diferentes modos, sendo que cada modo apresenta duração e consumo específicos de recursos renováveis e não renováveis, o que resulta em diferentes combinações viáveis possíveis para a execução do projeto. O objetivo do MRCPSP é minimizar o makespan total, determinando o período de término e o modo de execução para cada atividade. Este é um problema NP-difícil, portanto, a obtenção de soluções ótimas para instâncias de médio e grande por métodos exatos em tempo computacional razoável torna-se inviável. Nesse contexto, esta dissertação propõe a implementação das metaheurísticas Variable neighborhood search (VNS) e Greedy Randomized Adaptive Search Procedure (GRASP) para produzir soluções de alta qualidade de forma rápida. Adicionalmente, integra-se ao GRASP o procedimento de Path Relinking (PR) como estapa pós-otimização, com o objetivo de explorar regiões promissoras do espaço de busca. Duas variantes do PR são consideradas: o Interior PR (IPR), voltado à intensificação da busca ao longo do caminho que conecta soluções de alta qualidade, e o Exterior PR (EPR), direcionado à diversificação da busca por meio da exploração de regiões adjacentes a esse caminho. Na metodologia adotada a fase de construção do algoritmo GRASP é responsável por gerar soluções iniciais diversificadas, as quais são refinadas por um procedimento de busca local. Em seguida os procedimentos de PR são acionados, como estratégias de pós-otimização, para fazer um balanço entre diversificação e intensificação sobre as melhores soluções obtidas ao longo da busca. As análises das diferentes estratégias de busca e de pós-otimização indicam que as abordagens propostas apresentam desempenho competitivo ao da literatura, evidenciando o potencial dessas metodologias para a resolução do MRCPSP.
Descrição
Palavras-chave
Algoritmos – Teses, Estruturas de dados (Ciência da computação) – Teses, Otimização combinatória – Teses, Otimização matemática – Teses, Meta-heurísticas – Teses, Matemática discreta em Ciência da computação – Teses