An exact algorithm to minimize the makespan in project scheduling with scarce resources and generalized precedence relations

An exact algorithm to minimize the makespan in project scheduling with scarce resources and generalized precedence relations

0.00 Avg rating0 Votes
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: ,
Keywords: combinatorial optimization, programming: branch and bound
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.