TY - JOUR

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

AU - Lin, Yi-Kuei

PY - 2007/10/1

Y1 - 2007/10/1

N2 - 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.

AB - 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.

KW - Cost attribute

KW - Minimal cut

KW - Multistate flow network

KW - Reliability

KW - Two-commodity

KW - Unreliable nodes

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

U2 - 10.1016/j.cor.2005.11.013

DO - 10.1016/j.cor.2005.11.013

M3 - Article

AN - SCOPUS:33847735894

VL - 34

SP - 3043

EP - 3054

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

IS - 10

ER -