=Paper=
{{Paper
|id=Vol-1844/10000713
|storemode=property
|title=Minimal Cut and Minimal Path Vectors in Reliability Analysis of
Binary- and Multi-State Systems
|pdfUrl=https://ceur-ws.org/Vol-1844/10000713.pdf
|volume=Vol-1844
|authors=Miroslav Kvassay,Elena Zaitseva,Vitaly Levashenko
|dblpUrl=https://dblp.org/rec/conf/icteri/KvassayZL17
}}
==Minimal Cut and Minimal Path Vectors in Reliability Analysis of
Binary- and Multi-State Systems==
<pdf width="1500px">https://ceur-ws.org/Vol-1844/10000713.pdf</pdf>
<pre>
       Minimal Cut and Minimal Path Vectors in Reliability
          Analysis of Binary- and Multi-State Systems

                 Miroslav Kvassay1, Elena Zaitseva1 and Vitaly Levashenko1
   1
       Faculty of Management Science and Informatics, University of Zilina, Univerzitna 8215/1,
                                    01026 Zilina, Slovakia
                        (Miroslav.Kvassay, Elena.Zaitseva,
                         Vitaly.Levashenko)@fri.uniza.sk



         Abstract. Minimal Cut Vectors (MCVs) and Minimal Path Vectors (MPVs) are
         one of the principal tools of reliability engineering. MCVs represent situations
         in which repair/improvement of any system component results in functioning/
         improvement of the system. MPVs coincide with circumstances under which
         failure/degradation of any system component causes system failure/degradation.
         MCVs and MPVs allow us to compute a specific measure known as Fussell-
         Vesely’s Importance (FVI), which is used to evaluate importance of system
         components for system operation. The FVI has originally been developed for
         analysis of binary-state systems. In this paper, we propose several
         generalizations of this measure for multi-state systems. Furthermore, we
         summarize results from several papers focusing on identification of the MCVs
         and MPVs in multi-state systems and combine them with the proposed
         measures to develop a complex procedure for importance analysis of multi-state
         systems. The tool used for identification of the MCVs and MPVs is logical
         differential calculus.

         Keywords: Multi-State System, Structure Function, Minimal Cut Vector,
         Minimal Path Vector, Logical Differential Calculus

         Key Terms. Reliability, Model, Approach, Methodology, Scientific Field




1 Introduction

One of the basic tasks of reliability analysis is investigation of importance of
individual system components for system activity. Generally, two approaches can be
used for solving this task. The first one is based on identification of critical state
vectors that describe circumstances under which a change of a component activity
results in a change of system performance. Another possibility is to detect minimal
scenarios that ensure that the system can accomplish its mission or minimal scenarios
whose occurrence causes that the system cannot satisfy the requested objectives.
These scenarios are known as Minimal Path Sets (MPSs) and Minimal Cut Sets
(MCSs) respectively [1], [2], [3], [4].
   MCSs and MPSs or their equivalents known as Minimal Cut Vectors (MCVs) and
Minimal Path Vectors (MPVs), respectively, have been introduced in reliability
analysis of Binary-State Systems (BSSs). In [5], the terminology of MCSs and MPSs
has been generalized for Multi-State Systems (MSSs). One of the principal tasks in
the analysis based on MCSs or MPSs is their identification. In case of BSSs, a lot of
algorithms have been developed for this task, e.g. [6], [7], [8]. Using MCSs and
MPSs, several approaches have been proposed to perform the quantitative analysis of
BSSs. These approaches allow estimating system availability or computing
importance of individual system components [9], [10], [11], [12]. In case of MSSs,
MCVs and MPVs are more frequently used than MCSs and MPSs respectively. They
have primarily been used in the qualitative and quantitative analysis of network
structures, e.g. distribution networks and, therefore, most of the algorithms developed
for their identification in MSSs, e.g. [13], [14], [15], have been based on the
assumption that the structure of a MSS can be expressed in the form of a network.
However, not every MSS can be expressed as a graph structure. Because of that, more
general algorithm has been proposed in [16], [17]. This algorithm permits detection of
MCVs or MPVs in a MSS of any type. This allows us to apply the concept of MCVs
and MPVs not only in the analysis of network systems but also in the investigation of
other types of MSSs. This idea has been considered in [18] where one of the typical
measures investigating importance of system components in BSSs known as Fussell-
Vesely’s Importance (FVI) [9], [10] has been generalized for investigation of
importance of individual states of components in a MSS. The generalization has been
done based on the concept of MCVs and using logical differential calculus.
   In this paper, we summarize results presented in [16], [17], [18] and propose an
approach for investigation of MSSs using MCVs and MPVs. We define some more
general types of FVI that allow us to investigate importance of the entire component
(not only of a specific component state). The achieved results are illustrated based on
the analysis of the service system considered in [18], but this approach could also be
applied in reliability analysis of information systems, especially in the analysis of
distributed systems, such as distributed temporal database systems studied in [19].


