Abstract
We consider a project scheduling problem where a number of tasks need to be scheduled. The tasks share resources, satisfy precedences, and all tasks must be completed by a common deadline. Each task is associated with a cash flow (positive or negative value) from which a “net present value” is computed dependent upon its completion time. The objective is to maximize the cumulative net present value of all tasks. We investigate (1) Lagrangian relaxation methods based on list scheduling, (2) ant colony optimization and hybrids of (1) and (2) on benchmark datasets consisting of up to 120 tasks. Considering lower bounds, i.e., maximizing the net present value, the individual methods prove to be effective but are outperformed by the hybrid method. This difference is accentuated when the integrality gaps are large.
| Original language | English |
|---|---|
| Pages (from-to) | 643-676 |
| Number of pages | 34 |
| Journal | Journal of Heuristics |
| Volume | 20 |
| Issue number | 6 |
| DOIs | |
| Publication status | Published - 2014 |
Keywords
- Ant colony optimisation
- Lagrangian relaxation
- Net present value
- Project scheduling
Cite this
}
A lagrangian relaxation and ACO hybrid for resource constrained project scheduling with discounted cash flows. / Thiruvady, Dhananjay Raghavan; Wallace, Mark; Gu, Hanyu; Schutt, Andreas.
In: Journal of Heuristics, Vol. 20, No. 6, 2014, p. 643-676.Research output: Contribution to journal › Article › Research › peer-review
TY - JOUR
T1 - A lagrangian relaxation and ACO hybrid for resource constrained project scheduling with discounted cash flows
AU - Thiruvady, Dhananjay Raghavan
AU - Wallace, Mark
AU - Gu, Hanyu
AU - Schutt, Andreas
PY - 2014
Y1 - 2014
N2 - We consider a project scheduling problem where a number of tasks need to be scheduled. The tasks share resources, satisfy precedences, and all tasks must be completed by a common deadline. Each task is associated with a cash flow (positive or negative value) from which a “net present value” is computed dependent upon its completion time. The objective is to maximize the cumulative net present value of all tasks. We investigate (1) Lagrangian relaxation methods based on list scheduling, (2) ant colony optimization and hybrids of (1) and (2) on benchmark datasets consisting of up to 120 tasks. Considering lower bounds, i.e., maximizing the net present value, the individual methods prove to be effective but are outperformed by the hybrid method. This difference is accentuated when the integrality gaps are large.
AB - We consider a project scheduling problem where a number of tasks need to be scheduled. The tasks share resources, satisfy precedences, and all tasks must be completed by a common deadline. Each task is associated with a cash flow (positive or negative value) from which a “net present value” is computed dependent upon its completion time. The objective is to maximize the cumulative net present value of all tasks. We investigate (1) Lagrangian relaxation methods based on list scheduling, (2) ant colony optimization and hybrids of (1) and (2) on benchmark datasets consisting of up to 120 tasks. Considering lower bounds, i.e., maximizing the net present value, the individual methods prove to be effective but are outperformed by the hybrid method. This difference is accentuated when the integrality gaps are large.
KW - Ant colony optimisation
KW - Lagrangian relaxation
KW - Net present value
KW - Project scheduling
UR - http://www.scopus.com/inward/record.url?scp=85027920704&partnerID=8YFLogxK
U2 - 10.1007/s10732-014-9260-3
DO - 10.1007/s10732-014-9260-3
M3 - Article
VL - 20
SP - 643
EP - 676
JO - Journal of Heuristics
JF - Journal of Heuristics
SN - 1381-1231
IS - 6
ER -