Many real-world systems such as electric power systems and transportation systems can be regarded as capacitated-flow networks. A multi-source multi-sink capacitated-flow network consists of a set of nodes, including source nodes that supply resources and sink nodes where resource demands are realized, and a set of directed arcs that carry resource flows, in which each arc has several operational states. The network reliability is defined as the probability that resource demands can be successfully transmitted form source nodes to sink nodes. In this study, an optimal resource allocation for a multi-source multi-sink capacitated-flow network under the cost constraint is proposed. For given demands, an algorithm is developed to obtain an optimal resource allocation that maximizes the network reliability subject to a specified transmission cost. When demands change, the optimal resource allocation will also be changed. An algorithm is developed for updating, rather than re-computing, the optimal resource allocation when demands change incrementally. Further, nodes may be unreliable. An efficient algorithm is also developed when internal nodes are unreliable in a multi-source multi-sink capacitated-flow network.

Ahuja, R. K., Magnanti, T. L. and Orlin, J. B. Network Flows-Theory, Algorithms, and Applications. Prentice-Hall, 1993.

Aven, T. Reliablilty evaluation of multistate systems with multistate components. IEEE Transactions on Reliability, 34(5), 473-479, 1985.

Doulliez, P. and Jamoulle, J. Transportation networks with random arc capacities. RAIRO, Recherche Operationnelle Operations Research, 3, 45-60, 1972.

Hsieh, C. C. and Huang, K. C. Optimal resource allocation on reliability maximization of a multi-source multi-sink flow network. Working Paper, 2001.

Hudson, J. C. and Kapur, K. C. Reliability analysis for multistate systems with multistate components. IIE Transactions, 15(2), 127-135, 1983.

Hudson, J. C. and Kapur, K. C. Reliability bounds for multistate systems with multistate components. Operations Research, 33(1), 153-160, 1985.

Jane, C. C., Lin, J. S. and Yuan, J. Reliability evaluation of a limited-flow network in terms of minimal cutsets. IEEE Transactions on Reliability, 42(3), 354-361, 1993.
Lee, S. H. Reliablilty evaluation of a flow network. IEEE Transactions on Reliability, 29(1), 24-26, 1980.

Lin, J. S. Reliability evaluation of capacitated-flow networks with budget constraints. IIE Transactions, 30, 1175-1180, 1998.

Lin, J. S., Jane, C. C. and Yuan, J. On reliability evaluation of a capacitated-flow network in terms of minimal pathsets. Networks, 25, 131-138, 1995.

Lin, Y. K. A simple algorithm for reliability evaluation of a stochastic-flow network with node failure. Computers & Operations Research, 28, 1277-1285, 2001a.

Lin, Y. K. Study on the multicommodity reliability of a capacitated-flow network. Computers and Mathematics with Applications, 42, 255-264, 2001b.

Lin, Y. K. Two-commodity reliability evaluation for a stochastic-flow network with node failure. Computers & Operations Research, 29, 1927-1939, 2002.

Xue, J. On multistate system analysis. IEEE Transactions on Reliability, 34(4), 329-337, 1985.

Yeh, W. C. A simple algorithm to search for all d-MPs with unreliable nodes. Reliability Engineering and System Safety, 73, 49-54, 2001a.

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, 2001b.

Yeh, W. C. A simple method to verify all d-minimal path candidates of a limited-flow network and its reliability. Int J Adv Manufacturing Technology, 20, 77-81, 2002.