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

Yi-Kuei Lin*

*Corresponding author for this work

Research output: Contribution to journalArticle

13 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)1595-1607
Number of pages13
JournalComputers and Operations Research
Volume30
Issue number11
DOIs
StatePublished - 1 Sep 2003

Keywords

  • Minimal cuts
  • Performance index
  • Stochastic-flow network
  • System capacity
  • Two-commodity

Fingerprint Dive into the research topics of 'Using minimal cuts to study the system capacity for a stochastic-flow network in two-commodity case'. Together they form a unique fingerprint.

Cite this