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

Hanyu Gu, Andreas Schutt, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

8 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationIntegration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 10th International Conference, CPAIOR 2013, Proceedings
PublisherSpringer
Pages340-346
Number of pages7
ISBN (Print)9783642381706
DOIs
Publication statusPublished - 1 Dec 2013
Externally publishedYes
EventInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2013 - Yorktown Heights, United States of America
Duration: 18 May 201322 May 2013
Conference number: 10th
https://link.springer.com/book/10.1007/978-3-642-38171-3 (Proceedings)

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7874 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2013
Abbreviated titleCPAIOR 2013
CountryUnited States of America
CityYorktown Heights
Period18/05/1322/05/13
Internet address

Cite this