TY - JOUR

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

AU - Lin, Yi-Kuei

PY - 2011/9/1

Y1 - 2011/9/1

N2 - 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.

AB - 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.

KW - Budget

KW - Quickest path

KW - Stochastic flow network

KW - System state

KW - Time threshold

UR - http://www.scopus.com/inward/record.url?scp=80052402163&partnerID=8YFLogxK

U2 - 10.1016/j.camwa.2011.08.002

DO - 10.1016/j.camwa.2011.08.002

M3 - Article

AN - SCOPUS:80052402163

VL - 62

SP - 2629

EP - 2638

JO - Computers and Mathematics with Applications

JF - Computers and Mathematics with Applications

SN - 0898-1221

IS - 6

ER -