A lagrangian relaxation based forward-backward improvement heuristic for maximising the net present value of resource-constrained projects

Publication Type:
Conference Proceeding
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2013, 7874 LNCS pp. 340 - 346
Issue Date:
Filename Description Size
Thumbnail2012007927OK.pdf Published version234.79 kB
Adobe PDF
Full metadata record
In this paper we propose a forward-backward improvement heuristic for the variant of resource-constrained project scheduling problem aiming to maximise the net present value of a project. It relies on the Lagrangian relaxation method to generate an initial set of schedules which are then improved by the iterative forward/backward scheduling technique. It greatly improves the performance of the Lagrangian relaxation based heuristics in the literature and is a strong competitor to the best meta-heuristics. We also embed this heuristic into a state-of-the-art CP solver. Experimentation carried out on a comprehensive set of test data indicates we compare favorably with the state of the art. © Springer-Verlag 2013.
Please use this identifier to cite or link to this item: