Please use this identifier to cite or link to this item:
Kimms, Alf
Year of Publication: 
Series/Report no.: 
Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 504
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.
Resource-constrained project scheduling
net present value
Lagrangean relaxation
Document Type: 
Working Paper

Files in This Item:

Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.