2 Reliability Analysis

The principal step in investigation of system reliability is creation of its model. As a
rule, two types of mathematical models are used in reliability analysis: BSSs and
MSSs. A BSS allows defining only two states in system/components performance –
functioning (presented as number 1) and failure (represented by number 0). These
models are useful in the investigation of consequences of system failure, but they do
not allow us to study processes that gradually results in system failure. For this
purpose, MSSs are more suitable because they permit defining more than two states to
describe system/components performance – from perfectly functioning to complete
failure. The dependency of system state on states of its components is defined by a
map known as structure function. For MSSs, this function has the next form [2]:
 (x): {0,1,…, m1 -1}×{0,1,…, m2 -1}×…×{0,1,…, mn -1}{0,1,…, m -1} ,                (1)
where n denotes number of system components, m agrees with the number of system
states (state 0 means that the system is completely failed, while state m -1 agrees with
perfect functioning), mi denotes number of states of component i (state 0 corresponds
to complete failure and state mi -1 to perfect functioning), for i = 1,2,…, n, xi is a
variable defining state of component i, and x = (x1, x2,…, xn) is a vector defining states
of the system components (state vector). Specially, if m1 = m2 =…= m, then the
system is identified as homogeneous [2], [3]. Special type of homogeneous systems is
a BSS for which m1 = m2 =…= m = 2 [1].
   Based on the properties of the structure function, two basic classes of systems can
be recognized – coherent and noncoherent. A system is coherent if its structure
function is non-decreasing in all its variables, i.e. there exist no circumstances under
which a degradation of a system component can result in system improvement. If this
assumption is not satisfied, then the system is noncoherent. In what follows, only
coherent systems will be considered.
   The structure function describes layout of the system components and, therefore, it
allows us to investigate topological properties of the system. However, this function
carries no information about state probabilities of individual system components and,
therefore, only its knowledge is not sufficient for the analysis of system reliability.
So, the state probabilities of the system components represent other information that
has to be included in the model [2], [3]:
                        pi,s = Pr{xi = s}, s = 0,1,…, mi -1 .                         (2)
For BSSs, pi,0 is denoted as qi, and it is known as component unavailability because it
coincides with time during which the component is unavailable (failed). Similarly, pi,1
is denoted only as pi, and it is known as component availability because it agrees with
proportion of time during which the component is available (working).
   If a system model is known, the analysis can be performed. Some of the basic
characteristics evaluating reliability of a system under consideration are system states
probabilities, system availability and unavailability. For BSSs, system availability
agrees with the probability that the system is in state 1, while the unavailability
corresponds to the probability that it is in state 0. This is not true for MSSs where
system availability (unavailability) is defined as the probability that the system can
(cannot) satisfy a specific requirement. If we know a minimal system state, e.g. state j,
that allows satisfying the requirement, then system availability (unavailability) is
defined as the probability that the system is at least in (below) state j [2]:
       A j  Pr{ ( x)  j}, U  j  Pr{ ( x)  j}, for j {1,2, , m  1} .        (3)



2.1 Minimal Path Sets and Minimal Path Vectors

MPSs have been introduced in reliability analysis of BSSs. They represent minimal
sets of components whose simultaneous functioning ensures system functioning [1],
[12]. In terms of state vectors they can be expressed as so-called MPVs that agree
with situations in which a failure of any working component causes system failure.
More formally, a state vector x is a MPV if (x) = 1 and (y) = 0 for any y < x. Please
note that relation y < x between state vectors x = (x1, x2,…, xn) and y = (y1, y2,…, yn)
means that yi ≤ xi for all i{1,2,…, n} and there exists at least one i such that yi < xi.
Specially, if only the first part of the definition is satisfied for a state vector x, i.e.
(x) = 1, then the state vector is known as a path vector.
   The concept of MPSs and MPVs has been generalized for homogeneous MSSs in
[5]. Using that paper, we can generalize this concept on nonhomogeneous systems in
the following way.
   Let us consider a nonhomogeneous MSS of n components and denote
 M  max i{1, 2,,n} mi . Next, let us denote a set of all system components that are in
state s as Ns for s = 0,1,…, M -1 (please note that if no system component is in state s,
then the set Ns is empty). Using this, we can define a partition η = (N0, N1,…, NM) of
n system components into M sets such that i  Ns  s < mi (this implies that
component i can occur in set Ns if and only if its maximal possible state is not less
than s). Clearly, there exist  mi different partitions, and every partition
                                      n
                                       i 1
