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 quite 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.
