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

Página do item simplificado
dc.contributor.advisorSouza, Sergio Ricardo de
dc.contributor.advisor-coSá, Elisangela Martins de
dc.contributor.advisor-coSilva, Maria Amélia Lopes
dc.contributor.advisor-coLatteshttp://lattes.cnpq.br/4686246805500174
dc.contributor.advisor-coLatteshttp://lattes.cnpq.br/1584173805850799
dc.contributor.advisorLatteshttp://lattes.cnpq.br/3677015295211434
dc.contributor.authorFreitas, Warley Ribeiro de
dc.contributor.authorLatteshttp://lattes.cnpq.br/8032107634782984
dc.contributor.refereeSouza, Sergio Ricardo de
dc.contributor.refereeSá, Elisangela Martins de
dc.contributor.refereeSilva, Maria Amélia Lopes
dc.contributor.refereeFernandes, Gustavo Alves
dc.contributor.refereeSouza, Marcone Jamilson Freitas
dc.date.accessioned2026-09-24T16:09:23Z
dc.date.available2026-09-24T16:09:23Z
dc.date.issued2026-02-20
dc.description.abstractEsta 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.
dc.description.abstractotherThis dissertation addresses the resolution of the Multi-mode Resource-Constrained Project Scheduling Problem (MRCPSP), a problem that consists of sequencing and scheduling all project activities, related by precedence and limited resource constraints. Each activity can be executed in different modes, with each mode presenting specific duration and consumption of renewable and non-renewable resources, resulting in different feasible combinations for project execution. The objective of the MRCPSP is to minimize the total makespan, determining the completion period and execution mode for each activity. This is an NP-hard problem, therefore obtaining optimal solutions for medium and large instances by exact methods within reasonable computational time becomes unfeasible. In this context, this dissertation proposes the implementation of the metaheuristics Variable Neighborhood Search (VNS) and Greedy Randomized Adaptive Search Procedure (GRASP) to produce high-quality solutions quickly. Additionally, Path Relinking (PR) is integrated into GRASP as a post-optimization step, aiming to explore promising regions of the search space. Two variants of PR are considered: Interior PR (IPR), focused on intensification along the path connecting high-quality solutions, and Exterior PR (EPR), directed at diversification through the exploration of regions adjacent to this path. In the adopted methodology, the construction phase of the GRASP algorithm is responsible for generating diversified initial solutions, which are refined by a local search procedure. Subsequently, PR procedures are triggered as post-optimization strategies to balance diversification and intensification over the best solutions obtained throughout the search. Analyses of the different search and post-optimization strategies indicate that the proposed approaches present competitive performance compared to the literature, highlighting the potential of these methodologies for solving the MRCPSP.
dc.identifier.urihttps://repositorio.cefetmg.br//handle/123456789/3036
dc.language.isopt
dc.publisherCentro Federal de Educação Tecnológica de Minas Gerais
dc.publisher.countryBrasil
dc.publisher.initialsCEFET-MG
dc.publisher.programPrograma de Pós-Graduação em Modelagem Matemática e Computacional
dc.subjectAlgoritmos – Teses
dc.subjectEstruturas de dados (Ciência da computação) – Teses
dc.subjectOtimização combinatória – Teses
dc.subjectOtimização matemática – Teses
dc.subjectMeta-heurísticas – Teses
dc.subjectMatemática discreta em Ciência da computação – Teses
dc.titleGVNS 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
dc.typeDissertação

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
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.pdf
Tamanho:
1.96 MB
Formato:
Adobe Portable Document Format
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.39 KB
Formato:
Item-specific license agreed to upon submission
Descrição:
Baixar

Coleções

Mestrado em Modelagem Matemática e Computacional