corresponds to a state vector of the system structure function. Moreover, there is one-
to-one correspondence between state vectors of the structure function and partitions of
the system. This correspondence is based on the rule that the i-th system component is
present in set Ns of partition η if and only if a state vector corresponding to the
partition η has the form of (si, x) = (x1, x2,…, xi -1, s, xi +1,…, xn). The state vector that
agrees with partition η will be denoted as x(η). Using these conventions, a MPS for
level j of system availability is defined as a partition η for which ϕ(x(η)) ≥ j and
ϕ(y) < j for any y < x(η). Please note that this definition implies that MPSs can be
recognized with respect to m -1 different states of the system, i.e. for j = 1,2,…, m -1.
   The previous definition of a MPS for level j of system availability uses vectors
corresponding to MPSs. As in the case of BSSs, these state vectors are known as
MPVs [2], [5]. More formally, a state vector x is a MPV for level j of system
availability if ϕ(x) ≥ j and ϕ(y) < j for any y < x. Specially, if only the first part of the
definition is satisfied by a vector x, then it is known as a path vector for level j of
system availability. Clearly, MPVs for system availability level j correspond to
situations in which a degradation of any system component that can degrade, i.e. that
is not completely failed, results in decrease in system state below value j. Please note
that the definitions of MPSs and MPVs are very similar but the latter is not based on
term “partition” and, therefore, it is probably clearer.


2.2 Minimal Cut Sets and Minimal Cut Vectors

Another concept that is closely related to MPSs and MPVs is a concept of MCSs and
MCVs. These terms have also been introduced firstly in the analysis of BSSs. For a
BSS, a MCS represents a minimal set of components whose simultaneous failure
results in system failure. A state vector that corresponds to a MCS is known as a
MCV. Unlike a MCS, a MCV describes a situation in which a repair of any failed
component causes system functioning. Mathematically, a state vector x is a MCV if
(x) = 0 and (y) = 1 for any y > x. Please note that relation y > x between two state
vectors x = (x1, x2,…, xn) and y = (y1, y2,…, yn) has a similar meaning as in the case of
MPVs, i.e. it means that yi ≥ xi for all i{1,2,…, n} and there exists at least one i such
that yi > xi. Specially, if only the first part of the definition is satisfied for a state
vector x, i.e. (x) = 0, then the state vector can be recognized as a cut vector.
    In case of MSSs, we can generalize definition of a MCS introduced in [5] for
nonhomogeneous systems in the similar way as in the case of MPSs. However, this
has no practical sense for the purpose of this paper and, therefore, we only introduce
definition of a MCVs presented in [2]. So, a state vector x is a MCV for level j of
system availability if ϕ(x) < j and ϕ(y) ≥ j for any y > x. Furthermore, every state
vector x satisfying ϕ(x) < j is known as a cut vector for level j of system availability.
This definition implies that a MCV for level j of system availability represents a
situation in which an improvement of any system component that can be improved,
i.e. that is not perfectly working, causes that the system reaches at least state j.


3 Reliability Analysis based on Minimal Path and Cut Vectors

MPVs (MCVs) are very useful in both – qualitative and quantitative analysis. In the
qualitative analysis of BSSs they describe circumstances under which a failure of any
working (repair of any failed) component results in system failure (functioning). For
MSSs, they correspond to situations in which a minor degradation (improvement) of
any functioning (non-perfectly working) component causes that the system will not be
able (will be able) to accomplish its mission. In the quantitative analysis, they can be
used to estimate some global characteristics, e.g. system availability, system state
probabilities [1], [2], [3], or to quantify importance of individual system components
(or their states in case of MSSs) [9], [10], [11], [12], [18].
   Firstly, let us focus on the global reliability characteristics. For MSSs, system
availability and unavailability can be calculated based on MPVs and MCVs in the
following way [20]:
                                         N p           
                                          j


                          A   j
                                                       
                                    Pr   x  M PVl j  ,
                                          l 1          
                                                                                      (4)
                                         N c           
                                          j


                         U    j
                                                        
                                    Pr   x  M CVl j  ,
                                          l 1          

where Np≥j (Nc≥j) agrees with the number of MPVs (MCVs) for system state j, MPVl j
MCV  denotes the l-th MPV (MCV) for level j of system availability, and event
      l
       j


x  MPV  x  MCV  means that an arbitrary state vector x is greater (less)
            l
             j
                           l
                            j


than or equal to the l-th MPV (MCV) for level j of system availability. Please note
that relation “≥” (“≤”) between two state vectors has similar meaning as relation “>”
(“<”) used in definitions of MPVs and MCVs, and the only difference is that it admits
equality of state vectors.
   Using system availabilities or unavailabilities, the system state probability can be
computed as follows:
                        1  A 1              U 1                   if j  0 ,
                        
      Pr{ ( x )  j}   A  j  A  j 1     U  j 1  U  j       if j  1,2, , m  2,                     (5)
                         A  m 1             1  U  m1            if j  m  1 .
                        
   Another possibility how MPVs and MCVs can be used is investigation of influence
