An efficient Activity Network Reduction Algorithm based on the Label Correcting Tracing Algorithm

Authors: Weng Ming Chu

Abstract:

When faced with stochastic networks with an uncertain duration for their activities, the securing of network completion time becomes problematical, not only because of the non-identical pdf of duration for each node, but also because of the interdependence of network paths. As evidenced by Adlakha & Kulkarni [1], many methods and algorithms have been put forward in attempt to resolve this issue, but most have encountered this same large-size network problem. Therefore, in this research, we focus on network reduction through a Series/Parallel combined mechanism. Our suggested algorithm, named the Activity Network Reduction Algorithm (ANRA), can efficiently transfer a large-size network into an S/P Irreducible Network (SPIN). SPIN can enhance stochastic network analysis, as well as serve as the judgment of symmetry for the Graph Theory.

Keywords: Series/Parallel network, Stochastic network, Network reduction, Interdictive Graph, Complexity Index.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1086173

References:

[1] Adlakha, V.G. & Kulkarni, V.G., "A classified bibliography of research on stochastic PERT networks: 1966-1987", Information Systems and Operational Research, 27, n3, 272-296, 1989.
[2] Bein,W.W., Kamburowski, J. and Stallmann, M.F.M., "Optimal reduction of two-terminal directed acyclic graphs," SIAM J. Computing, 21, 1112-1129, 1992.
[3] Burt J.M., Garman M.B., "Conditional Monte Carlo: A simulation technique for stochastic network analysis", Management Science, 18, 3, 1971.
[4] Colby, A.H., Elmaghraby S.E., "On the complete reduction of directed acyclic graphs", OR Report No. 197, N.C. State Univ., Raleigh, NC., 1984.
[5] Dodin, B.M., "Determining the K most critical paths in PERT networks", Operations Research, 32, n4, 859-877, 1984.
[6] Dodin, B.M., "Approximating the distribution function in stochastic networks",Computers and Operations Research, 12, n3, 251-264,1985.
[7] Duffin, R, "Topology ofseries-parallel networks", J. Math. Anal. Appl., 10, pp. 303-318, 1965.
[8] Fisher, D.L., Saisi, D. & Goldstein, W.M., "Stochastic PERT networks: op diagrams, critical paths and the project completion time", Computers and Operations Research,12-5, 471-482, 1985.
[9] Harley, H.O., Wortham, A.W., "A statistical theory for PERT critical path analysis", Management Science, 12, n 10, 469-481, 1966.
[10] Kamburowski, J., Michael, D.J., Stallman, M.F.M., "Minimizing the complexity index of an activity network", Networks, 36, 47-52, 2000.
[11] Kleindorfer G.B., "Bounding distributions for stochastic logic", Operations Research, 19, 7, 1586-1601, 1971.
[12] Kleindorfer, G.B., "Bounding distributions for a stochastic acyclic network", Journal of Operations Research, 19-7, 1586-1601, 1977.
[13] Martin, J.J., "Distribution of the time through a directed acyclic network", Operational Research, 13, 46-66, 1965.
[14] Ringer, L.J., "Numerical operators for statistical PERT critical path analysis", Management Science, 16, 136-143, 1969.
[15] Robillard, P., Trahan, M., "The completion time of PERT networks", Operations Research. 25, 15-29, 1977.
[16] Sahner R.A., Trivedi K.S., "Performance and reliability analysis using directed acyclic graphs", IEEE Transactions on Software Engineering, 13, 1105-1114, 1987.
[17] Splde, J.G., "Bounds for the distribution function of network variables", First Symposium of Operations Research, 3, 113-123, 1977.
[18] Van, Slyke, R.M., "Monte Carlo methods and the PERT problem", Operations Research, 11, 839-861, 1963.
[19] Yao, M.J., Chu, W.M., Tseng, T.Y., "A Label-Correcting Tracing Algorithm for the Approximation of the Probability Distribution Function of the Project Completion Time", Journal of Chinese Institute of Industrial Engineers, 24-2, p.153~165, March 2007.
[20] Yao, M.J., Chu, W.M., "A New Approximation Algorithm for Obtaining the Probability Distribution Function of the Project Completion Time", Computers and Mathematics with Applications., 54-2, p. 282~295, July 2007.