Multi-state k-out-of-n systems and their Performance evaluation.

1. Introduction

The k-out-of-n system structure is a very popular type of redundancy in fault-tolerant systems, and finds wide application in both industrial and military systems. Examples of such fault-tolerant systems include the multi-engine system in an airplane, the multi-display system in a cockpit and the multi-transmitter system in a communication system (Kuo and Zuo, 2003). Efficient reliability evaluation algorithms for binary k-out-of-n systems with independent components have been provided by Barlow and Heidtmann (1984) and Rushdi (1986).

Many practical components and systems have more than two different performance levels. For example, a power generator in a power station can work at full capacity, which is its nominal capacity, say 10 MW, when there are no failures at all (Lisnianski and Levitin, 2003). Certain types of failures can cause the generator to be completely failed, while other failures will lead to the generator working at a reduced capacity say at 4 MW. On the system level, let us consider a power generating system consisting of several power generators. The abilities of the system to meet high power load demand, normal power load demand and lower power load demand can be regarded as different system states. Another example of multi-state components is an oil transmission pipeline. The pipeline is used to transmit oil from the source to spots A, B and C aligned in order along the pipeline. We say that the pipeline is in state 0 when it cannot transmit oil to any of the spots; it is in state 1 if the oil can reach spot A; it is in state 2 if the oil can reach up to spot B, i.e., spot A and B; it is in state 3 if the oil can reach up to spot C. A component with multiple failure modes can also be considered to be a multi-state component (Elsayed, 1996). A component like this has a working state and several failure states which might have different impacts on the system level. Since Barlow and Wu (1978) presented the first multi-state coherent system structure, many system structures, such as series-parallel structures, k-out-of-n structures and network structures, have been extended from the binary case to the multi-state case by allowing the components and the systems to take more than two possible states. With multi-state models, we can deal with reliability issues of engineering systems more accurately, and are thus able to answer more questions.

El-Neweihi et al. (1978) defined the first multi-state k-out-of-n system model, where the system state was defined as the state of the kth best component. In another words, at any state j, for the system to be in state j or above, there should be at least k components in state j or above. That is, the k value is the same with respect to all states. Boedigheimer and Kapur (1994) defined the multi-state k-out-of-n model from the perspective of lower and upper boundary points, and their definition is actually consistent with that by El-Neweihi et al. (1978). Their study on multi-state k-out-of-n systems is purely theoretical, and no practical applications have been identified to fit into this model.

Huang et al. (2000) proposed the generalized multi-state k-out-of-n:G system model, where there can be different k values with respect to different states.

Definition 1. (Huang et al. (2000)). An n-component system is called a generalized k-out-of-n:G system [empty set] (x) [greater than or equal to] j (1 [less than or equal to] j [less than or equal to] M) whenever there exists an integer value l (j [less than or equal to] l [less than or equal to] M) such that at least [k.sub.l] components are in state l or above.

This model allows the description of practical multi-state k-out-of-n:G systems with more flexibility. Tian. et al. (2005) and Zuo and Tian (2006) developed an efficient recursive algorithm for reliability evaluation of generalized multi-state k-out-of-n systems with identically and independently distributed (i.i.d.) components. It is a natural extension of the binary k-out-of-n system model that we allow different k values with respect to different states. However, the Huang-Zuo-Wu model of multi-state k-out-of-n systems (Huang et al., 2000) suffers from the fact that few practical applications can fit into this model. Zuo and Tian (2006) presented a power station with three generators as an example of a decreasing multi-state k-out-of-n:G system model. The limitations are that there can only be three possible states and thus two k values, [k.sub.1] and [k.sub.2] can only be equal to one. There might be other applications of the Huang-Zuo-Wu model yet to be identified.

In this paper, we propose a new multi-state k-out-of-n system model which allows different k values with respect to different states as well, and, very importantly, more practical engineering systems can fit into this model. Two categories of applications have been identified for this model. In the first category, multiple states are interpreted as multiple levels of capacity, as in the oil transmission pipeline case mentioned earlier. The system has different requirements on the number of components on different levels. In the second category, multiple states are interpreted in terms of multiple failure modes. The working state of a component has positive cumulative contributions to the system, some failure states of a component have no contributions whatsoever to the system, while other failure states of a component have some kind of negative cumulative contribution to the system. The new multi-state k-out-of-n system model and the detailed descriptions of these two categories of applications will be presented in Section 2.