of individual components (or their states in case of MSSs) on system activity. For this
task, a lot of measures have been proposed. One of them is FVI.
   The FVI has been introduced in reliability analysis of BSSs as the probability that a
failure of a given component contributes to system unavailability [9], [10], [12]. This
agrees with the probability that at least one MCS containing the considered
component is failed given that the system is failed. (Please note a MCS is failed if all
components forming the MCS are failed.) Another option is to define the FVI in such
a way that it allows us to identify contribution of functioning of component i to
system availability. This idea has been presented in [11] where this measure has been
defined as the probability that at least one MPS containing component i is working
given that the system is functioning. (A MPS is working if all components forming it
are functioning.) In [20], these measures have been defined using MCVs and MPVs
instead of MCSs or MPSs respectively.
   Definitions in [20] can be generalized for MSSs in several ways, which allow us to
define several types of FVI measures. Firstly, let us focus on FVI measures based on
MCVs. In this case, we can define FVI ic,,sj for state s of component i with respect to
level j of system availability as the probability that a degradation of a given
component state contributes to system unavailability U ≥ j [18]:

         FVI ic,,sj 
                            
                          Pr MCV j ( s  1) i   MCVs j ; x  MCV j ( s  1) i         ,                  (6)
                                                          j
                                                      U
where MCVs ≥ j is a set of all MCVs for level j of system availability, MCV ≥ j((s -1)i)
denotes a MCV for level j of system availability in which xi = s -1, and event
                                                                  
 MCV j (s  1) i   MCVs j ; x  MCV j (s  1) i  means that there is at least one
MCV with xi = s -1 that is greater than or equal to an arbitrary state vector x. The
previously introduced meaning of this definition results from the fact that if state
vector ((s -1)i, x) = (x1, x2,…, xi -1, s -1, xi +1,…, xn) is a MCV for level 𝑗 of system
availability, then it follows that degradation of component i from state s to lower one
contributes to level j of system unavailability.
   Formula (6) admits that component i can degrade more than one state. However,
some approaches used in importance analysis of MSSs are based on the assumption
that a component can degrade only one state. For this purpose, we can modify
formula (6) in the following way:

                                                                                          p
FVI ic,,s j  Pr MCV j ( s  1) i   MCVs j ; (( s  1) i , x )  MCV j ( s  1) i 
                                                                                                    i , s 1
                                                                                                               ,   (7)
                                                                                                U j

                   
where event MCV j (s  1) i   MCVs j ; ((s  1) i , x)  MCV j (s  1) i  means that       
there exists at least one MCV with xi = s -1 that is greater than or equal to an arbitrary
state vector ((s -1)i, x).
   The previous formula focuses on contribution of a specific component state to
system unavailability. If we sum FVI ic,,s j measures through all possible values of s,
i.e. for s = 1,2,…, mi -1, then we can quantify the total contribution of component i to
system unavailability U ≥ j:
                                                  mi 1
                                     FVI ic , j   FVI ic,,s j .                                              (8)
                                                   s 1

 In the similar way, we can generalize FVI based on MPVs introduced in [20] for
MSSs. In this case, we obtain the next formulae:

                                                                                           p
FVI ip, s, j  Pr MPV j ( s  1) i   MPVs j ; (( s  1) i , x )  MPV j ( s  1) i 
                                                                                                 i , s 1
                                                                                                            ,    (9)
                                                                                                A j

                                                  mi  2
                                    FVI ip , j   FVI ip, s, j .                                             (10)
                                                   s 0

Formula (9) quantifies contribution of a minor improvement of state s of component i
to system availability A ≥ j, while FVI ip,s, j measure can be used to estimate the total
contribution of component i to system availability A ≥ j.


3.1 Direct Partial Logic Derivatives

Logical differential calculus is a special tool developed for analysis of dynamic
properties of logic functions. The central term of this tool is a logic derivative.
Several types of logic derivatives exist, and one of them is Direct Partial Logic
Derivative (DPLD) [21]. This derivative has originally been defined for MVL
functions. Since the structure function of a homogeneous MSS can be viewed as a
MVL function [21], DPLD can also be applied in reliability analysis of such systems.
Furthermore, it has been shown in [22] that this derivative can also be used in the
analysis of nonhomogeneous systems. For this purpose, definition of a DPLD of
function ϕ(x) with respect to variable xi has been generalized in the following way:
                    ( j  h) 1, if  ( si , x )  j and  (ri , x )  h
                                                                        ,
                   xi ( s  r ) 0, otherwise                                                                  (11)
              for s,r  0,1, , mi -1, s  r ,           j, h  0,1, , m-1, j  h ,

