Finding All the Upper Boundary Points of a Stochastic-Flow Network with Budget Constraints

Finding All the Upper Boundary Points of a Stochastic-Flow Network with Budget Constraints

Abstract

Recently, several algorithms have been proposed for computing system reliability and unreliability as two frequent performance indices. Here, we make use of a performance index to measure the performance for a stochastic-flow network. The index is the probability of being the maximum flow from source to sink being equal to a given demand level d subject to a budget constraint. The index can be determined in terms of all upper boundary points. Presenting some useful results to decrease the number of candidates, an improved algorithm is proposed to find all the constrained upper boundary points. The time complexity of the algorithm is established, showing its efficiency as compared to other algorithms. Moreover, a medium-size network is employed to provide an intuitive understanding of the efficiency of the algorithm. Using the obtained results, the performance index of the example is computed by the sum of disjoint product approach.

References