New heuristic and hybrid algorithms for the Dynamic Resource-Constrained Project Scheduling Problem

This Thesis presents new methods for solving Dynamics Resource-Contrained Project Scheduling Problem (DRCPSP). This kind of resource is different from others because it is consumed when a project task is activated, but is also produced at the end of this activation. Its maximum amount is not bounded like the renewable resources, which are very common in project scheduling problems. The objective of DRCPSP is to maximize the amount of resources at the end of a planning horizon, through the activation of tasks considered profitable. The DRCPSP may be used to model expansion projects of companies, where the main objective is to obtain the greatest possible amount of resources .It is proposed in this thesis a new mathematical model for the problem, as well as meta-heuristic algorithms and hybrid methods. Some tests showed that the evolutionary algorithms that use a specific form of representation of the solutions are quite efficient compared with other meta-heuristcs. Hybrid methods that use these evolutionary algorithms with the CPLEX optimizer had very good performance in several instances.Conselho Nacional de Desenvolvimento Cientifico e TecnológicoEsta tese apresenta novos métodos para resolver o Problema de Escalonamento de Projetos com Restrições de Recurso Dinâmicos (PEPRD).Este tipo de recurso é diferente dos demais porque é consumido quando uma tarefa do projeto é ativada, mas também é produzido ao final desta ativação. Sua quantidade máxima não é limitada como nos recursos renováveis, muito comuns em problemas de escalonamento de projetos. O objetivo do PEPRRD é maximizar quantidade de recursos ao final de um horizonte de planejamento, por meio da ativação de tarefas consideradas lucrativas. .O PEPRRD pode ser usado para modelar projetos de expansão de empresa, onde o objetivo principal é obter a maior quantidade possível de recursos. É proposta nesta tese uma nova modelagem matemática para o problema, bem como algoritmos meta-heurísticos e métodos híbridos. Alguns testes mostraram que os Algoritmos Evolutivos que utilizam uma forma específica de representação das soluções são bastante eficientes comparando com outras meta-heurísticas. Métodos híbridos que utilizam este evolutivo como otimizador CPLEX apresentaram desempenho muito bom em várias instâncias