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

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