Unreliability evaluation for a limited-flow network with failed nodes subject to the budget constraint. (English) Zbl 1094.94004

Summary: This paper concentrates on a limited-flow network in which each node and branch has a designated capacity, which will have different lower levels due to various partial and complete failures. We try to evaluate the system unreliability that the maximum flow of the network is less than or equal to the demand \(d\) without exceeding the budget \(B\). First, a simple algorithm in terms of minimal cuts is proposed to generate all (\(d, B\))-MCs in order to evaluate the system unreliability. A computer example is shown to illustrate the solution procedure.


94A05 Communication theory
68M10 Network design and communication in computer systems
68M15 Reliability, testing and fault tolerance of networks and computer systems
Full Text: DOI


[1] Aggarwal, K.K.; Rai, S., Symbolic reliability evaluation using logical signal relations, IEEE transactions on reliability, 27, 202-205, (1978) · Zbl 0385.90049
[2] Fard, N.S.; Lee, T.H., Cutset enumeration of network systems with link and node failures, Reliability engineering and system safety, 65, 141-146, (1999)
[3] Malinowski, J.; Preuss, W., A parallel algorithm evaluating the reliability of a system with known minimal cuts (paths), Microelectronics and reliability, 37, 255-265, (1997)
[4] Aggarwal, K.K.; Gupta, J.S.; Misra, K.B., A simple method for reliability evaluation of a communication system, IEEE transactions on communications, 23, 563-565, (1975) · Zbl 0349.94003
[5] Aggarwal, K.K.; Chopra, Y.C.; Bajwa, J.S., Capacity consideration in reliability analysis of communication systems, IEEE transactions on reliability, 31, 177-180, (1982) · Zbl 0485.90046
[6] Lee, S.H., Reliability evaluation of a flow network, IEEE transactions on reliability, 29, 24-26, (1980) · Zbl 0428.90024
[7] Lee, D.W.; Yum, B.J., Determination of minimal upper paths for reliability analysis of planar flow networks, Reliability engineering and system safety, 39, 1-10, (1999)
[8] Rueger, W.J., Reliability analysis of networks with capacity-constraints and failures at branches and nodes, IEEE transactions on reliability, 35, 523-528, (1986) · Zbl 0608.90036
[9] Clancy, D.P.; Gross, G.; Wu, F.F., Probability flows for reliability evaluation of multiarea power system interconnections, Electrical power and energy system, 5, 100-114, (1985)
[10] Doulliez, P.; Jamoulle, J., Transportation networks with random arc capacities, RAIRO, rech. oper. res., 3, 45-60, (1972) · Zbl 0249.90025
[11] Evans, J.R., Maximal flow in probabilistic graphs—the discrete case, Networks, 6, 161-183, (1976) · Zbl 0339.90017
[12] Jane, C.C.; Lin, J.S.; Yuan, J., On reliability evaluation of a limited-flow network in terms of minimal cutsets, IEEE transactions on reliability, 42, 354-361, (1993) · Zbl 0795.90028
[13] Lin, Y.K., On reliability evaluation of a stochastic-flow network in terms of minimal cuts, Journal of Chinese institute of industrial engineers, 18, 49-54, (2001)
[14] Xue, J., On multistate system analysis, IEEE trans. reliability, 34, 329-337, (1985)
[15] Yeh, W.C., A simple approach to search for all d-MCs of a limited-flow network, Reliability engineering and system safety, 71, 15-19, (2001)
[16] Lin, Y.K., A simple algorithm for reliability evaluation of a stochastic-flow network with node failure, Computers and operations research, 28, 1277-1285, (2001) · Zbl 0989.90015
[17] Lin, Y.K., Two-commodity reliability evaluation for a stochastic-flow network with node failure, Computers and operations research, 29, 1927-1939, (2002) · Zbl 1259.90011
[18] Ford, L.R.; Fulkerson, D.R., ()
[19] Griffith, W.S., Multistate reliability models, Journal of applied probability, 17, 735-744, (1980) · Zbl 0435.60088
[20] Lin, Y.K., Using minimal cuts to study the system capacity for a stochastic-flow network in two-commodity case, Computers and operations research, 30, 1595-1607, (2003) · Zbl 1039.90006
[21] Lin, Y.K., Study on the system capacity for a multicommodity stochastic-flow network with node failure, Reliability engineering and system safety, 78, 57-62, (2002)
[22] El-Neweihi, E.; Proschan, F.; Sethuraman, J., Multistate coherent systems, Journal of applied probability, 15, 675-688, (1978) · Zbl 0386.60061
[23] A.M., Al-Ghanim, A heuristic technique for generating minimal paths and cutsets of a general network, Computers and industrial engineering, 36, 45-55, (1999)
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.