direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 661-2000

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Resource-Constrained Project Scheduling: From a Lagrangian Relaxation to Competitive Solutions
4-page extended abstract, appeared in the Proceedings of the 7th International Workshop on Project Management and Scheduling, April 2000, pages 254-257.
not available
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.
Download as [PDF] [ps.gz]
See also
Title: Journal version

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe