×

A decomposition-based stochastic programming approach for the project scheduling problem under time/cost trade-off settings and uncertain durations. (English) Zbl 1231.90114

Summary: Resource allocation in project networks allows for the control of the processing time of an activity under time-cost tradeoff settings. In practice, project decisions are made in advance when activity durations are still highly uncertain. Given an activity-on-node project network and a set of execution modes for each activity, we consider the problem of deciding how and when to execute each activity to minimize project completion time or total cost with respect to captured activity durations. The inherent stochasticity is represented using a set of discrete scenarios in which each scenario is associated with a probability of occurrence and a realization of activity durations. In this paper, we propose a path-based two-stage stochastic integer programming approach in which the execution modes are determined in the first stage while the second stage performs activity scheduling according to the realizations of activity durations, hence, providing flexibility in the scheduling process at subsequent stages. The solution methodology is based on a decomposition algorithm which has been implemented and widely tested using a large number of test instances of varying size and uncertainty. The reported computational results demonstrate that the proposed algorithm converges fast to the optimal solution and present the benefits of using the stochastic model as opposed to the traditional deterministic model that considers only expected values of activity durations.

MSC:

90B15 Stochastic network models in operations research
90B36 Stochastic scheduling theory in operations research
90C15 Stochastic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Birge, J. R., The value of the stochastic solution in stochastic linear programs with fixed recourse, Mathematical Programming, 24, 314-325 (1982) · Zbl 0502.90065
[2] Hadjiconstantinou E, Klerides E. A new path-based cutting plane approach for the discrete time-cost tradeoff problem. Computational Management Science, doi:10.1007/s10287-009-0115-6.; Hadjiconstantinou E, Klerides E. A new path-based cutting plane approach for the discrete time-cost tradeoff problem. Computational Management Science, doi:10.1007/s10287-009-0115-6. · Zbl 1194.90039
[3] Wollmer, R. D., Critical path planning under uncertainty, Mathematical Programming Study, 25, 164-171 (1985) · Zbl 0583.90101
[4] De, P.; Dunne, E. J.; Ghosh, J. B.; Wells, C. E., Complexity of the discrete time-cost tradeoff problem for project networks, Operations Research, 45, 2, 302-306 (1997) · Zbl 0893.90086
[5] Demeulemeester, E.; De Reyck, B.; Foubert, B.; Herroelen, W. S.; Vanhoucke, M., New computational results on the discrete time/cost trade-off problem in project networks, The Journal of the Operational Research Society, 49, 11, 1153-1163 (1998) · Zbl 1140.90439
[6] Skutella, M., Approximation algorithms for the discrete time-cost tradeoff problem, Mathematics of Operations Research, 23, 992-1020 (1998)
[7] Akkan, C.; Drexl, A.; Kimms, A., Network decomposition-based benchmark results for the discrete time-cost tradeoff problem, European Journal of Operational Research, 165, 2, 339-358 (2005) · Zbl 1066.90021
[8] De, P.; Dunne, E. J.; Ghosh, J. B.; Wells, C. E., The discrete time-cost tradeoff problem revisited, European Journal of Operational Research, 81, 225-238 (1995) · Zbl 0927.90046
[9] Brucker, P.; Drexl, A.; Mohring, R.; Neumann, K.; Pesch, E., Resource-constrained project scheduling: notation, classification, models, and methods, European Journal of Operational Research, 112, 1, 3-41 (1999) · Zbl 0937.90030
[10] Kolisch, R.; Padman, R., An integrated survey of deterministic project scheduling, Omega, 29, 3, 249-272 (2001)
[11] Demeulemeester, E. L.; Herroelen, W. S., Project scheduling: a research handbook (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Boston · Zbl 1059.90068
[12] Zhu, G.; Bard, J. F.; Yu, G., A two-stage stochastic programming approach for planning with uncertain activity durations, Journal of Scheduling, 10, 167-180 (2007) · Zbl 1168.90570
[13] Gutjahr, W., A stochastic branch-and-bound approach to activity crashing in project management, INFORMS Journal on Computing, 12, 2, 125 (2000) · Zbl 1034.90005
[14] Van Slyke, R. M.; Wets, R. J.B., L-shaped linear programs with applications to optimal control and stochastic programming, SIAM Journal on Applied Mathematics, 17, 638-663 (1986) · Zbl 0197.45602
[15] Wallace, S. W., Bounding the expected time-cost curve for a stochastic PERT network from below, Operations Research Letters, 8, 89-94 (1989) · Zbl 0674.90073
[16] Tavares, L. V.; ntunes Ferreira, J. A.; Coelho, J. S., On the optimal management of project risk, European Journal of Operational Research, 107, 2, 451-469 (1998) · Zbl 0943.90043
[17] Laslo, Z., Activity time-cost tradeoffs under time and cost chance constraints, Computers and Industrial Engineering, 44, 3, 365-384 (2003)
[18] Tereso, A. P.; Araujo, M. M.T.; Elmaghraby, S. E., Adaptive resource allocation in multimodal activity networks, International Journal of Production Economics, 92, 1-10 (2004)
[19] Tereso AP, Araujo MMT, Elmaghraby SE. Experimental results of an adaptive resource allocation technique to stochastic multimodal projects; 2003.; Tereso AP, Araujo MMT, Elmaghraby SE. Experimental results of an adaptive resource allocation technique to stochastic multimodal projects; 2003.
[20] Tereso AP, Araujo MMT, Elmaghraby SE. Basic approximations to an adaptive resource allocation technique to stochastic multimodal projects; 2003.; Tereso AP, Araujo MMT, Elmaghraby SE. Basic approximations to an adaptive resource allocation technique to stochastic multimodal projects; 2003.
[21] Herroelen, W.; Demeulemeester, E.; De Reyck, B., A classification scheme for project scheduling problems (1999), Kluwer Academic: Kluwer Academic Amsterdam, p. 1-26 [Chapter 1]
[22] Sherali, H.; Zhu, X., Two-stage fleet assignment model considering stochastic passenger demands, Operations Research, 56, 2, 383-399 (2008) · Zbl 1167.90387
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.