RELIABILITY EVALUATION OF A CAPACITATED-FLOW NETWORK IN TERMS OF MINIMAL PATHSETS

Many real-world systems such as electric power transmission and distribution systems, transportation systems, and manufacturing systems can be regarded as flow networks whose arcs have independent, finite, and multivalued random capacities. Such a flow network is indeed a multistate system with multistate components and so its reliability for the system demand d, i.e., the probability that the maximal flow is no less than d, can be computed in terms of minimal path vectors to level d (named d-MPs here). The main objective of this paper was to present a simple algorithm to generate all d-MPs of such a system for each system capacity level d in terms of minimal pathsets. Analysis of our algorithm and comparison to Xue's algorithm shows that our method has the following advantages: (1) the family of d-MP candidates that it generates is smaller in size and so d-MPs can be generated more efficiently, (2) it is expressed more intuitively and so easier to understand, and (3) whenever applied in a series-parallel case, both algorithms are essentially the same, but in a non series-parallel case, Xue's algorithm needs the extra work to transform the system into a series-parallel in advance. Two examples are illustrated to show how all d-MPs are generated by our algorithm and then the reliability of one example is computed. (C) 1995 John Wiley and Sons, Inc.