Varied capacity weights in a two-commodity multistate flow network

摘要

With varied capacity weights, this paper extends the performance evaluation problem to a two-commodity multistate flow network composed of multistate edges and nodes. Both types of commodity consume the capacities of edges and nodes differently. The maximal total flow is not suitable to be treated as the system capacity in two-commodity case. Hence, the system capacity is defined as a 2-tuple vector and then a performance index, the probability that the upper bound of the system capacity is a given pattern, is proposed. Such a performance index 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.