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

doi:10.1007/978-3-642-38171-3_24

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 proceeding › Conference Paper › Research › peer-review

16 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 language	English
Title of host publication	Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 10th International Conference, CPAIOR 2013, Proceedings
Publisher	Springer
Pages	340-346
Number of pages	7
ISBN (Print)	9783642381706
DOIs	https://doi.org/10.1007/978-3-642-38171-3_24
Publication status	Published - 1 Dec 2013
Externally published	Yes
Event	International 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 2013 → 22 May 2013 Conference number: 10th https://link.springer.com/book/10.1007/978-3-642-38171-3 (Proceedings)

Publication series

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

Conference

Conference	International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2013
Abbreviated title	CPAIOR 2013
Country/Territory	United States of America
City	Yorktown Heights
Period	18/05/13 → 22/05/13
Internet address	https://link.springer.com/book/10.1007/978-3-642-38171-3 (Proceedings)

Access to Document

10.1007/978-3-642-38171-3_24

Cite this

Gu, H., Schutt, A., & Stuckey, P. J. (2013). A lagrangian relaxation based forward-backward improvement heuristic for maximising the net present value of resource-constrained projects. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 10th International Conference, CPAIOR 2013, Proceedings (pp. 340-346). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7874 LNCS). Springer. https://doi.org/10.1007/978-3-642-38171-3_24

Gu, Hanyu ; Schutt, Andreas ; Stuckey, Peter J. / A lagrangian relaxation based forward-backward improvement heuristic for maximising the net present value of resource-constrained projects. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 10th International Conference, CPAIOR 2013, Proceedings. Springer, 2013. pp. 340-346 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a084a7d6750243679b5c5298eea4739b,

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

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.",

author = "Hanyu Gu and Andreas Schutt and Stuckey, {Peter J.}",

year = "2013",

month = dec,

day = "1",

doi = "10.1007/978-3-642-38171-3_24",

language = "English",

isbn = "9783642381706",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "340--346",

booktitle = "Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 10th International Conference, CPAIOR 2013, Proceedings",

note = "International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2013, CPAIOR 2013 ; Conference date: 18-05-2013 Through 22-05-2013",

url = "https://link.springer.com/book/10.1007/978-3-642-38171-3",

}

Gu, H, Schutt, A & Stuckey, PJ 2013, A lagrangian relaxation based forward-backward improvement heuristic for maximising the net present value of resource-constrained projects. in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 10th International Conference, CPAIOR 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7874 LNCS, Springer, pp. 340-346, International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2013, Yorktown Heights, New York, United States of America, 18/05/13. https://doi.org/10.1007/978-3-642-38171-3_24

A lagrangian relaxation based forward-backward improvement heuristic for maximising the net present value of resource-constrained projects. / Gu, Hanyu; Schutt, Andreas; Stuckey, Peter J.
Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 10th International Conference, CPAIOR 2013, Proceedings. Springer, 2013. p. 340-346 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7874 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

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

AU - Gu, Hanyu

AU - Schutt, Andreas

AU - Stuckey, Peter J.

N1 - Conference code: 10th

PY - 2013/12/1

Y1 - 2013/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84892926193&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-38171-3_24

DO - 10.1007/978-3-642-38171-3_24

M3 - Conference Paper

AN - SCOPUS:84892926193

SN - 9783642381706

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 340

EP - 346

BT - Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 10th International Conference, CPAIOR 2013, Proceedings

PB - Springer

T2 - International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2013

Y2 - 18 May 2013 through 22 May 2013

ER -

Gu H, Schutt A, Stuckey PJ. A lagrangian relaxation based forward-backward improvement heuristic for maximising the net present value of resource-constrained projects. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 10th International Conference, CPAIOR 2013, Proceedings. Springer. 2013. p. 340-346. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-38171-3_24

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

Abstract

Publication series

Conference

Access to Document

Other files and links

Cite this