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

    21 Citations (Scopus)


    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
    Issue number6
    Publication statusPublished - 2014


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

    Cite this