It is critical to find efficient reliability evaluation algorithms for multi-state k-out-of-n systems. In Section 3, we propose an approach for reliability evaluation of multi-state k-out-of-n systems with i.i.d. components. This approach is very similar to that by Zuo and Tian (2006), except that it uses minimal path vectors while the algorithm by Zuo and Tian (2006) uses minimal cut vectors, based on the differences of the multi-state k-out-of-n models with which they deal. In Section 4, we propose a recursive algorithm for reliability evaluation of multi-state k-out-of-n systems with independent components. This algorithm, however, can be considered to be an extension of the binary k-out-of-n system reliability evaluation algorithms of Barlow and Heidtmann (1984) and Rushdi (1986). Efficiencies of the proposed algorithms will be investigated as well in the following sections of this paper.

Assumptions

1. The state space of each component and the system is {0, 1, 2,..., M}.

2. The state of the system is completely determined by the states of the components.

Notation

N = the number of components of a system;

M = the maximum state level of a multi-state system and its components;

[x.sub.i] = state of component i, [x.sub.i] = j if component i is in state j, 0 [less than or equal] j [less than or equal] M, 1 [less than or equal] i [less than or equal] n;

X = an n-dimensional vector representing the states of all components, x = ([x.sub.1], [x.sub.2],..., [x.sub.n]);

[empty set] (x) = the state of the system, 0 [less than or equal] [phi](x) [less than or equal] M;

[k.sub.j] = the k value with respect to level j of a generalized multi-state k-out-of-n system;

[v.sub.j] = a minimal cut vector to level j of an increasing multi-state k-out-of-n:F system;

[P.sub.s,j] = Pr([phi](x) [greater than or equal] j);

[Q.sub.s,j] = Pr([phi](x) < j), i.e., l - [P.sub.s,j];

[r.sub.s,j] = Pr([empty set] (x) = j);

P(*) = the recursive function, P = P(n, k, P);

k = the k vector of a multi-state k-out-of-n system, k = ([k.sub.1], [k.sub.2],..., [k.sub.M]);

P = the component state distribution matrix for a nominal multi-state k-out-of-n system;

[p.sub.nj] = the probability of component n in state j;

[k.sup.j] = the generated k vector when component n is in state

[P.sup.j] = the generated P matrix when component n is in state j.

2. The multi-state k-out-of-n system model and its applications

2.1. Definition of the multi-state k-out-of-n system model

We define a new multi-state k-out-of-n:G system model as follows:

Definition 2. An n-component system is called a k-out-of-n:G system if [phi](x) [greater than or equal to] j (1 less than or equal to] j [less than or equal to] M) whenever at least [k.sub.l] components are in state l or above for all l such that 1 [less then or equal to] l [less than or equal to] j.

Intuitively, to be in state j or above, the system has to meet all the requirements on the number of components at states form one to j. In the Huang-Zuo-Wu model of multi-state k-out-of-n:G system in Definition 1, however, the system is in state j or above if any of the requirements on the number of components at states from j to M can be met. The multi-state k-out-of-n:G system model reported by Huang et al. (2000) (given in Definition 1) and the one proposed in this paper (given in Definition 2) are both multi-state monotone systems as defined in Natvig (1985): (i) the system state is non-decreasing with the increase of each component state; (ii) the system is in state 0 if all of its components are in state 0, and the system is in state M (the highest possible state) if all of its components are in state M.

A special case of the proposed multi-state k-out-of-n:G system model given in Definition 2 is defined as follows.

Definition 3. A multi-state k-out-of-n:G system is called a decreasing k-out-of-n:G system if [k.sub.1] > [k.sub.2] > ... > [k.sub.M].

As will be shown later in this paper, the reliability evaluation of the general case of the multi-state k-out-of-n:G system given in Definition 2 can be handled through a decreasing multi-state k-out-of-n:G system given in Definition 3.

Print Get the Mag Weekly Updates