Reliability of a stochastic-flow network with unreliable branches and nodes, under budget constraints

System reliability evaluation for flow networks is an important issue in quality management. This paper concentrates on a stochastic-flow network in which nodes as well as branches have several possible capacities, and can fail. The possibility is evaluated that a given amount of messages can be transmitted through the stochastic-flow network under the budget constraint. Such a possibility, system reliability, is a performance index for a stochastic-flow network. A minimal path, an order sequence of nodes and branches from the source to the sink without cycles, is used to assign the flow to each component (branch or node). A lower boundary point for (d, C) is a minimal capacity vector, which enables the system to transmit d messages under the budget C. Based on minimal paths, an efficient algorithm is proposed to generate all lower boundary points for (d, C). The system reliability can then be calculated in terms of all lower boundary points for (d, C) by applying the inclusion–exclusion rule. Simulation shows that the implicit enumeration (step, 1) of the proposed algorithm can be executed efficiently.