Skip to main content
SpringerLink
Log in

Robust resource-constrained max-NPV project scheduling with stochastic activity duration

  • Regular Article
  • Published:
OR Spectrum Aims and scope Submit manuscript

Abstract

This study investigates the robust resource-constrained max-NPV project problem with stochastic activity duration. First, the project net present value (NPV) and the expected penalty cost are proposed to measure quality robustness and solution robustness from the perspective of discounted cash flows, respectively. Then, a composite robust scheduling model is proposed in the presence of activity duration variability and a two-stage algorithm that integrates simulated annealing and tabu search is developed to deal with the problem. Finally, an extensive computational experiment demonstrates the superiority of the combination between quality robustness and solution robustness as well as the effectiveness of the proposed two-stage algorithm for generating project schedules compared with three other algorithms, namely simulated annealing, tabu search, and multi-start iterative improvement method. Computational results indicate that the proactive project schedules with composite robustness not only can effectively protect the payment plan from disruptions through allocating appropriate time buffers, but also can achieve a remarkable performance with respect to the project NPV.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11

Similar content being viewed by others

Notes

  1. https://ww2.mathworks.cn/matlabcentral/fileexchange/67332-900-project-instances-are-randomly-constructed-by-the-project-generator-progen.

  2. https://ww2.mathworks.cn/matlabcentral/fileexchange/67333-computational-results.

