×

A new approach to determine the critical path in stochastic activity network. (English) Zbl 1407.90088

Summary: The determination of the critical path (CP) in stochastic networks is difficult. It is partly due to the randomness of path durations and partly due to the probability issue of the selection of the critical path in the network. What we are confronted with is not only the complexity among random variables but also the problem of path dependence of the network. Besides, we found that CP is not necessarily the longest (or shortest) path in the network, which was a conventional assumption in use. The Program Evaluation and Review Technique (PERT) and Critical Path Index (CPI) approaches are not able to deal with this problem efficiently. In this study, we give a new definition on the CP in stochastic network and propose a modified label-correcting tracing algorithm (M-LCTA) to solve it. Based on the numerical results, compared with Monte Carlo simulation (MCS), the proposed approach can accurately determine the CP in stochastic networks.

MSC:

90B15 Stochastic network models in operations research
90C35 Programming involving graphs or networks

Software:

PSPLIB
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Elmaghraby, S. E., Activity Networks: Project Planning and Control by Network Models (1977), New York, NY, USA: John Wiley & Sons, New York, NY, USA · Zbl 0385.90076
[2] Adlakha, V. G.; Kulkarni, V. G., A classified bibliography of research on stochastic PERT networks: 1966-1987, Information Systems and Operational Research, 27, 3, 272-296 (1989) · Zbl 0678.90033
[3] Hagstrom, J. N., Computational complexity of PERT problems, Networks, 18, 2, 139-147 (1988) · doi:10.1002/net.3230180206
[4] Gallagher, C. A., Note on PERT assumption, Management Science, 33, 1360-1362 (1987) · doi:10.1287/mnsc.33.10.1360
[5] Martin, J. J., Distribution of the time through a directed, acyclic network, Operations Research, 13, 46-66 (1965) · Zbl 0137.39302
[6] van Slyke, R. M., Monte Carlo methods and the PERT problem, Operations Research, 11, 839-861 (1963) · doi:10.1287/opre.11.5.839
[7] Sigal, C. E.; Pritsker, A. A. B.; Solberg, J. J., The use of cutsets in Monte Carlo analysis of stochastic networks, Mathematics and Computers in Simulation, 21, 4, 376-384 (1979) · Zbl 0416.90030 · doi:10.1016/0378-4754(79)90007-7
[8] Dodin, B., Determining the \(K\) most critical paths in PERT networks, Operations Research, 32, 4, 859-877 (1984) · Zbl 0546.90045 · doi:10.1287/opre.32.4.859
[9] Dodin, B. M.; Elmaghraby, S. E., Approximating the criticality indices of the activities in PERT networks, Management Science, 31, 2, 207-223 (1985) · Zbl 0607.90044 · doi:10.1287/mnsc.31.2.207
[10] Elmaghraby, S. E., On criticality and sensitivity in activity networks, European Journal of Operational Research, 127, 2, 220-238 (2000) · Zbl 0990.90119 · doi:10.1016/S0377-2217(99)00483-X
[11] Fatemi Ghomi, S. M. T.; Teimouri, E., Path critical index and activity critical index in PERT networks, European Journal of Operational Research, 141, 1, 147-152 (2002) · Zbl 0998.90009 · doi:10.1016/S0377-2217(01)00268-5
[12] Kamburowski, J., An upper bound on the expected completion time of PERT networks, European Journal of Operational Research, 21, 2, 206-212 (1985) · Zbl 0569.90047 · doi:10.1016/0377-2217(85)90032-3
[13] Kamburowski, J., Normally distributed activity durations in pert networks, Journal of the Operational Research Society, 36, 11, 1051-1057 (1985) · Zbl 0579.90052
[14] Loui, R. P., Optimal paths in graphs with stochastic or multidimensional weights, Communications of the Association for Computing Machinery, 26, 9, 670-676 (1983) · Zbl 0526.90085 · doi:10.1145/358172.358406
[15] Mirchandani, P. B.; Soroush, H., Optimal paths in probabilistic networks: a case with temporary preferences, Computers & Operations Research, 12, 4, 365-381 (1985) · Zbl 0607.90086 · doi:10.1016/0305-0548(85)90034-6
[16] Murthy, I.; Sarkar, S., A relaxation-based pruning technique for a class of stochastic shortest path problems, Transportation Science, 30, 3, 220-236 (1996) · Zbl 0879.90093
[17] Corea, G. A.; Kulkarni, V. G., Shortest paths in stochastic networks with arc lengths having discrete distributions, Networks, 23, 3, 175-183 (1993) · Zbl 0788.90029 · doi:10.1002/net.3230230305
[18] Polychronopoulos, G. H.; Tsitsiklis, J. N., Stochastic shortest path problems with recourse, Networks, 27, 2, 133-143 (1996) · Zbl 0851.90129
[19] Yao, M.-J.; Chu, W.-M., A new approximation algorithm for obtaining the probability distribution function for project completion time, Computers & Mathematics with Applications, 54, 2, 282-295 (2007) · Zbl 1235.62149 · doi:10.1016/j.camwa.2007.01.036
[20] Dodin, B., Approximating the distribution functions in stochastic networks, Computers and Operations Research, 12, 3, 251-264 (1985) · Zbl 0606.90047
[21] Agrawal, M. K.; Elmaghraby, S. E., On computing the distribution function of the sum of independent random variables, Computers and Operations Research, 28, 473-483 (2001) · Zbl 0973.65005
[22] Tereso, A. P.; Araújo, M. M. T.; Elmaghraby, S. E., Adaptive resource allocation in multimodal activity networks, International Journal of Production Economics, 92, 1, 1-10 (2004) · doi:10.1016/j.ijpe.2003.09.005
[23] Kolisch, R.; Sprecher, A., PSPLIB—a project scheduling problem library, European Journal of Operational Research, 96, 1, 205-216 (1996) · Zbl 0947.90587
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.