where ϕ(ai, x) = ϕ(x1, x2,…, xi -1, a, xi +1,…, xn) for a  {s, r}. This implies that the
DPLD can be used to find circumstances under which a degradation/improvement of
the i-th system component results in degradation/improvement of the whole system.
Since only coherent systems are considered in this paper, only DPLDs in which j > h
and s > r or in which j < h and s < r can be nonzero. The former identify state vectors
(.i, x) = (x1, x2,…, xi -1, xi +1,…, xn) at which degradation of component i from state s to
r results in degradation of system from state j to h, while the nonzero values of the
latter agree with state vectors (.i, x) at which improvement of system state from value
j to h results from improvement of state s of component i to value r.
3.2 Integrated Direct Partial Logic Derivatives

   DPLDs are useful to identify situations in which a specific change of a state of a
given component results in the specified change of system state. However, a problem
is that a lot of DPLDs can be defined with respect to one component, i.e. if the
component has mi and the system has m different states, then mi(mi -1)m(m -1) DPLDs
can be defined with respect to this component. Assuming that the system is coherent
and using the fact that  ( j  h) xi (s  r )   (h  j ) xi (r  s) [21], only
mi(mi -1)m(m -1)/4 DPLDs are needed to be computed. This can be still quite a lot.
Another fact is that these DPLDs have a lot of zero values and, therefore, they usually
carry little information. Furthermore, if we consider derivative  ( j  h) xi (s  r )
that is nonzero for a state vector (si, x), then all other DPLDs  ( j   h) xi (s  r ) ,
where j′ ≠ j or h′ ≠ h, have to take value 0 for the considered state vector. Due to these
facts, new types of logic derivatives have been introduced in [16], [22]. These
derivatives were named as Integrated Direct Partial Logic Derivatives (IDPLDs),
because they combine several DPLDs together. Three types of IDPLDs can be
defined. For the purpose of this paper, the most important ones are IDPLDs of type III
that can be used to find state vectors at which degradation (improvement) of a given
component state causes degradation (improvement) of a given level of system
availability. In notation of system degradation, this derivative is defined as follows:
   (h j  h j )   m1 j 1
                                   (hu  hd ) 1 if  ( si , x )  j and  (ri , x )  j
                                                                                      ,
    xi ( s  r )     hu  j hd 0 xi ( s  r )  0 otherwise                                 (12)
           for s, r  0,1,, mi -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. If we want to focus on system improvement, then
this IDPLD has the following form:
   (h j  h j )    j 1 m1
                                   (hd  hu ) 1 if  ( si , x )  j and  (ri , x )  j
                                                                                      ,
    xi ( s  r )     hd 0 hu  j xi ( s  r )  0 otherwise                                 (13)
           for s, r  0,1,, mi -1, s  r , j  1,2,, m-1.
   It can be shown simply that the following relation holds between the IDPLDs
introduced above:
                           (h j  h j )        (h j  h j )
                                                                     ,                        (14)
                             xi ( s  r )          xi (r  s)
but the principal difference between these two integrated derivatives is that IDPLD
 (h j  h j ) xi (s  r ) can be computed only at state vectors of the form of
(si, x), while IDPLD  (h j  h j ) xi (r  s) can be calculated only at state
vectors of the form of (ri, x) (Fig. 1).
              (x)  (h1  h1 ) x1 (1  0)         (x)  (h1  h1 ) x1 (0  1)
            (0,0) = 0         <1
                                                     (0,0) = 0     <1                  0
            (0,1) = 0         <1                    (0,1) = 0     <1                  1
            (0,2) = 0         <1                    (0,2) = 0     <1
                                                                                        1
            (0,3) = 0         <1                    (0,3) = 0     <1         
                                                                                        1
            (1,0) = 0         ≥1            0      (1,0) = 0     ≥1

            (1,1) = 1         ≥1
                                             1      (1,1) = 1     ≥1

            (1,2) = 2         ≥1
                                             1      (1,2) = 2     ≥1

            (1,3) = 3         ≥1
                                             1      (1,3) = 3     ≥1



Fig. 1. Example of existence and computation of IDPLDs of type III for structure function
ϕ(x1, x2) = x1x2 for x1  {0,1} and x2  {0,1,2,3}.


3.3 Calculation of Minimal Cut and Path Vectors using Integrated Direct
Partial Logic Derivatives

According to previous text, a MCV for level j of system availability agrees with a
state vector at which the structure function takes a value less than j and at which a
minor improvement (improvement by one state) of any non-perfectly working
component causes that the system achieves at least state j. Identification of state
vectors at which a minor improvement of component i results in such change of
system state can be done using IDPLDs  (h j  h j ) xi (s  s  1) for s = 0,1,…,
mi -2. If we compute these IDPLDs for all system components and combine them
together using some special conjunction, then we can identify all MCVs for level j of
system availability. This idea has been studied in [16], [17], where the following
algorithm for computation of MCVs has been formulated:
    1.    Repeat the next two steps for all system components:
             1.1. Compute expanded IDPLDs  e (h j  h j )  e xi (s  s  1) for
                    s = 0,1,…, mi -2.
               1.2. Calculate Π-conjunction m 2  e (h j  h j )  e xi (s  s  1) of the
                                                         i

                                                        s 0

                   expanded IDPLDs computed in the previous step.
    2.    Calculate Π-conjunction of the Π-conjunctions computed in step 1 and
          identify state vectors for which it takes value 1. These state vectors agree
          with the MCVs for level j of system availability.
   This algorithm does not use directly IDPLDs of type III but rather their expanded
