Navegando por Autor "Freitas, Warley Ribeiro de"

Agora exibindo 1 - 1 de 1
  • Imagem de Miniatura
    Item
    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
    (Centro Federal de Educação Tecnológica de Minas Gerais, 2026-02-20) Freitas, Warley Ribeiro de; Souza, Sergio Ricardo de; Sá, Elisangela Martins de; Silva, Maria Amélia Lopes; http://lattes.cnpq.br/4686246805500174; http://lattes.cnpq.br/1584173805850799; http://lattes.cnpq.br/3677015295211434; http://lattes.cnpq.br/8032107634782984; Souza, Sergio Ricardo de; Sá, Elisangela Martins de; Silva, Maria Amélia Lopes; Fernandes, Gustavo Alves; Souza, Marcone Jamilson Freitas
    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.