An Exact Algorithm for the Resource-Constrained Project Scheduling Problem Based on a New Mathematical Formulation
- 1 May 1998
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Management Science
- Vol. 44 (5), 714-729
- https://doi.org/10.1287/mnsc.44.5.714
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. (1978). 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.Keywords
This publication has 26 references indexed in Scilit:
- A Branch-and-Bound Procedure for the Multiple Resource-Constrained Project Scheduling ProblemManagement Science, 1992
- A new heuristic solution method in resource-constrained project schedulingNaval Research Logistics (NRL), 1991
- An exact algorithm for the maximum clique problemOperations Research Letters, 1990
- Some efficient multi-heuristic procedures for resource-constrained project schedulingEuropean Journal of Operational Research, 1990
- Solving resource-constrained project scheduling problems by a* searchNaval Research Logistics (NRL), 1990
- Project scheduling with resource constraints: A branch and bound approachEuropean Journal of Operational Research, 1987
- Scheduling subject to resource constraints: classification and complexityDiscrete Applied Mathematics, 1983
- Heuristics for Scheduling Resource-Constrained Projects: An Experimental InvestigationManagement Science, 1976
- A Comparison of Heuristic and Optimum Solutions in Resource-Constrained Project SchedulingManagement Science, 1975
- An Algorithm for Optimal Project Scheduling under Multiple Resource ConstraintsManagement Science, 1971