An exact algorithm for the resource-constrained Project Scheduling Problem based on a new mathematical formulation

An exact algorithm for the resource-constrained Project Scheduling Problem based on a new mathematical formulation

0.00 Avg rating0 Votes
Article ID: iaor19991779
Country: United States
Volume: 44
Issue: 5
Start Page Number: 714
End Page Number: 729
Publication Date: May 1998
Journal: Management Science
Authors: , , ,
Keywords: networks, programming: branch and bound, project management
Abstract:

In this paper we consider the Project Scheduling Problem with resource constraints, where the objective is to minimize the project makespan. We present a new 0–1 linear programming formulation of the problem that requires an exponential number of variables, corresponding to all feasible subsets of activities that can be simultaneously executed without violating resource or precedence constraints. Different relaxations of the above formulation are used to derive new lower bounds, which dominate the value of the longest path on the precedence graph and are tighter than the bound proposed by Stinson et al. A tree search algorithm, based on the above formulation, that uses new lower bounds and dominance criteria is also presented. Computational results indicate that the exact algorithm can solve hard instances that cannot be solved by the best algorithms reported in the literature.

Reviews

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