An Exact Algorithm for the Resource-Constrained Project Scheduling Problem Based on a New Mathematical Formulation

Aristide Mingozzi, Vittorio Maniezzo, Salvatore Ricciardelli and Lucio Bianco
Additional contact information
Aristide Mingozzi: Department of Mathematics, University of Bologna, Bologna, Italy
Vittorio Maniezzo: Department of Mathematics, University of Bologna, Bologna, Italy
Salvatore Ricciardelli: Department of Electrical Engineering, University Tor Vergata, Rome, Italy
Lucio Bianco: Department of Electrical Engineering, University Tor Vergata, Rome, Italy

Management Science, 1998, vol. 44, issue 5, 714-729

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: Project Scheduling; Branch-and-Bound Methods; Networks/Graphs; Lower Bounds (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (53)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.44.5.714 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:44:y:1998:i:5:p:714-729

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().