versions that are defined also for state vectors at which IDPLDs cannot be computed.
In these situations, the expanded IDPLD takes value “*”:
                              1 if xi  s and  ( si , x )  j and  (ri , x )  j
          e (h j  h j )  
                             0 if xi  s and  ( si , x )  j or  (ri , x )  j ,
            e xi ( s  r )                                                                 (15)
                              * if xi  s
                    for s, r  0,1,, mi -1, s  r , j  1,2,, m-1.
   The Π-conjunction used in the algorithm is computed for two expanded IDPLDs
based on the rules defined in Table 1 [16], [17].

                Table 1. Π-conjunction of two expanded IDPLDs of type III.

                                                          e  ( h  j  h j )
                                Π-conjunction             e x i2 ( s 2  r2 )
                                                         *         0        1
                             e  ( h  j  h j )   *   *         0        1
                                                     0   0         0        0
                              e x i1 ( s1  r1 )
                                                     1   1         0        1

   The similar algorithm can also be used to find all MPVs for level j of system
availability [17]. The only difference is that expanded IDPLDs of the form of
 e (h j  h j )  e xi (s  s  1) , for s = 1,2,…, mi -1, have to be used. These expanded
derivatives are defined similarly as (15).
   After obtaining the MCVs or MPVs based on logical differential calculus, the
quantitative analysis of the investigated system can be performed. This is done simply
by computing FVI measures introduced in the previous part.


4 Hand Calculation Example

Previous parts of this paper presented a complex approach for investigation of MSSs.
This approach includes 1) computation of expanded IDPLDs, 2) identification of
MCVs or MPVs based on the derivatives, 3) evaluation of importance of states of the
system components (formulae (7) and (9)) or the total importance of the system
components (formulae (8) and (10)) for level j of system availability. Now, we will
illustrate some of these steps.
    Let us consider the service system used in [18]. It is composed of 3 components:
service point 1 (component 1), service point 2 (component 2), and infrastructure
(component 3). The system has 4 states with the following meaning: 0 –
nonfunctioning (no customer is satisfied by the service points), 1 – partially
functioning (some customers are satisfied), 2 – partially nonfunctioning (some
customers are not satisfied), 3 – perfectly functioning (all customers are satisfied).
The service points can be only functioning (state 1) or failed (state 0). The
infrastructure is modeled as a 4-state component where value 0 means that the
infrastructure is poor while value 3 agrees with its perfect quality. The system
structure function and the state probabilities of the components are defined in Table 2.
    If we want to investigate importance of the system components using the proposed
method, firstly the MCVs and MPVs of the system have to be computed. This can be
done using the algorithm described in the previous section. According to this
algorithm, firstly, expanded versions of IDPLDs of type III have to be computed. In
the second step, their Π-conjunction has to be calculated. Let us assume that we want
to find all MCVs and MPVs for level 1 of system availability. For this purpose,
expanded IDPLDs  e (h1  h1 )  e xi (s  s  1) and  e (h1  h1 )  e xi (s  s  1)
have to be calculated for all system components, i.e. for i = 1,2,3, and for all
components states for which they can be computed. In the next step, Π-conjunctions
including all relevant component states have to be calculated for every system
component. Please note components 1 and 2 have only 2 possible states, what implies
that the Π-conjunctions are equal to expanded derivatives  e (h1  h1 )  e x1 (0  1)
and  e (h1  h1 )  e x2 (0  1) respectively in the case of MCVs identification and
derivatives  e (h1  h1 )  e x1 (1  0) and  e (h1  h1 )  e x2 (1  0) respectively
in the case of MPVs identification. Therefore, there is no need to compute Π-
conjunctions for these two components. However, the 3-rd component has 4 states
and, therefore, the Π-conjunction has to be calculated. So, if we are interested in
MCVs, then expression 2  e (h1  h1 )  e x3 (s  s  1) has to be formed from
                                  s 0

the expanded IDPLDs, while conjunction 3  e (h1  h1 )  e x3 (s  s  1) has to
                                                           s 1
