Stochastic flow networks via multiple paths under time threshold and budget constraint

This paper extends the quickest path problem to a stochastic flow network in which the capacity of each arc is variable. We mainly evaluate the system reliability that d units of data can be sent from the source to the sink under both time threshold T and budget B. In particular, the data are transmitted through multiple disjoint minimal paths simultaneously in order to reduce the transmission time. A simple algorithm is proposed to generate all lower boundary points for (d,T,B), and the system reliability can then be computed in terms of such points by utilizing a union of subsets. Computational complexity in both worst case and average cases show that the proposed algorithm can be executed efficiently.