Article ID: | iaor20121860 |
Volume: | 219 |
Issue: | 1 |
Start Page Number: | 73 |
End Page Number: | 85 |
Publication Date: | May 2012 |
Journal: | European Journal of Operational Research |
Authors: | Bianco Lucio, Caramia Massimiliano |
Keywords: | combinatorial optimization, programming: branch and bound |
In this paper we propose an exact algorithm for the Resource Constrained Project Scheduling Problem (RCPSP) with generalized precedence relationships (GPRs) and minimum makespan objective. For the RCPSP with GPRs we give a new mathematical formulation and a branch and bound algorithm exploiting such a formulation. The exact algorithm takes advantage also of a lower bound based on a Lagrangian relaxation of the same mathematical formulation. We provide an extensive experimentation and a comparison with known lower bounds and competing exact algorithms drawn from the state of the art.