Title
Resource-Constrained Project Scheduling: From a Lagrangian Relaxation to Competitive Solutions
Authors
-
Publication
4-page extended abstract, appeared in the
Proceedings of the 7th International Workshop on Project Management and Scheduling,
April 2000, pages 254-257.
Source
-
Classification
-
not available
Keywords
-
Scheduling, Project Scheduling, Lagrangian Relaxation, List Scheduling
-
-
List scheduling belongs to the classical and widely used algorithms
for scheduling problems, but for resource-constrained project
scheduling problems most standard priority lists do not capture
enough of the problem structure, often resulting in poor
performance. We use a well-known Lagrangian relaxation to first
compute schedules which do not necessarily respect the resource
constraints. We then apply list scheduling in the order of
so-called α-completion times of jobs. Embedded into a
standard subgradient optimization, our computational results show
that the schedules compare to those obtained by state-of-the-art
local search algorithms. In contrast to purely primal heuristics,
however, the Lagrangian relaxation also provides powerful lower
bounds, thus the deviation between lower and upper bounds can be
drastically reduced by this approach.
See also
-
