Solving Project Scheduling Problems by Minimum Cut Computations

Rolf H. Möhring (), Andreas S. Schulz (), Frederik Stork () and Marc Uetz ()
Additional contact information
Rolf H. Möhring: Fakultät II, Institut für Mathematik, Technische Universität Berlin, Sekr. MA 6-1, Stra\beta e des 17. Juni 136, D-10623 Berlin, Germany
Andreas S. Schulz: Sloan School of Management, E53-361, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, Massachusetts 02139
Frederik Stork: ILOG Deutschland GmbH, Ober-Eschbacher Stra\beta e 109, D-61352 Bad Homburg, Germany
Marc Uetz: Faculty of Economics and Business Administration, Quantitative Economics, Universiteit Maastricht, P.O. Box 616, 6200 MD Maastricht, The Netherlands

Management Science, 2003, vol. 49, issue 3, 330-350

Abstract: In project scheduling, a set of precedence-constrained jobs has to be scheduled so as to minimize a given objective. In resource-constrained project scheduling, the jobs additionally compete for scarce resources. Due to its universality, the latter problem has a variety of applications in manufacturing, production planning, project management, and elsewhere. It is one of the most intractable problems in operations research, and has therefore become a popular playground for the latest optimization techniques, including virtually all local search paradigms. We show that a somewhat more classical mathematical programming approach leads to both competitive feasible solutions and strong lower bounds, within reasonable computation times. The basic ingredients of our approach are the Lagrangian relaxation of a time-indexed integer programming formulation and relaxation-based list scheduling, enriched with a useful idea from recent approximation algorithms for machine scheduling problems. The efficiency of the algorithm results from the insight that the relaxed problem can be solved by computing a minimum cut in an appropriately defined directed graph. Our computational study covers different types of resource-constrained project scheduling problems, based on several notoriously hard test sets, including practical problem instances from chemical production planning.

Keywords: Project Scheduling; Resource Constraints; Linear Programming Relaxation; Lagrangian Relaxation; Minimum Cut (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (32)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.49.3.330.12737 (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:49:y:2003:i:3:p:330-350

Access Statistics for this article

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