be found to identify the MPVs. Finally, using Π-conjunction we can combine the
expanded IDPLDs computed with respect to components 1 and 2 with the Π-
conjunction calculated for component 3 and identify all MCVs (MPVs) for level 1 of
system availability. For MCVs, these calculations are shown in Table 3. According to
this table, the system has two MCVs for the considered level of system availability,
i.e. (0,0,3) and (1,1,0). Similarly, we can compute that the MPVs are (0,1,1) and
(1,0,1). The similar procedure can be used to identify the MCVs and MPVs for levels
2 and 3 of system availability. The final results are in Table 4.

  Table 2. Structure function of the service system and state probabilities of its components.

                       Components
                                                                  x3 (p3,s)
                         states
                     x1 (p1,s)   x2 (p2,s)   0 (0.20)   1 (0.60)        2 (0.10)   3 (0.10)
                     0 (0.30) 0 (0.20)          0           0                 0       0
                     0 (0.30) 1 (0.80)          0           1                 1       2
                     1 (0.70) 0 (0.20)          0           1                 1       2
                     1 (0.70) 1 (0.80)          0           2                 3       3


  MCVs and MPVs identified in the previous step can be used to investigate
importance of individual states of the system components for a given level of system
availability. This can be done using FVI measures (7) and (9). For illustration, let us
compute FVI 3c,,11 , which quantifies contribution of minor degradation of state 1 of
component 3 to system unavailability U ≥1. Using MCVs, this measure can be
calculated in the following way:
                                                                  p
                         FVI 3c,,11  Pr( x1 , x2 ,0)  (1,1,0) 3, 01 ,                   (16)
                                                                  U
where unavailability U ≥1 can be computed using (4) as follows:
               U 1  Prx  (0,0,3)  x  (1,1,0)
                                                                                                             (17)
                     Prx  (0,0,3)  Prx  (1,1,0)  Prx  (0,0,0).

Using the numbers presented in Table 2, we obtain that FVI 3c,,11  0.8065 . In the
similar way, we can compute all other measures of the form of FVI 3c,,s j (Table 5).
According to the data presented in Table 5, we can state that a degradation of state 1
of component 3 contributes mainly to unavailabilities U ≥1 and U ≥2, a degradation of
state 2 to unavailabilities U ≥2 and U ≥3, and a degradation of state 3 contributes only
to unavailability U ≥3.

Table 3. Computation of the minimal cut vectors of the service system using expanded
integrated direct partial logic derivatives.

                             e (h1  h1 )     e (h1  h1 )    2
                                                                             e (h1  h1 )
  x1    x2    x3    ϕ(x)
                               e x1 (0  1)        e x 2 (0  1)
                                                                       x (s  s  1)
                                                                     s 0
                                                                                                 Π-conjunction
                                                                             e 3

   0    0     0       0            0                      0                        0                     0
   0    0     1       0            1                      1                        0                     0
   0    0     2       0            1                      1                        0                     0
   0    0     3       0            1                      1                        *                     1
   0    1     0       0            0                      *                        1                     0
   0    1     1       1            0                      *                        0                     0
   0    1     2       1            0                      *                        0                     0
   0    1     3       2            0                      *                        *                     0
   1    0     0       0            *                      0                        1                     0
   1    0     1       1            *                      0                        0                     0
   1    0     2       1            *                      0                        0                     0
   1    0     3       2            *                      0                        *                     0
   1    1     0       0            *                      *                        1                     1
   1    1     1       2            *                      *                        0                     0
   1    1     2       3            *                      *                        0                     0
   1    1     3       3            *                      *                        *                     *

Table 4. Minimal cut vectors and minimal path vectors for individual levels of availability of
the service system.


            System          Minimal cut vectors for given            Minimal path vectors for given
       availability level    level of system availability             level of system availability

               1                       (0,0,3), (1,1,0)                            (0,1,1), (1,0,1)
               2             (0,0,3), (0,1,2), (1,0,2), (1,1,0)              (0,1,3), (1,0,3), (1,1,1)
               3                  (0,1,3), (1,0,3), (1,1,1)                            (1,1,2)


   In the next step, we can sum all measures FVI 3c,,s j for given level j of system
availability. This allows us to evaluate the total contribution of component 3 to
system unavailability U ≥ j. Results of these calculations are presented in the right
column of Table 5, and they imply that component 3 has the greatest influence on
level 1 of system availability and the lowest on level 2. The similar investigations
could be done for the remaining two components or using MPVs.

Table 5. Fussell-Vesely’s importance measures for component 3 based on minimal cut vectors.

                                            Component state
                    Component 3                                   Sum
                                        1        2          3
                                  1   0.8065      0        0      0.8065
                   availability
                     System

                      level


                                  2   0.3891    0.3750   0.0856   0.4747

                                  3     0       0.6757     0      0.6757




5 Conclusion

In this paper, a complex approach for investigation of MSSs based on MCVs, MPVs,
and logical differential calculus was presented. The approach allows identifying all
MCVs or MPVs for a given level of system availability. Based on the MCVs or
MPVs several importance measures introduced in this paper can be computed. The
measures represent generalization of the FVI, which has been developed originally for
BSSs. The proposed generalizations of the FVI allows quantifying contribution of a
degradation (improvement) of a given state of a given system component to system
unavailability (availability) or total contribution of a given component to system
unavailability (availability).
   One of the most important parts of the approach presented in this paper is
