Escalonamento de projetos com restrição de recursos e precedências generalizadas: um método exato de resolução

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorPessoa, Artur Alves-
Autor(es): dc.contributorBarboza, Eduardo Uchoa-
Autor(es): dc.contributorRoboredo, Marcos Costa-
Autor(es): dc.contributorAragão, Marcus Vinicius Soledade Poggi de-
Autor(es): dc.contributorSantos, Haroldo Gambini-
Autor(es): dc.creatorAzevedo, Guilherme Henrique Ismael de-
Data de aceite: dc.date.accessioned2024-07-11T17:38:15Z-
Data de disponibilização: dc.date.available2024-07-11T17:38:15Z-
Data de envio: dc.date.issued2018-09-24-
Data de envio: dc.date.issued2018-09-24-
Data de envio: dc.date.issued2017-
Fonte completa do material: dc.identifierhttps://app.uff.br/riuff/handle/1/7647-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/754346-
Descrição: dc.descriptionEm 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-
Descrição: dc.descriptionIn a Resource Constrained Project Scheduling Problem with Generalized Precedences (RCPSP/Max), one must schedule a set of activities with known duration in a time horizon, without preemption, satisfying precedence restrictions with variables time lags and respecting the availability of resources required for each activity. The goal is to minimize the project duration, also known as makespan. The objective of this study is to develop a computational method to find solutions and prove their optimality. In this work, we present an exact method to solve RCPSP/Max. Our procedure is based on the Satisfiability Problem and on workload relaxations. A reduction to SAT is used to find solutions and prove optimality. TheWorkload relaxations aim to reduce the size of the generated SAT relaxations by reducing the decision variables domain. It is also useful to reduce the search range for the optimal makespan. We have tested several reductions from the feasibility version of RCPSP/Max to SAT. For a better performance on solving SAT reductions, we also propose custom propagators to include clauses on demand inside the SAT solver. The proposed method was tested on RCPSP/Max instances with 10 to 500 activities and 5 resources, on RCPSP (a particular case with classical precedence constraints) with 30 to 120 activities and 4 resources and on Open Shop instances. Out of 4662 tested instances, we solved 124 previously unsolved ones in up to 600s and 146 instances until 3600s. Our method also improved bounds on the optimal makespan on 234 instances. Overall, the method here proposed solved more instances in less running time than the best-known methods in the Literature-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Direitos: dc.rightsopenAccess-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectOtimização-
Palavras-chave: dc.subjectEscalonamento de projetos-
Palavras-chave: dc.subjectRestrição de recursos-
Palavras-chave: dc.subjectRestrição de carga de trabalho-
Palavras-chave: dc.subjectProblema de satisfabilidade-
Palavras-chave: dc.subjectEscalonamento de projeto-
Palavras-chave: dc.subjectOtimização combinatória-
Palavras-chave: dc.subjectRestrição de recurso-
Palavras-chave: dc.subjectOptimization-
Palavras-chave: dc.subjectProject scheduling-
Palavras-chave: dc.subjectResource constraint-
Palavras-chave: dc.subjectWorkload constraint-
Palavras-chave: dc.subjectSatisfiability problem-
Título: dc.titleEscalonamento de projetos com restrição de recursos e precedências generalizadas: um método exato de resolução-
Título: dc.titleProject scheduling with resource constraints and generalized precedence: an exact method of resolution-
Tipo de arquivo: dc.typeTese-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.