In this paper, analysis of k-out-of-n Multi-State Systems (MSSs) is considered. This type of systems consists of n components, and it can be in state j if and only if at least k components are in state j or greater. Investigation of such systems has been considered in several works. However, most of them have dealt only with an efficient computation of several global characteristics, such as system state probability or system availability. In this paper, we deal with importance analysis for such systems. Particularly, we focus on two commonly used importance measures - structural importance and Birnbaum's importance. Using logical differential calculus, we propose an efficient way of how to calculate these measures for a k-out-of-n MSS. The obtained results are then used to analyze an oil supply system.
Reliability has been considered as an important characteristic of many systems [
- 442
result in system failure. For this purpose, the approach based on the idea that the
system and all its components can be in one of more than two states is more suitable. In
this case, we say about Multi-State Systems (MSSs) [
One of the current issues of reliability engineering is evaluation of complex
systems. Such systems are composed of many components with very various natures [
Reliability analysis of MSSs is a complex problem that includes a lot of tasks. This paper focuses on two specific tasks: identification of situations in which component or its state is critical for system activity, i.e. situations in which a degradation of a component results in system degradation, and quantification of importance of individual system components, i.e. finding components with the greatest influence on system activity. One of the possible ways of how to perform this analysis is application of logical differential calculus.
Logical differential calculus has originally been developed for analysis of dynamic
properties of Multiple-Valued Logic (MVL) functions [
A k-out-of-n system is composed of n components. Based on [
Efficient ways of how to calculate some global characteristics, e.g. system state
probability or system availability, for this kind of systems have been considered, for
example, in [
A MSS is a mathematical representation of a system under consideration. It allows us
to define m levels at which the system or its components can operate. These levels are
known as states of the system/component and they take values from the set {0,1,…,
m -1}. State 0 means that the system/component is completely failed, while state m -1
implies that it is perfectly functioning. A mapping that defines the dependency of
system state on the states of its components is known as structure function. For a MSS
composed of n components, this function has the following form [
Based on the properties of the structure function, two classes of MSSs can be defined – coherent and incoherent. A MSS is coherent if its structure function is nondecreasing in all its arguments, i.e. there exist no circumstances under which degradation (improvement) of a system component can result in improvement (deterioration) of system state. In what follows, only coherent systems are considered.
The structure function defines system topology. However, if we want to investigate not only system topology but also some others characteristics, such as system state probability, system availability, or importance of individual system components, the state probabilities of the system components have to be known. For the i-th system component, they will be denoted as follows: (2) (3) (4) pi,s = Pr{xi = s}, s = 0,1,…, m -1 .
Pr{(x) = j}, for j {0,1,…, m -1} ,
Using these probabilities and the system structure function, we can compute two
basic characteristics of MSSs – system state probability [
A j Pr{ ( x) j}, U j Pr{ ( x) j}, for j {1,2,, m 1}.
This definition implies that system availability (unavailability) for system state j agrees with the probability that the system is in such state that its performance can (cannot) satisfy a demand corresponding to state j. For illustration, let us consider a power supply unit that can generate 30 MW, 10 MW, or 0 MW of electricity. Clearly, the system has 3 performance levels from which level 30 MW corresponds to state 2, level 10 MW to state 1 and level 0 MW to state 0. If there is a demand of at least 5 MW of electricity, then the unit is working if it is at least in state 1. This implies that it is available if it is at least in state 1 and, therefore, its availability (unavailability) should be computed with respect to state 1 for this situation. 2.1
Importance Analysis of Multi-State Systems
System state probability and availability are important characteristics of a system.
They give us a global view on the system. On the other hand, they carry no
information about the system structure, i.e. they do not allow investigating influence of
individual system components or their states on the system. For this purpose, other
indices are used. These indices are known as Importance Measures (IMs), and some of
the most commonly known are Structural Importance (SI) and Birnbaum’s
Importance (BI). The SI investigates only system topology while the BI takes into account
also state probabilities of the system components. These two indices play a key role in
importance analysis because a lot of other measures are defined based on them [
Importance analysis of MSSs based on SI and BI has been considered in several
papers, e.g., [
The approaches presented in the aforementioned works have been combined into
one complex framework in [
Logical differential calculus has been developed for analysis of dynamic properties of MVL functions. Logic derivative is a key term of this tool. There exist several types of logic derivatives but, for the purpose of this paper, Direct Partial Logic Derivatives (DPLDs) are the most important.
A DPLD reveals circumstances under which a considered change of a MVL
variable results in the studied change of the analyzed MVL function. Since the formal
definition of the structure function of a MSS agrees with the definition of a MVL
function, this derivative can also be used in the analysis of MSSs. In this case, it
allows us to detect situations in which a given change of a given component state
results in the studied change of the system state. More formally, a DPLD with respect to
variable xi is defined as follows [
10,, iofthe(rswi,ixse) j and (ri , x) h, for s,r, j, h 0,1,, m-1, s r, j h , (5) where (ai, x) = (x1, x2,…, xi -1, a, xi +1,…, xn) for a {s, r}.
Depending on the relations between s and r and j and h in (5), four kinds of DPLDs with different physical meaning can be used in reliability analysis of MSSs: ─ if s > r and j > h, then the DPLD identifies situations in which degradation of component i from state s to r results in degradation of system from state j to h, ─ if s < r and j < h, then the DPLD detects circumstances under which improvement of component i from state s to r causes improvement of system state from value j to h, ─ if s > r and j < h, then the DPLD finds circumstances under which degradation of component i from state s to r results in improvement of system state from value j to h, ─ if s < r and j > h, then the DPLD reveals situations in which degradation of the system from state j to h is caused by improvement of component i from state s to r.
Clearly, situations identified by the last two kinds of DPLDs cannot occur in case of a coherent system and, therefore, only the first two DPLDs are meaningful in the analysis of coherent MSSs. Furthermore, in what follows, we will primarily deal with investigation of consequences of component degradation on system activity. This implies that only DPLDs in which s > r and j > h will be taken into account.
Based on the meaning of DPLDs, it is clear that they allow us to find state vectors of the form of (si, x) at which deterioration of state s of component i to state r results in degradation of system state j to h. These state vectors are known as critical state vectors and, clearly, they describe circumstances under which a given component state is critical for a given degradation of system state j.
One of the assumptions that are often used in importance analysis of MSSs is that
the system components degrade gradually state by state. This assumption is not
unrealistic because even if a component deteriorates from state m -1 to state 0, we can
assume that it stays in every state from set {1,2,…, m -2} for very short time [
DPLDs give us a detailed view on the dependency between component degradation
and system degradation. However, they are not very appropriate for importance
analysis of a general MSS, i.e. a MSS in which a minor degradation (degradation by
one state) of any system component can result in degradation of the system by more
than one state. This inadequacy results from the fact that a lot of DPLDs have to be
computed in such situations, e.g., if we want to investigate consequences of a minor
degradation of state s of component i, then we have to compute DPLDs of the form of
( j h) xi (s s 1) for all h < j, i.e. j -1 DPLDs. The similar fact can also be
observed if we want to use DPLDs to investigate the coincidence between component
degradation and decrease in system availability level. To avoid this problem, new
types of logic derivatives have been introduced in [
An IDPLD of type I is defined as follows: xi(s( j)r) hj01 xi((sj hr)) 10,, iofthe(rswi,ixse) j and (ri , x) j, for s, r 0,1,, m-1, s r, j 1,2,, m-1, (6) and it allows us to find situations in which a given degradation of state s of system component i results in a deterioration of system state j. Quantification of these situations allows us to estimate influence of the considered component degradation on system state j.
An IDPLD of type III has the following form: (xhi(js hr) j ) hmu1j hdj10x(ih(us hrd) ) 10,, iofthe(rswi,isxe) j and (ri , x) j, (7) for s, r 0,1,, m-1, s r, j 1,2,, m-1, where notation h≥j (h<j) means that all system states that are greater than or equal to (less than) j are taken into account. Please note, this definition implies that IDPLDs of type III can be used to find state vectors at which a degradation of a given component state causes degradation of a given level of system availability and, therefore, they can be used to quantify consequences of a given deterioration of state s of component i on level j of system availability.
It has been mentioned in the previous paragraphs that quantification of situations in
which an IDPLD of type I or III takes nonzero value allows us to estimate influence
of degradation a given component state on system state/availability level. This
quantification can be done in two ways [
Another possibility is to calculate the probability that the considered IDPLD is
nonzero. This agrees with the probability that the studied degradation of a given
component state causes decrease in a given state/availability level of the system. If we
assume that only minor degradations of the system components can occur, then this
number agrees with BI of a given component state for a given system
state/availability level [
The previously mentioned versions of SI and BI deals with importance of a given
component state for a given state/availability level of the system. It has been shown in
[
The SI measures that can be used for these purposes are presented in Table 1. The similar table can be shown for the BI measures, but the only difference will be in replacement of the truth density notation with the probability that the IDPLD takes nonzero value. Please note that complex importance analysis of a MSS can be performed by computation of all types of SI or BI measures. Based on the formulae presented in Table 1, the SI (BI) measures investigating all possible dependencies between component degradation and system deterioration can be expressed in the form of Table 2 (IMs concerning with system state) or Table 3 (IMs focusing on system availability level).
The SI of a given SIi,s m1SIij,s wAhrieclhatisvtaetenusmobfercoomfpsiotnueantitonisriencomponent state j1 sults in system degradation. A relative number of situations in gTcivhoeemnSpsIoynoseftenamtgfoisvtraeatne SIij m1 1 ms11SIij,s scwyahusitsceehms .ddeeggrraaddaattiioonn ooff sctoamtepjonoefntthei The SI of a given A relative number of situations in cogmivpeonnseynsttefomr a SIi j m1 1 ms11SIi,sj cwahuiscehs ddeeggraraddaatitoionnofofcolmevpeolnejntofi availability level system availability.
The total SI of a SIi 1 m1SIi,s wAhrieclhatdiveegrnaudamtiboenr ooff csoitmuaptoionnesntini given component m 1 s1 results in system degradation. *note: TD(.) – truth density of the argument interpreted as a function with a Boolean-valued output 3
Let us consider a k-out-of-n MSS. According to Table 1 – Table 3, the most important thing in computation of the IMs considered above is efficient identification of nonzero elements of IDPLDs. For example, in case of computing SIij,s , this agrees with finding all state vectors (.i, x) = (x1, x2,…, xi -1, xi +1,…, xn) for which IDPLD ( j ) xi (s s 1) takes nonzero value. Now, let us find IDPLDs of which form can be nonzero. Firstly, let us assume that j > s. Such derivative cannot be nonzero because the k-out-of-n MSS can be in state j if and only if at least k components are in state j or greater. This implies that degradation of a component that is in a state less than j cannot result in degradation of system state j because system state is not determined by this component. Secondly, let us assume that j < s. This derivative cannot also take nonzero values because the system can be in state j if and only if not more than k -1 components are in a state greater than j. It follows that a minor degradation of a component that is in a state greater than system state j does not result in violation of this condition and, therefore, there exist no circumstances under which degradation of this component from state s to state s -1 can result in degradation of the system if the system is in state j such that j < s. Finally, let us consider an IDPLD of the form of ( j ) xi ( j j 1) . This derivative identifies situations in which a minor degradation of state j of component i results in degradation of system state j. Such situations can occur if and only if component i is in state j and exactly k -1 from the remaining components are in state j or greater than j. These situations correspond to state vectors of the form of ( ji , ru j,(1) , ru j,(2) ,, rukj1,(k1) , rv j,(1) , rv j,(2) ,, rvnjk,(nk ) ) 1 2 1 2 where u1, u2,…, uk -1 are components that are in states greater than or equal to j; v1, v2,…, vn-k are components that are in states less than j; ru j,(t) , for t = 1,2,…, k -1, det notes state of component ut (this state is greater than or equal to j); and rvt j,(t) , for t = 1,2,…, n - k, means that component vt is in a state less than j. It can be simply shown that n 1m jk1 j nk such state vectors exist. It follows that integrated deriva k 1
kn 11m jk1 j nk nonzero elements. Since every
tives ( j ) xi ( j j 1) has
IDPLD and DPLD has mn -1 elements [
( j ) n 1 m j k1 j nk TD xi ( j j 1) k 1 mn1
Based on the results obtained in the previous paragraph and information presented in Table 1, SIij,s can be computed for a k-out-of-n MSS using the following formula: SIij,s TD xi (s (j s)1) kn 11 m mj nk11 j nk 0, , if s j
. otherwise
Above, we have shown that only IDPLDs of the form of ( j ) xi ( j j 1) are nonzero in case of a k-out-of-n MSS. Since this IDPLD is nonzero if and only if states of the system components are characterized by state vectors of the form of ( ji , ru j,(1) , ru j,(2) ,, rukj1,(k1) , rv j,(1) , rv j,(2) ,, rvnjk,(nk ) ) , then degradation of component 1 2 1 2 i from state j to j -1 has to result in degradation of system state from j to j -1. This implies that the nonzero elements of this derivative agrees with the nonzero elements of DPLD ( j j 1) xi ( j j 1) . It follows that only such DPLDs are nonzero in case of a k-out-of-n MSS. Using this fact and definitions (6) and (7) of IDPLDs, the next formula can be proved simply for k-out-of-n MSSs:
( j ) xi (s s 1) (h j h j ) ( j j 1) xi (s s 1) xi (s s 1) ( j j 1) xi ( j j 1) 0, , if s j otherwise .
(10)
This formula implies that the k-out-of-n MSS represents a special type of MSSs in which a minor degradation of a system component can result only in a minor degradation of system state. Furthermore, it follows that the following relationships exist between SI measures presented in Table 1: (8) (9)
Finally, the total topological importance of component i for the activity of the kout-of-n MSS can be computed using the following formula:
All these formulae imply that there is no sense to distinguish between the SI measures investigating topological properties of the k-out-of-n MSS with respect to system state (Table 2) and with respect to system availability level (Table 3):
Now, let us consider the BI measures. These measures can also be computed using IDPLDs I or III. However, as has been shown in (10), these IDPLDs computed with respect to system state/availability level j agree with ( j j 1) xi (s s 1) in case of k-out-of-n MSSs and, therefore, the following relationships will hold between BI measures calculated with respect to system state and with respect to system availability level: (11) (12) otherwise (13) ( j j 1) Pr BIij,s BIi,sj xi ( j j 1)
1, if s j , BIij BIi j BIi,s BIis,s , BIi 1 m1
BIij,j . m 1 j1 0,
1 m 1
BIij,j ,
This implies that only problem in computation of the BI measures is calculation of
the probability that DPLD ( j j 1) xi ( j j 1) takes nonzero value.
According to the results presented in the previous paragraphs, this DPLD takes nonzero
values for all state vectors of the structure function that have the form of
( ji , ru j,(1) , ru j,(2) ,, rukj1,(k1) , rv j,(1) , rv j,(2) ,, rvnjk,(nk ) ) . Since a DPLD computed with
1 2 1 2
respect to variable xi does not depend on this variable [
For illustration of our approach, let us consider a modified oil supply system proposed
in [
Firstly, let us investigate topological properties of this system. This can be done simply using SI measures shown in Table 1 and formulae (11) and (12). For pipeline 1 and individual values of k, these results are presented in Table 5. According to the results presented in the form of formulae (11) and (12), the SI measures computed in these tables investigate topological properties of the system not only with respect to system state but also with respect to system availability level. As we can see (the lower right corner of sub-tables), degradation of component 1 has the greatest influence on system activity if k {2,3} and the least if k {1,4}. Next, in the bottom parts of the sub-tables, we can see that, in case of k {1,2}, the most important state te 1 a t s em 2 t s yS 3 te 1 a t s em 2 t s yS 3 0 0 0 0 of the component is state 3, while the least important is state 1. On the other hand, if k {3,4}, then the situation is completely different, i.e. the state with the greatest topological influence on system degradation is state 1, while state 3 has the least influence. Similarly, using the information presented in the right columns of the subtales, we can state if k {1,2}, then pipeline 1 has the greatest influence on system state/availability level 3 and the least on system state/availability level 1; while if k {3,4}, then pipeline 1 has the greatest influence on system state/availability level 1 and the least on system state/availability level 3. Clearly, the same results can be obtained for the remaining pipelines since formulae (11) and (12) imply that all components (or components states) have the same topological influence in case of k-outof-n systems and fixed values of k and n.
Now, let us calculate the BI measures for this system. These measures take into
account not only system topology but also state probabilities of the pipelines. In this
case, we use numbers presented in [
The BI measures for the oil supply system can be computed using formulae (13). According to these formulae, the most important part in computation of these measures is calculating the probability that DPLD ( j j 1) xi ( j j 1) , for j = 1,2,3 and i = 1,2,3,4, takes nonzero value. This can be done simply by identifying the state vectors of the form of (.i , ru1 j,(1) , ru2 j,(2) ,, rukj1,(k1) , rv1 j,(1) , rv2 j,(2) ,, rvnjk,(nk ) ) for specific values of j and k. For example, if we want to compute the probability that DPLD (1 0) x1 (1 0) is nonzero for k = 1, then its nonzero elements agree with the state vectors of the form of (., r 1, r 1, r 1 ) . Only one state vector has this form, i.e. state vector (.,0,0,0); therefore, the probability that the DPLD takes nonzero value is computed as follows:
(2 1) Pr x1 (2 1)
1 Pr{(.1 ,x) (.,0,0,0)} p2,0 p3,0 p4,0 where relation “≤” between state vectors (.i, x) = (x1, x2,…, xi -1, xi +1,…, xn) and (.i, y) = (y1, y2,…, yi -1, yi +1,…, yn) means that xk ≤ yk for k = 1,2,…, i -1, i +1,…, n. So, the DPLD is nonzero with the following probability:
(2 1) Pr x1 (2 1)
1 Pr{(.1 ,x) (.,1,1,1)} ( p2,0 p2,1 )( p3,0 p3,1 )( p4,0 p4,1 ) (15)
Finally, the probability of DPLD (3 2) x1 (3 2) being nonzero for k = 1 agrees with the probability that state vector (.1, x) has the form of (., r 3 , r 3 , r 3 ) . Using the notation “≤”, this can be calculated as follows:
(3 2) Pr x1 (3 2)
1 Pr{(.1 ,x) (.,2,2,2)} ( p2,0 p2,1 p2,2 )( p3,0 p3,1 p3,2 )( p4,0 p4,1 p4,2 ) values of BI1j,j and BI1, jj , it allows us to investigate importance of degradation of state j of pipeline 1 on state/availability level j of the oil supply system. Since all other BI measures investigating importance of a degradation of a component on system (14) (16) state/availability level are equal to 0 (formulae (13)), these values can be used to investigate importance of a given component state for the system, or total importance of pipeline 1 for a specific system state/availability level, or total importance of pipeline 1 for the entire system. All these numbers are presented in the upper left sub-table of Table 7. Clearly, the same results can be obtained if we investigate importance of component 2, since state probabilities for these components are same.
Using the similar procedure as has been presented above, the BI measures of all
system components can be obtained (upper left sub-tables of Table 7 and Table 8).
Furthermore, if we repeat this procedure for other values of k, i.e. for k = 2,3,4, we
can investigate importance of individual pipelines for all versions of the oil supply
system (the remaining parts of Table 7 and Table 8). (Please note that we obtain the
same results for components 1 and 2 and for components 3 and 4 since their state
probabilities have the same values.) According to the data presented in Table 7 and
Table 8, we can state that pipelines 1 and 2 have less influence on the activity of the
oil supply system than pipelines 3 and 4 if k = 1,2,3 but greater if k = 4. Another
interesting fact that can be noticed based on Table 7 and Table 8 is that all system
components have greater influence on greater states of the system in case of k {1,2,3},
(e.g., if k = 1, then degradation of component 1 results in degradation of system state
3 with the probability 0.0016 while in degradation of system state 1 with the
probability 0.00002. However, in case of k = 4, all pipelines are more important for lower
states of the system (e.g., a degradation of pipeline 1 causes degradation of system
state 1 with the probability 0.2980 and degradation of system state 3 with the
probability 0.1885). The similar facts can be observed for the BI measures investigating
the total importance of individual states of the pipelines for the oil supply system (the
bottom rows in sub-tables of Table 7 and Table 8). All these results imply that
importance of individual system components in case of k-out-of-n systems largely depends
on mutual values of k and n.
In this paper, importance analysis of a k-out-of-n MSS was considered. We
summarized some results from the qualitative and quantitative analysis of MSSs and
proposed the method for calculation of all range of the SI and BI measures. Furthermore,
we showed that a k-out-of-n MSS is a special type of MSSs in which a minor
degradation of any system component can result only in a minor degradation of system
state. Because of that, it is not important to distinguish between IMs focusing on
system state and IMs dealing with system availability level. Next, using logical
differential calculus, we found closed-form expressions for calculation of the SI measures for
a k-out-of-n MSS. All these results were used in the analysis of the oil supply system
considered in [
This work was supported by grants VEGA 1/0498/14 and VEGA 1/0038/16.