TY - JOUR

T1 - Using minimal cuts to study the system capacity for a stochastic-flow network in two-commodity case

AU - Lin, Yi-Kuei

PY - 2003/9/1

Y1 - 2003/9/1

N2 - Traditionally, the flow network is assumed to allow a single type of commodity to transmit through it. The system capacity is the maximum value of flow from the source to the sink. It is trivial that the system capacity is fixed for a deterministic flow network. However, for a stochastic-flow network (the capacity of each arc may have several possible values), the system capacity is not fixed. Hence, many authors proposed methods to calculate two performance indices, the probability that the system capacity is greater than d and the system capacity is less than d, for a level d in terms of minimal paths and minimal cuts, respectively. In the case that two types of commodities are transmitted through the stochastic-flow network, this paper uses the properties of minimal cuts to define the system capacity as a two-tuple vector and to propose an algorithm in order to evaluate a new performance index, the probability that the upper bound of system capacity is (d1, d2), for a level (d1, d2). The max-flow min-cut theorem states that for a deterministic flow network, the maximum value of the flow from s to t equals the minimum capacity of all s-t minimal cuts. Hence, we can use the minimal cuts to deal with the flow problems in network analysis. This paper studies the stochastic-flow network in which two or more types of commodities are transmitted through it. From the poit of view of quality management, it is an important issue to define the system capacity and then to develop some indices in order to evaluate the system performance. The existing performance index, the probability that the lower bound of the system capacity is (d1, d2) can be calculated in terms of minimal paths. The purpose of this paper is to use the properties of minimal cuts in order to define the system capacity for such a network. Then to develop a new performance index, the probability that the upper bound of the system capacity is (d1, d2), for a level (d1, d2) and to propose an algorithm to evaluate it. However, the two performance indices cannot convert into each other.

AB - Traditionally, the flow network is assumed to allow a single type of commodity to transmit through it. The system capacity is the maximum value of flow from the source to the sink. It is trivial that the system capacity is fixed for a deterministic flow network. However, for a stochastic-flow network (the capacity of each arc may have several possible values), the system capacity is not fixed. Hence, many authors proposed methods to calculate two performance indices, the probability that the system capacity is greater than d and the system capacity is less than d, for a level d in terms of minimal paths and minimal cuts, respectively. In the case that two types of commodities are transmitted through the stochastic-flow network, this paper uses the properties of minimal cuts to define the system capacity as a two-tuple vector and to propose an algorithm in order to evaluate a new performance index, the probability that the upper bound of system capacity is (d1, d2), for a level (d1, d2). The max-flow min-cut theorem states that for a deterministic flow network, the maximum value of the flow from s to t equals the minimum capacity of all s-t minimal cuts. Hence, we can use the minimal cuts to deal with the flow problems in network analysis. This paper studies the stochastic-flow network in which two or more types of commodities are transmitted through it. From the poit of view of quality management, it is an important issue to define the system capacity and then to develop some indices in order to evaluate the system performance. The existing performance index, the probability that the lower bound of the system capacity is (d1, d2) can be calculated in terms of minimal paths. The purpose of this paper is to use the properties of minimal cuts in order to define the system capacity for such a network. Then to develop a new performance index, the probability that the upper bound of the system capacity is (d1, d2), for a level (d1, d2) and to propose an algorithm to evaluate it. However, the two performance indices cannot convert into each other.

KW - Minimal cuts

KW - Performance index

KW - Stochastic-flow network

KW - System capacity

KW - Two-commodity

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

U2 - 10.1016/S0305-0548(02)00094-1

DO - 10.1016/S0305-0548(02)00094-1

M3 - Article

AN - SCOPUS:0037791894

VL - 30

SP - 1595

EP - 1607

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

IS - 11

ER -