Nuevos métodos de resolución del problema de secuenciación de proyectos con recursos limitados

Abstract

The Resource Constrained Project Scheduling Project (RCPSP) is an optimisation problem, which is considered to be the most important basic problem in scheduling under resource constrains. Due to the fact that the RCPSP is the basis of several problems, every improvement in its resolution can produce new advances in the resolution of the other problems. We have developed three heuristic algorithms for the RCPSP, combining metaheuristic ideas with problem-specific procedures. According to the computational results, one of our algorithms is at least competitive with the state-of-the-art heuristic algorithms, whereas the other two clearly outperform them. In the developing of these algorithms we have introduced several concepts that are interrelated with the possible solutions of the problem. We have also described some of their properties. These elements are important by themselves, and can be used in other heuristic algorithms. Another essential feature of the PhD. has been the proof that two existing techniques, the justification and the backward scheduling, are much more important than what it is reflected in the literature. The most important theoretical innovations has been the definition, for the first time in the RCPSP, of distances between possible solutions, the creation of a theoretical framework for the justification and the analysis of the problems that arise when peaks, the key element in our best algorithm, are combined.