Lagrangean relaxation for scheduling projects under resource constraints to maximize the net present value

Arbeitspapier

Resource-constrained project scheduling under a net present value objective attracts growing interest. Because this is an NP-hard problem, it is unlikely that optimum solutions can be computed for large instances. Thus, heuristics have become a popular research field. Up to now, however, tight upper bounds have not been proposed. Therefore, most researchers evaluate their heuristics on the basis of a best known lower bound, but it is unclear how good the performance really is. With this contribution we close this gap and derive tight upper bounds on the basis of a Lagrangean relaxation of the resource constraints. We also use this approach as a basis for a heuristic and show that our heuristic as well as the cash flow weight heuristic proposed by Baroum and Patterson yield solutions very close to the optimum result. Furthermore, we discuss the proper choice of a test-bed, and, by reviewing the literature, emphasize that discount rates must be carefully chosen to give realistic instances.

Angaben zum Objekt

• Sprache: Englisch

Verweise und Beziehungen

• Erschienen in: Series: Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel ; No. 504

Klassifikation und Themen

• Klassifikation: Management
• Thema: Resource-constrained project scheduling ; net present value ; Lagrangean relaxation ; heuristics ; Scheduling-Verfahren ; Projektmanagement ; Dynamische Investitionsrechnung ; Mathematische Optimierung ; Theorie

Beteiligte, Orts- und Zeitangaben

• Ereignis: Geistige Schöpfung
• (wer): Kimms, Alf
• Ereignis: Veröffentlichung
• (wer): Universität Kiel, Institut für Betriebswirtschaftslehre ; ZBW – Leibniz Information Centre for Economics
• (wo): Kiel
• (wann): 1999

Weitere Informationen

• Handle: http://hdl.handle.net/10419/147592
• Letzte Aktualisierung: 10.03.2025, 11:46 MEZ