Kimms, Alf:
Maximizing the Net Present Value of a Project Under Resource Constraints Using a Lagrangian Relaxation Based Heuristic with Tight Upper Bounds.
In: Annals of Operations Research, Jg. 102 (2001), Heft 1/4, S. 221 - 236
2001Artikel/Aufsatz in Zeitschrift
WirtschaftswissenschaftenMercator School of Management - Fakultät für Betriebswirtschaftslehre
Damit verbunden: 1 Publikation(en)
Titel:
Maximizing the Net Present Value of a Project Under Resource Constraints Using a Lagrangian Relaxation Based Heuristic with Tight Upper Bounds.
Autor*in:
Kimms, AlfUDE
LSF ID
15707
Sonstiges
der Hochschule zugeordnete*r Autor*in
Erscheinungsjahr:
2001

Abstract:

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 within reasonable computation time. Thus, heuristics have become a popular research field. Up to now, however, upper bounds are not well researched. 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 Lagrangian 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 emphasize that discount rates must be carefully chosen to give realistic instances.