Souza, Sergio Ricardo deFreitas, Warley Ribeiro de2026-09-242026-02-20https://repositorio.cefetmg.br//handle/123456789/3036Esta 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.ptDissertação2026-09-24Algoritmos – TesesEstruturas de dados (Ciência da computação) – TesesOtimização combinatória – TesesOtimização matemática – TesesMeta-heurísticas – TesesMatemática discreta em Ciência da computação – Teses