References

  • Artigues C, Roubellat F (2000) A polynomial activity insertion algorithm in a multi-resource schedule with cumulative constraints and multiple modes. Eur J Oper Res 127(2):297–316

    Article  Google Scholar 

  • Artigues C, Michelon P, Reusser S (2003) Insertion techniques for static and dynamic resource-constrained project scheduling. Eur J Oper Res 149(2):249–267

    Article  Google Scholar 

  • Baroum SM, Patterson JH (1996) The development of cash flow weight procedures for maximizing the net present value of a project. J Oper Manag 14(3):209–227

    Article  Google Scholar 

  • Bey RB, Doersch RH, Patterson JH (1981) The net present value criterion: its impact on project scheduling. Proj Manag Q 12(2):35–45

    Google Scholar 

  • Bouleimen K, Lecocq H (2003) A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. Eur J Oper Res 49(2):268–281

    Article  Google Scholar 

  • Buss AH, Rosenblatt MJ (1997) Activity delay in stochastic project networks. Oper Res 45(1):126–139

    Article  Google Scholar 

  • Creemers S, Leus R, Lambrecht M (2010) Scheduling markovian pert networks to maximize the net present value. Oper Res Lett 38(1):51–56

    Article  Google Scholar 

  • Demeulemeester E, Herroelen W (1992) A branch-and-bound procedure for the multiple resource-constrained project scheduling problem. Manag sci 38(12):1803–1818

    Article  Google Scholar 

  • Demeulemeester E, Herroelen W (2011) Robust project scheduling. Found Trends Technol Inf Oper Manag 3(3–4):201–376

    Google Scholar 

  • Doersch RH, Patterson JH (1977) Scheduling a project to maximize its present value: a zero-one programming approach. Manag Sci 23(8):882–889

    Article  Google Scholar 

  • Elmaghraby SE (2005) On the fallacy of averages in project risk management. Eur J Oper Res 165(2):307–313

    Article  Google Scholar 

  • Gu H, Schutt A, Stuckey PJ, Wallace MG, Chu G (2015) Exact and heuristic methods for the resource-constrained net present value problem. In: Schwindt C, Zimmermann J (eds) Handbook on project management and scheduling. Springer, Berlin, pp 299–318

    Chapter  Google Scholar 

  • Hartmann S, Briskorn D (2008) A survey of variants and extensions of the resource-constrained project scheduling problem. Eur J Oper Res 207(1):1–14

    Article  Google Scholar 

  • He Z, Wang N, Jia T, Xu Y (2009) Simulated annealing and tabu search for multi-mode project payment scheduling. Eur J Oper Res 198(3):688–696

    Article  Google Scholar 

  • He Z, Liu R, Jia T (2012) Metaheuristics for multi-mode capital-constrained project payment scheduling. Eur J Oper Res 223(3):605–613

    Article  Google Scholar 

  • Herroelen W, Leus R (2001) On the merits and pitfalls of critical chain scheduling. J Oper Manag 19(5):559–577

    Article  Google Scholar 

  • Herroelen W, Leus R (2004) The construction of stable project baseline schedules. Eur J Oper Res 156(3):550–565

    Article  Google Scholar 

  • Herroelen W, Leus R (2005) Project scheduling under uncertainty: survey and research potentials. Eur J Oper Res 165(2):289–306

    Article  Google Scholar 

  • Herroelen W, Dommelen P, Demeulemeester E (1997) Project network models with discounted cash flows a guided tour through recent developments. Eur J Oper Res 100(1):97–121

    Article  Google Scholar 

  • Hu X, Cui N, Demeulemeester E (2015) Effective expediting to improve project due date and cost performance through buffer management. Int J Prod Res 53(5):1460–1471

    Article  Google Scholar 

  • Icmeli O, Erenguc SS (1994) A tabu search procedure for the resource constrained project scheduling problem with discounted cash flows. Comput Oper Res 21(8):841–853

    Article  Google Scholar 

  • Kahn AB (1962) Topological sorting of large networks. Commun ACM 5(11):558–562

    Article  Google Scholar 

  • Lambrechts O, Demeulemeester E, Herroelen W (2008) A tabu search procedure for developing robust predictive project schedules. Int J Prod Econ 111(2):493–508

    Article  Google Scholar 

  • Leus R (2004) The generation of stable project plans. Q J Belg Fr Ital Oper Res Soc 2(3):251–254

    Google Scholar 

  • Leus R, Herroelen W (2004) Stability and resource allocation in project planning. IIE Transactions 36(7):667–682

    Article  Google Scholar 

  • Leyman P, Vanhoucke M (2016) Payment models and net present value optimization for resource-constrained project scheduling. Comput Ind Eng 91:139–153

    Article  Google Scholar 

  • Mika M, Waligóra G, Wȩglarz J (2005) Simulated annealing and tabu search for multi-mode resource-constrained project scheduling with positive discounted cash flows and different payment models. Eur J Oper Res 164(3):639–668

    Article  Google Scholar 

  • Mika M, Waligóra G, Wȩglarz J (2008) Tabu search for multi-mode resource-constrained project scheduling with schedule-dependent setup times. Eur J Oper Res 187(3):1238–1250

    Article  Google Scholar 

  • Mohaghar A, Khoshghalb A, Rajabi M, Khoshghalb A (2016) Optimal delays, safe floats, or release dates? Applications of simulation optimization in stochastic project scheduling. Procedia Econ Finance 39:469–475

    Article  Google Scholar 

  • Neumann K, Schwindt C, Zimmermann J (2003) Order-based neighborhoods for project scheduling with nonregular objective functions. Eur J Oper Res 149(2):325–343

    Article  Google Scholar 

  • Russell AH (1970) Cash flows in networks. Manag Sci 16(5):357–373

    Article  Google Scholar 

  • Skorinkapov J (1990) Tabu search applied to the quadratic assignment problem. Orsa J Comput 2(1):33–45

    Article  Google Scholar 

  • Sobel MJ, Szmerekovsky JG, Tilson V (2009) Scheduling projects with stochastic activity duration to maximize expected net present value. Eur J Oper Res 198(3):697–705

    Article  Google Scholar 

  • Tantisuvanichkul V, Kidd M (2011) Maximizing net present value a review through literature. Int Proc Econ Dev Res 15(2):93–97

    Google Scholar 

  • Tukel OI, Rom WO, Eksioglu SD (2006) An investigation of buffer sizing techniques in critical chain scheduling. Eur J Oper Res 172(2):401–416

    Article  Google Scholar 

  • Vonder SVD, Demeulemeester E, Herroelen W, Leus R (2005) The use of buffers in project management: the trade-off between stability and makespan. Int J Prod Econ 97(2):227–240

    Article  Google Scholar 

  • Vonder SVD, Demeulemeester E, Herroelen W, Leus R (2006) The trade-off between stability and makespan in resource-constrained project scheduling. Int J Prod Res 44(2):215–236

    Article  Google Scholar 

  • Vonder SVD, Demeulemeester E, Herroelen W (2008) Proactive heuristic procedures for robust project scheduling: an experimental analysis. Eur J Oper Res 189(3):723–733

    Article  Google Scholar 

  • Wang J (2005) Constraint-based schedule repair for product development projects with time-limited constraints. J Prod Econ 95(3):399–414

    Article  Google Scholar 

  • Waligóra G (2014) Discrete-continuous project scheduling with discounted cash inflows and various payment model: a review of recent results. Ann Oper Res 213(1):319–340

    Article  Google Scholar 

  • Waligóra G (2014) Simulated annealing and tabu search for discrete-continuous project scheduling with discounted cash flows. RAIRO Oper Res 48(1):1–24

    Article  Google Scholar 

  • Waligóra G (2016) Comparative analysis of some metaheuristics for discrete-continuous project scheduling with activities of identical processing rates. Asia Pac J Oper Res 33(3):1650015

    Article  Google Scholar 

  • Wang Q, Zhang X, Mahadevan S, Deng Y (2015) Solving the longest path problem in directed acyclic graphs based on amoeba algorithm. Int J Unconv Comput 11(2):147–163

    Google Scholar 

  • Wiesemann W, Kuhn D, Rustem B (2010) Maximizing the net present value of a project under uncertainty. Eur J Oper Res 202(2):356–367

    Article  Google Scholar 

  • Zheng W, He Z, Wang N (2017) Proactive and reactive resource-constrained max-NPV project scheduling with random activity duration. J Oper Res Soc 2(2):1–12

    Google Scholar 

  • Zhu G, Bard JF, Yu G (2005) Disruption management for resource-constrained project scheduling. J Oper Res Soc 56(4):365–381

    Article  Google Scholar 

Download references

Acknowledgements

This work was supported by the National Natural Science Foundation of China [Grant numbers: 71271097, 71701073, and 71701067]. We would also like to acknowledge the Research Center for Operations Management of the KU Leuven for providing support to Yangyang Liang and Tian Wang as visiting research associates.

Author information

Authors and Affiliations

  1. Research Center of Hubei Logistics development, Hubei University of Economics, Wuhan, People’s Republic of China

    Yangyang Liang

  2. School of Management, Huazhong University of Science and Technology, Wuhan, People’s Republic of China

    Nanfang Cui

  3. School of Business Administration, Zhongnan University of Economics and Law, Wuhan, People’s Republic of China

    Tian Wang

  4. Research Center for Operations Management, Department of Decision Sciences and Information Management, Faculty of Economics and Business, Katholieke Universiteit Leuven, Leuven, Belgium

    Erik Demeulemeester

Authors
  1. Yangyang Liang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nanfang Cui
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tian Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Erik Demeulemeester
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tian Wang.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Liang, Y., Cui, N., Wang, T. et al. Robust resource-constrained max-NPV project scheduling with stochastic activity duration. OR Spectrum 41, 219–254 (2019). https://doi.org/10.1007/s00291-018-0533-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00291-018-0533-3

Keywords

Search

Navigation