A two-commodity multistate flow network with capacity weight varying with edges, nodes and types of commodity

摘要

In a single-commodity flow network, the system capacity is the maximum flow from the source to the destination. The reliability and unreliability based on system capacity are two appropriate performance indices to measure the quality level of a flow network. This paper extends the performance evaluation problem to a two-commodity multistate flow network composed of multistate components (edges and nodes). 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. The maximal total flow is not suitable to be treated as the system capacity in two-commodity case. Hence, 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. Such a performance index that is used to measure the quality level of a supply–demand system can be easily computed in terms of upper boundary vectors. An efficient algorithm in terms of minimal cuts is thus presented to generate all upper boundary vectors.