System capacity for a two-commodity multistate flow network with unreliable nodes and capacity weight

Yi-Kuei Lin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


The system capacity of a single-commodity flow network is the maximum flow from the source to the destination. This paper discusses the system capacity problem for a two-commodity multistate flow network composed of multistate components (edges and nodes). In particular, each component has both capacity and cost attributes. Both types of commodity, which are transmitted through the same network simultaneously, consume the capacities of edges and nodes differently. That is, the capacity weight varies with types of commodity, edges and nodes. We first define the system capacity as a 2-tuple vector and then propose a performance index, the probability that the upper bound of the system capacity is a given pattern subject to the budget constraint. Such a performance index can be easily computed in terms of upper boundary vectors. An efficient algorithm based on minimal cuts is thus presented to generate all upper boundary vectors. The manager can apply this performance index to measure the quality level of supply-demand systems such as computer, logistics, power transmission, telecommunication and urban traffic systems.

Original languageEnglish
Pages (from-to)3043-3054
Number of pages12
JournalComputers and Operations Research
Issue number10
StatePublished - 1 Oct 2007


  • Cost attribute
  • Minimal cut
  • Multistate flow network
  • Reliability
  • Two-commodity
  • Unreliable nodes

Fingerprint Dive into the research topics of 'System capacity for a two-commodity multistate flow network with unreliable nodes and capacity weight'. Together they form a unique fingerprint.

Cite this