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.