Parallel algorithms to solve the resource-constrained project scheduling problem (Spanish text).

摘要

This work contemplates the standard version of the Resource-Constrained Project Scheduling Problem, with the objective of obtaining a feasible schedule that minimises the duration of the project. This problem has a combinatory nature and belongs to the NP-hard problem class, and therefore, the number of possible solutions exponentially increases as the size of the problem increases.; Although the use of ever more powerful machines during the last decade has allowed the size and number of problems that are optimally solved to increase, the process of solving these problems keeps requiring a higher processing speed. Parallel computation seems a possible approach to reach a solution for these problems, since it uses the idea of work divided among a set of processors that co-operate on the solution of a single problem.; The goals of this work are focused on the development, adaptation and implementation of parallel algorithms to optimally solve this problem while considering the advantages and disadvantages of these methods. The reformulation and introduction of new concepts have been required in order to allow the accurate application of some dominance rules that cease to be valid when a parallel search for the optimal solution is performed.; The results obtained when solving the projects of 30 and 60 activities of the standard library PSPLIB, using a cluster of personal computers, have allowed us to evaluate the behaviour of the branch&bound parallel algorithms developed. These results demonstrate that parallel computation is an adequate technique to optimally solve the resource-constrained project scheduling problem. Furthermore, the truncated version of the algorithms designed can compete with some of the best heuristic algorithms published.