Title
Resource Constrained Project Scheduling: Computing Lower Bounds by Solving Minimum Cut Problems
Authors
-
Publication
Extended abstract in: Algorithms - ESA'99, Jaroslav Nesetril (ed.), Lecture Notes in Computer Science 1643, Springer, Berlin, 1999, pages 139-150, Proceedings of the 7th Annual European Symposium on Algorithms.
Source
-
Classification
-
not available
Keywords
-
Scheduling, Project Scheduling, Lagrangian Relaxation, Subgradient Optimization, Minimum Cut
-
-
We propose a novel approach to compute bounds on the
objective function value of a wide class of
resource-constrained project scheduling problems.
The basis is a polynomial-time algorithm to solve
the following scheduling problem: Given a set of
activities with start-time dependent costs and
temporal constraints in the form of time windows,
find a feasible schedule of minimum total
cost. Motivated by a known result that this problem
can be formulated as a cardinality-constrained
stable set problem in comparability graphs, we show
how to reduce it to a minimum cut problem in an
appropriate directed graph. We then focus on an
application of this algorithm to different types of
resource-constrained project scheduling problems by
using it for the computation of lower bounds on the
objective function value via Lagrangian relaxation
of these problems. This approach shows to be
applicable to various problem settings, and an
extensive study based on widely accepted test beds
in project scheduling reveals that our algorithm
significantly improves upon other fast computable
lower bounds at very modest running times. For
problems with time windows, we obtain the best known
bounds for several instances, and for a class of
notoriously hard labor-constrained scheduling
problem with time-varying resources, we drastically
reduce the time to obtain the lower bounds based on
the corresponding LP relaxation. For
precedence-constrained scheduling with several
resource types, our bounds are again computed very
fast, and improve the bounds obtained in reasonable
time by all currently known algorithms.
See also
-
