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

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.

Authors:

• Weng Ming Chu

Keywords:

• Series/Parallel network
• Stochastic network
• Network reduction
• Interdictive Graph
• Complexity Index.

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.