Detalhes bibliográficos
| Ano de defesa: |
2017 |
| Autor(a) principal: |
Azevedo, Guilherme Henrique Ismael de |
| Orientador(a): |
Não Informado pela instituição |
| Banca de defesa: |
Não Informado pela instituição |
| Tipo de documento: |
Tese
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
por |
| Instituição de defesa: |
Não Informado pela instituição
|
| Programa de Pós-Graduação: |
Não Informado pela instituição
|
| Departamento: |
Não Informado pela instituição
|
| País: |
Não Informado pela instituição
|
| Palavras-chave em Português: |
|
| Link de acesso: |
https://app.uff.br/riuff/handle/1/7647
|
Resumo: |
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 |
