Scheduling projects with stochastic activity duration to maximize expected net present value. (English) Zbl 1176.90264

Summary: Although uncertainty is rife in many project management contexts, little is known about adaptively optimizing project schedules. We formulate the problem of adaptively optimizing the expected present value of a project’s cash flow, and we show that it is practical to perform the optimization. The formulation includes randomness in activity durations, costs, and revenues, so the optimization leads to a recursion with a large state space even if the durations are exponentially distributed. We present an algorithm that partially exercises the “curse of dimensionality” as computational results demonstrate. Most of the paper is restricted to exponentially distributed task durations, but we sketch the adaptation of the algorithm to approximate any probability distribution of task duration.


90B36 Stochastic scheduling theory in operations research
90C39 Dynamic programming
Full Text: DOI


[1] Azaron, A.; Katagiri, H.; Sakawa, M.; Kato, K.; Memariani, A., A multi-objective resource allocation problem in PERT networks, European Journal of Operational Research, 172, 2, 838-854 (2006) · Zbl 1111.90051
[2] Benati, S., An optimization model for stochastic project networks with cash flows, Computational Management Science, 3, 271-284 (2006) · Zbl 1136.90009
[3] Bey, R. P.; Doersch, R. H.; Patterson, J. H., The net present value criterion: Its impact on project scheduling, Project Management Quarterly, 12, 35-45 (1981)
[4] Buss, A. H.; Rosenblatt, M. J., Activity delay in stochastic project networks, Operations Research, 45, 126-139 (1997) · Zbl 0892.90068
[5] Chitgopekar, S. S., Continuous time markov sequential control processes, SIAM Journal of Control, 17, 367-389 (1969) · Zbl 0184.19304
[6] Dayanand, N.; Padman, R., Project contracts and payment schedules: The client’s problem, Management Science, 47, 12, 1654-1667 (2001) · Zbl 1232.91404
[7] De Reyck, B.; Leus, R., R& D-project scheduling when activities may fail, IIE Transactions, 40, 4, 367-384 (2008)
[8] Elmaghraby, S. E., On the fallacy of averages in project risk management, European Journal of Operational Research, 165, 2, 307-313 (2005) · Zbl 1066.90530
[9] Goemans, M. X.; Williamson, D. P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the Association for Computing Machinery, 42, 1115-1145 (1995) · Zbl 0885.68088
[10] Hall, N. G.; Posner, M. E., Generating experimental data for computational testing with machine scheduling applications, Operations Research, 49, 7, 854-865 (2001) · Zbl 1163.90490
[11] Herroelen, W. S.; van Dommelen, P.; Demeulemeester, E. L., Project network models with discounted cash flows a guided tour through recent developments, European Journal of Operational Research, 100, 97-121 (1997) · Zbl 0947.90583
[12] Herroelen, W. S.; Leus, R., Project scheduling under uncertainty: Survey and research potentials, European Journal of Operational Research, 165, 289-306 (2005) · Zbl 1066.90050
[13] Howard, R., Dynamic Programming and Markov Processes (1960), MIT Press: MIT Press Cambridge, MA · Zbl 0091.16001
[14] Jørgensen, T.; Wallace, S. W., Improving project cost estimation by taking into account managerial flexibility, European Journal of Operational Research, 127, 2, 239-251 (2000) · Zbl 0985.90047
[15] Klastorin, T., Project Management: Tools and Trade-offs (2004), John Wiley: John Wiley Hoboken, NJ
[16] Kulkarni, V. G.; Adlakha, V. G., Markov and Markov-regenerative PERT networks, Operations Research, 34, 769-781 (1986) · Zbl 0615.90042
[17] Malcolm, D. G.; Roseboom, J. H.; Clark, C. E.; Fazar, W., Application of a technique for research and development program evaluation, Operations Research, 7, 5, 646-669 (1959) · Zbl 1255.90070
[18] Miller, B. L., Finite state continuous time Markov decision processes with an infinite planning horizon, Journal of Mathematical Analysis & Applications, 22, 552-569 (1968) · Zbl 0157.50301
[19] Russell, A. H., Cash flows in networks, Management Science, 16, 5, 357-373 (1970) · Zbl 0187.18201
[20] Serfozo, R. F., An equivalence between continuous and discrete time Markov decision processes, Operations Research, 27, 616-620 (1979) · Zbl 0413.90079
[21] Szmerekovsky, J. G., The impact of contractor behavior on the client’s payment-scheduling problem, Management Science, 51, 629-640 (2005) · Zbl 1145.90409
[23] Wolff, R. W., Stochastic Modeling and the Theory of Queues (1989), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ, pp. 269-270
[24] Zhang, H.; Tam, C. M.; Li, H., Modeling uncertain activity duration by fuzzy number and discrete-event simulation, European Journal of Operational Research, 164, 2, 715-729 (2005) · Zbl 1057.91507
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.