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 dd units of data can be sent from the source to the sink under both time threshold TT and budget BB. 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,Bd,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.