A lagrangian relaxation and ACO hybrid for resource constrained project scheduling with discounted cash flows

Dhananjay Raghavan Thiruvady, Mark Wallace, Hanyu Gu, Andreas Schutt

    Research output: Contribution to journalArticleResearchpeer-review

    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 languageEnglish
    Pages (from-to)643-676
    Number of pages34
    JournalJournal of Heuristics
    Volume20
    Issue number6
    DOIs
    Publication statusPublished - 2014

    Keywords

    • Ant colony optimisation
    • Lagrangian relaxation
    • Net present value
    • Project scheduling

    Cite this

    @article{71d36bd609dc495f90eba7f2deba277e,
    title = "A lagrangian relaxation and ACO hybrid for resource constrained project scheduling with discounted cash flows",
    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.",
    keywords = "Ant colony optimisation, Lagrangian relaxation, Net present value, Project scheduling",
    author = "Thiruvady, {Dhananjay Raghavan} and Mark Wallace and Hanyu Gu and Andreas Schutt",
    year = "2014",
    doi = "10.1007/s10732-014-9260-3",
    language = "English",
    volume = "20",
    pages = "643--676",
    journal = "Journal of Heuristics",
    issn = "1381-1231",
    publisher = "Springer-Verlag London Ltd.",
    number = "6",

    }

    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 journalArticleResearchpeer-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 -