TY - JOUR

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

AU - Lin, Yi-Kuei

PY - 2007/11/16

Y1 - 2007/11/16

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

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

KW - Budget

KW - Limited-flow networks

KW - p-Commodity

KW - Reliability

KW - Unreliable nodes

KW - Upper boundary vectors

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

U2 - 10.1016/j.ejor.2006.09.082

DO - 10.1016/j.ejor.2006.09.082

M3 - Article

AN - SCOPUS:34249282010

VL - 183

SP - 253

EP - 262

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 1

ER -