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

Yi-Kuei Lin*

*此作品的通信作者

研究成果: Article同行評審

14 引文 斯高帕斯(Scopus)

摘要

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.

原文English
頁(從 - 到)1595-1607
頁數13
期刊Computers and Operations Research
30
發行號11
DOIs
出版狀態Published - 1 九月 2003

指紋

深入研究「Using minimal cuts to study the system capacity for a stochastic-flow network in two-commodity case」主題。共同形成了獨特的指紋。

引用此