Variantes da metaheurística local branching para o problema de sequenciamento em projetos com restrição em recursos e múltiplos modos de execução
Nenhuma Miniatura disponível
Data
2022-03-30
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Centro Federal de Educação Tecnológica de Minas Gerais
Resumo
O Problema de Sequenciamento em Projetos com Restrição em Recursos e Múltiplos Modos de Execução (Multi-mode Resource Constrained Project Scheduling Problem – MRCPSP) consiste em sequenciar todas as atividades de um projeto, respeitando a ordem de precedência dessas atividades, que, uma vez iniciadas, não podem ser interrompidas. As atividades possuem várias combinações de modos de execução, que consistem em diferentes combinações de tempo de processamento e consumo de recursos. O objetivo é minimizar o tempo de duração do projeto, encontrando tempos de início para cada atividade do projeto. Trata-se de um problema NP-Difícil. Esta tese analisa sua resolução por uma estratégia de geração de pseudocortes, hibridizada com uma heurística de busca local, o que caracteriza um método chamado de matheurística. A proposta apresenta duas novas definições para o pseudocorte linear conhecido como local branching cut, bem como verifica outras duas definições da literatura para a resolução do MRCPSP por meio desse pseudocorte. Também são analisadas a influência dos parâmetros dessa matheurística e o impacto da heurística de busca local. Foram realizados testes computacionais utilizando instâncias das bibliotecas PSPLIB e MMLIB. Os melhores resultados conhecidos para as instâncias usadas nos testes são apresentados como referência para validar os resultados obtidos pela abordagem proposta nesta tese.
Descrição
Palavras-chave
Programação de produção – Teses, Programação heurística – Teses, Processos de ramificação – Teses, Agenda de execução (Administração) – Teses, Otimização combinatória – Teses