identification of MCVs or MPVs. For this purpose, the algorithm based on IDPLDs
[16], [17] can be used. According to the experiments performed in [17], this algorithm
can be used for small and medium MSSs that are composed of 15 to 20 components
(depending on the number of components states). However, the main benefit of this
algorithm is that it can be applied to systems with complicated structure because, as
has been shown in [17], its time complexity does not depend on the number of MCVs
or MPVs, which closely relate to internal structure of the system.

Acknowledgment
This work was supported by grants VEGA 1/0038/16 and VEGA 1/0354/17.


References

1. Rausand, M., Høyland, A.: System Reliability Theory. John Wiley & Sons, Inc., Hoboken,
   NJ (2004)
2. Lisnianski, A., Frenkel, I., Ding, Y.: Multi-state System Reliability Analysis and
   Optimization for Engineers and Industrial Managers. Springer-Verlag London Ltd.,
   London, UK (2010)
3. Natvig, B.: Multistate Systems Reliability Theory with Applications. John Wiley & Sons,
    Ltd, Chichester, UK (2011)
4. Rauzy, A.: Mathematical foundations of minimal cutsets. IEEE Transactions on Reliability.
    50, 389–396 (2001)
5. Butler, D.A.: A complete importance ranking for components of binary coherent systems,
    with extensions to multi-state systems. Naval Research Logistics Quarterly. 26, 565–578
    (1979)
6. Vatn, J.: Finding minimal cut sets in a fault tree. Reliability Engineering & System Safety.
    36, 59–62 (1992)
7. Rauzy, A.: New algorithms for fault trees analysis. Reliability Engineering & System
    Safety. 40, 203–211 (1993)
8. Yeh, W.-C.: Search for all MCs in networks with unreliable nodes and arcs. Reliability
    Engineering & System Safety. 79, 95–101 (2003)
9. Vesely, W.E.: A time-dependent methodology for fault tree evaluation. Nuclear
    Engineering and Design. 13, 337–360 (1970)
10. Fussell, J.B.: How to hand-calculate system reliability and safety characteristics. IEEE
    Transactions on Reliability. R-24, 169–174 (1975)
11. Meng, F.C.: Comparing the importance of system components by some structural
    characteristics. IEEE Transactions on Reliability. 45, 59–65 (1996)
12. Kuo, W., Zhu, X.: Importance Measures in Reliability, Risk, and Optimization: Principles
    and Applications. Wiley, Chichester, UK (2012)
13. Yeh, W.-C.: Search for all d-Mincuts of a limited-flow network. Computers & Operations
    Research. 29, 1843–1858 (2002)
14. Yeh, W.-C.: A simple MC-based algorithm for evaluating reliability of stochastic-flow
    network with unreliable nodes. Reliability Engineering & System Safety. 83, 47–55 (2004)
15. Yeh, W.-C.: A fast algorithm for searching all multi-state minimal cuts. IEEE Transactions
    on Reliability. 57, 581–588 (2008)
16. Kvassay, M., Zaitseva, E., Levashenko, V., Kostolny, J.: Minimal cut vectors and logical
    differential calculus. In: 2014 IEEE 44th International Symposium on Multiple-Valued
    Logic. pp. 167–172. IEEE (2014)
17. Kvassay, M., Kostolny, J.: Evaluation of algorithms for identification of minimal cut
    vectors and minimal path vectors in multi-state systems. Komunikacie. 17, 8–14 (2015)
18. Kvassay, M., Zaitseva, E., Levashenko, V.: Minimal cut sets and direct partial logic
    derivatives in reliability analysis. In: Safety and Reliability: Methodology and Applications
    - Proceedings of the European Safety and Reliability Conference, ESREL 2014. pp. 241–
    248. CRC Press/Balkema (2015)
19. Kvet, M.: Index distribution management in attribute level temporal model. In: 2015
    International Conference on Information and Digital Technologies. pp. 206–214. IEEE
    (2015)
20. Kvassay, M., Levashenko, V., Zaitseva, E.: Analysis of minimal cut and path sets based on
    direct partial Boolean derivatives. Proceedings of the Institution of Mechanical Engineers,
    Part O: Journal of Risk and Reliability. 230, 147–161 (2016)
21. Zaitseva, E., Levashenko, V.: Multiple-valued logic mathematical approaches for multi-
    state system reliability analysis. Journal of Applied Logic. 11, 350–362 (2013)
22. Kvassay, M., Zaitseva, E., Kostolny, J., Levashenko, V.: Importance analysis of multi-state
    systems based on integrated direct partial logic derivatives. In: 2015 International
    Conference on Information and Digital Technologies (IDT). pp. 183–195. IEEE (2015)

</pre>