Please use this identifier to cite or link to this item: https://app.uff.br/riuff/handle/1/7647
Title: Escalonamento de projetos com restrição de recursos e precedências generalizadas: um método exato de resolução
Other Titles: Project scheduling with resource constraints and generalized precedence: an exact method of resolution
Authors: Azevedo, Guilherme Henrique Ismael de
metadata.dc.contributor.advisor: Pessoa, Artur Alves
metadata.dc.contributor.members: Barboza, Eduardo Uchoa
Roboredo, Marcos Costa
Aragão, Marcus Vinicius Soledade Poggi de
Santos, Haroldo Gambini
Issue Date: 2017
Citation: 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.
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
metadata.dc.description.abstractother: In 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
URI: https://app.uff.br/riuff/handle/1/7647
Appears in Collections:PPGEP - Teses - Niterói

Files in This Item:
File Description SizeFormat 
Tese - Guilherme Azevedo - com ficha e assinaturas.pdf7.47 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.