ESCALONAMENTO DE PROJETOS COM RESTRIÇÃO DE RECURSOS E PRECEDÊNCIAS GENERALIZADAS: UM MÉTODO EXATO DE RESOLUÇÃO
Escalonamento de projetos
Restrição de recursos
Restrição de carga de trabalho
Problema de satisfabilidade
Escalonamento de projeto
Otimização combinatória
Restrição de recurso
Optimization
Project scheduling
Resource constraint
Workload constraint
Satisfiability problem
Azevedo, Guilherme Henrique Ismael de | Posted on:
2017
Abstract
Em um Problema de Escalonamento de Projetos com Restrição de Recursos e
Precedências Generalizadas (RCPSP/Max, do inglês Resource Constrained Project Scheduling
Problem with Generalized Precedences), deseja-se escalonar no tempo e sem preempção um
conjunto de atividades de duração conhecida, satisfazendo restrições de precedência com
intervalos de tempo (time lags) variáveis e respeitando as disponibilidades dos recursos
utilizados por cada atividade, de modo a minimizar a duração do projeto, chamada de
makespan. Este trabalho tem como objetivo o desenvolvimento de um método computacional
para encontrar e provar a otimalidade de soluções para o RCPSP/Max.
Neste trabalho, é apresentado um método exato para resolução do RCPSP/Max baseado
no Problema de Satisfabilidade em conjunto com relaxações pela carga de trabalho. O SAT é
utilizado para encontrar soluções e provar otimalidade. As relaxações pela Carga de Trabalho
visam reduzir o domínio das variáveis de decisão do problema, reduzindo o tamanho das
relaxações SAT geradas, e reduzir a amplitude da busca do makespan ótimo. Foram testadas
diversas formulações SAT para relaxações da versão viabilidade do RCPSP/Max. Para
melhorar o desempenho da resolução do SAT, também são propostos propagadores
personalizados para inclusão de cláusulas sob demanda.
O procedimento foi testado em instâncias do RCPSP/Max que têm de 10 a 500
atividades e 5 recursos, para instâncias do RCPSP (um caso particular com precedências
clássicas) que têm de 30 a 120 atividades e 4 recursos e para instâncias do Open Shop. Das
4662 instâncias consideradas, foram resolvidas 124 instâncias previamente não resolvidas em
até 600s e 146 até 3600s. Também melhoramos os limites para 234 instâncias. De forma geral,
o método proposto nesta Tese obteve maior quantidade de instâncias resolvidas em tempo de
processamento inferior aos melhores métodos previamente conhecidos na Literatura para o
RCPSP/Max e para o RCPSP
[Texto sem Formatação]
[Texto sem Formatação]
Document type
TeseSource
AZEVEDO, Guilherme Henrique Ismael de. Escalonamento de projetos com restrição de recursos e precedências generalizadas: um método exato de resolução. 2017. 168 f. (Doutorado em Engenharia de Produção) – Programa de Pós-Graduação em Engenharia de Produção, Universidade Federal Fluminense, Niterói, 2017.Subject(s)
OtimizaçãoEscalonamento de projetos
Restrição de recursos
Restrição de carga de trabalho
Problema de satisfabilidade
Escalonamento de projeto
Otimização combinatória
Restrição de recurso
Optimization
Project scheduling
Resource constraint
Workload constraint
Satisfiability problem