Generate upper boundary vectors meeting the demand and budget for a p-commodity network with unreliable nodes

Yi-Kuei Lin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

The system capacity for a single-commodity flow network is the maximum flow from the source to the sink. This paper discusses the system capacity problem for a p-commodity limited-flow network with unreliable nodes. In such a network, arcs and nodes all have several possible capacities and may fail. Different types of commodity, which are transmitted through the same network simultaneously, competes the capacities of arcs and nodes. In particular, the consumed capacity by different types of commodity varies from arcs and nodes. We first define the system capacity as a vector and then a performance index, the probability that the upper bound of the system capacity is a given pattern subject to the budget constraint, is proposed. Such a performance index can be easily computed in terms of upper boundary vectors meeting the demand and budget. A simple algorithm based on minimal cuts is thus presented to generate all upper boundary vectors. The manager can apply this performance index to measure the system capacity level for a supply-demand system.

Original languageEnglish
Pages (from-to)253-262
Number of pages10
JournalEuropean Journal of Operational Research
Volume183
Issue number1
DOIs
StatePublished - 16 Nov 2007

Keywords

  • Budget
  • Limited-flow networks
  • p-Commodity
  • Reliability
  • Unreliable nodes
  • Upper boundary vectors

Fingerprint Dive into the research topics of 'Generate upper boundary vectors meeting the demand and budget for a p-commodity network with unreliable nodes'. Together they form a unique fingerprint.

Cite this