Solving project scheduling problems by minimum cut computations

Solving project scheduling problems by minimum cut computations

0.00 Avg rating0 Votes
Article ID: iaor20032800
Country: United States
Volume: 49
Issue: 3
Start Page Number: 330
End Page Number: 350
Publication Date: Mar 2003
Journal: Management Science
Authors: , , ,
Keywords: programming: integer
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 progamming approach leads to both competitive feasible solutions and stong lower bounds, within reasonable computation times. The basic ingredients of our approach are the Lagrangian relaxation of a time-indexed integral programming formulation and relaxaton-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.

Reviews

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