|
Description
Notation
n = the number of components in the network;
[M.sub.i] = an integer value representing the maximum state or maximum capacity of component i, [M.sub.i] [greater than or equal to] 1, i = 1, 2,..., N;
s = the source node;
t = the sink node;
d = the demand of flow from the source node to the sink node;
[x.sub.i] = a discrete random variable representing the state or the capacity of component i, [x.sub.i] may take values 0, 1, 2,..., [M.sub.i], i = 1, 2,..., N;
x = ([x.sub.1], [x.sub.2],..., [x.sub.N]) (we call x the component state vector and it represents the states of all failure-prone components (i.e., all components);
[phi](x) = state of the system;
[p.sub.ij] = Pr([x.sub.i] = j), i = 1, 2,..., N, j = 0, 1, 2,..., [M.sub.i], [[summation].sub.j=0.sup.[M.sub.i]][p.sub.ij] = 1;
[P.sub.ij] = Pr([x.sub.i] [greater than or equal to] j), i = 1, 2,..., N, j = 0, 1, 2,..., [M.sub.i];
[z.sup.i] = the ith minimal path vector of the considered multistate network;
[y.sup.i] = a general vector with n elements and with index i;
[Y.sup.j,i] = a vector generated by the "[direct sum]" operator, [Y.sup.j,i] = [y.sup.j] [direct sum] [y.sup.i];
PrU(dot) = the recursive function of the RSDP algorithm;
[TM.sub.i] = the ith term in the SDP calculation;
[T.sub.1] = The CPU time used by Aven's algorithm;
[T.sub.2] = The CPU time used by RSDP;
[lambda] = the ratio [T.sub.1]/[T.sub.2].
1. Introduction
Many network systems, such as power generation and transmission systems, oil and gas supply systems, and communication systems, consist of components which can work at different levels of capacity. These systems are regarded as multistate networks (Lin et al., 1995; Kuo and Zuo, 2003; Lisnianski and Levitin, 2003). Reliability is an important index for evaluating the performance of these systems and for making decisions such as maintenance scheduling. We consider a network which satisfies the following assumptions: (i) all nodes are perfect; and (ii) all links are directed and failure prone. The capacity of a link is an independent discrete random variable which may take non-negative integer values following a certain probability distribution. The term "components", which is usually used in multistate system analysis (Kuo and Zuo, 2003; Lisnianski and Levitin, 2003), will be used to refer to these failure-prone "links".
We limit our discussions to two-terminal reliability analysis. This is a classical network reliability problem with a broad range of practical applications (Kuo et al., 1999; Ramirez-Marquez and Coit, 2005). We are interested in the flow from a single source node, s, to a single sink node, t. Under these assumptions, we can call the flow from node s to node t the capacity or the state of the system, represented by [phi](x) where x is the component state vector. For such a network, we are interested in evaluating the probability that the system state is equal to or greater than d units, i.e., [phi](x) [greater than or equal to] d, which can also be considered to be the reliability of the network once d is specified.
A general method for this multistate network reliability evaluation is using minimal path (cut) vectors. A component state vector, x, is called a minimal path vector to system state d if [phi](x) [greater than or equal to] d, and [phi](y) < d for any y < x. Such a minimal path vector is also called a d-MP for short. For the purpose of evaluating the probability of event [phi](x) [greater than or equal to] d, Xue (1985) reports an algorithm for generating all d-MPs. Lin et al. (1995) propose another algorithm for the same purpose, claiming it to be more efficient. Using either algorithm, one can find all d-MPs. Let us suppose that there are L such d-MPs and, for simplicity, denote them as [z.sup.1], [z.sup.2],..., [z.sup.L]. Then, the probability that [phi](x) [greater than or equal to] d can be calculated is as follows:
Pr([phi](x) [greater than or equal to] d) = Pr({x [greater than or equal to] [z.sup.1]} [union] {x [greater than or equal to] [z.sup.2]} [union] ... [union] {x [greater than or equal to] [z.sup.L]}). (1)
Given that all d-MPs have been found, the issue becomes how to evaluate the probability of the union of the events for which the component state vector is greater than or... |
Looking for additional articles?
Click here
to search our database of over 3 million articles.
|
