Reliability of linear multi-state multiple sliding window systems
Gregory Levitin
The Israel Electric Corporation Ltd., Haifa, Israel
E-mail:
Abstract
This paper proposes a new model that generalizes the linear consecutive k-out-of-r-from-n:F system to multi-state case with multiple failure criteria. In this model (named linear multi-state multiple sliding window system) the system consists of n linearly ordered multi-state elements (MEs). Each ME can have different states: from complete failure up to perfect functioning. A performance rate is associated with each state. Several functions are defined for a set of integer numbers in such a way that for each r corresponding function fr produces negative values if the combination of performance rates of r consecutive MEs corresponds to the unacceptable state of the system. The system fails if at least one of functions fr for any r consecutive MEs for r produces a negative value.
An algorithm for system reliability evaluation is suggested which is based on an extended universal moment generating function. Examples of system reliability evaluation are presented.
Keywords - multiple sliding window system, consecutive k-out-of-r-from-n:F system, multi-state element, universal moment generating function.
1. Introduction
The linear consecutive k-out-of-r-from-n:F system has n ordered elements and fails if at least k out of r consecutive elements fail. This system was formally introduced by Griffith [1], but had been mentioned previously by Tong [2], Saperstein [3,4], Naus [5] and Nelson [6] in connection with tests for non-random clustering, quality control and inspection procedures, service systems, and radar detection problems.
Consider for example a quality control system that selects randomly for a quality checkr items produced consecutively by a manufacturing process. If within the selected sample at least k items are defective, the system concludes that the process needs to be adjusted. If the process produces n items in a certain period of time, we are interested in the probability that such a random quality check is able to detect a problem in the process.
Different algorithms for evaluating the reliability of linear consecutive k-out-of-r-from-n:F systems were suggested in [7-9]. These algorithms either consider the case of identical elements (elements with equal reliability) and limited set of parameters [1,5,8] or provide bounds for system reliability [7-9] that are good enough only for element reliabilities very close to 1. An enumerative algorithm for exact evaluation of system reliability based on recursive computation of conditional probabilities was suggested by Malinowski and Preuss [10]. Because of the difficulty of estimating the exact value of system reliability, Psillakis [11] proposed a simulation approach and provided the error analysis.
A variety of models can be considered as special cases of the linear consecutive k-out-of-r-from-n:F system. When r=n, one has the well studied simple k-out-n:F system. When k=r, one has the consecutive k-out-of-n:F system, which was introduced by Chiang and Niu [12], and Bollinger [13,14]. The simple k-out-n:F system was generalized to the multi-state case by Wu & Chen in [15], where system elements have two states but can have different integer values of nominal performance rate. In [16] the general model is developed in which elements can have an arbitrary number of real-valued performance levels. The multi-state generalization of the consecutive k-out-of-n:F system was first suggested by Hwang & Yao [17] as a generalization of linear consecutive-k-out-of-n:F system and linear consecutively-connected system with 2-state elements, studied by Shanthikumar [18,19]. Algorithms for linear multistate consecutive k-out-of-n:F system reliability evaluation were developed by Hwang & Yao [17], Kossow & Preuss [20], Zuo & Liang [21].
This paper presents an exact algorithm for evaluating the reliability of a generalized consecutive k-out-of-r-from-n:F system. The system model is extended in two ways. First, it is assumed that each element can have several discrete states characterized by different real-valued performance rates. The system fails if some condition imposed on a function of performance rates of r consecutive elements is not met. Second, it is assumed that the failure criteria are defined for different numbers of consecutive elements. The system fails if at least one of the conditions for the groups of consecutive elements is not met.
In the general model, named the linear multi-state multiple sliding window system (MSWS), the system consists of n linearly ordered multi-state elements (MEs). Each ME can have several different states: from complete failure up to perfect functioning. A performance rate is associated with each state. A set of integer numbers is defined such that any r (1rn) corresponds to the number of consecutive MEs (length of sliding window). For each r a function fr(x1,…,xr) of r real-valued arguments (named the acceptability function) is defined in such a manner that fr<0 constitutes the failure. The MSWS fails if at least one of the functions fr(x1,…,xr) over the performance rates of any r consecutive MEs (for r) is negative.
Note that the special case of MSWS in which all of the n MEs are identical and have two states with performance rates 0 and 1 respectively, ={r} and
fr(x1,…,xr)=(1)
is k-out-of-r-from-n:F system.
The introduction of the MSWS model is motivated by the following examples.
Service system.
Consider a sequence of service stations in which each station should process the same sequence of n different tasks. Each station i can process ri incoming tasks simultaneously according to first-in-first-out rule using a limited resource wi. Each incoming task can have different states and the amount of the resource needed to process the task is different for each state of each task. The total resource needed to process ri consecutive tasks should not exceed the available amount of the resource wi. If in at least one of the stations there is no available resource to process ri tasks simultaneously, the system fails.
The simplest example of such a model is a transportation system in which n randomly ordered containers are carried by consecutive conveyors characterized by a different length and maximal allowable load. The number of containers ri that are loaded on each conveyor i is defined by its length. The transportation system fails if the total load of any one of the conveyors is greater than its maximal allowed load wi.
An example of the transportation system is presented in Fig. 1. The system consists of three conveyors and transports n=14randomly ordered containers of four types (each type m is characterized by its weight gm). The first conveyor can simultaneously carryr1=2 containers, the second and third conveyors can carryr2=6 and r3=3 containers respectively. The maximal allowable loads of conveyors 1, 2 and 3 are w1, w2 and w3 respectively. The system fails if the total weight of any two adjacent containers is greater than w1 or if the total weight of any six adjacent containers is greater than w2 or if the total weight of any three adjacent containers is greater than w3. The weight of j-th container in the line can be represented by a random value Gj: . The system acceptability function can be determined as:
for any group of riadjacent containers starting with h-th one(r1=2, r2=6, r3=3).
The system reliabilitytakes the form:
R=Pr{wi-0)},r1=2, r2=6, r3=3,
(where Pr{x} is the probability of event x).
Manufacturing.
Consider a heating system that should provide a certain temperature along several lines with moving parts placed at different distances from the heaters. The temperature at each point of the line i is determined by a cumulative effect of ri closest heaters. Each heater consists of several electrical heating elements. The heating effect of each heater depends on the availability of its heating elements and therefore can vary discretely (if the heaters are different, the number of different levels of heat radiation and the intensity of the radiation at each level are specific to each heater). In order to provide the temperature, which is not less than some specified value at each point of line i, any ri adjacent heaters should be in states where the sum of their radiation intensity is greater than the minimum allowed level wi. If any group of ri adjacent heaters provides the cumulative radiation intensity lower than wi the system fails.
In the example presented in Fig. 2 there are 12 heaters providing random radiation intensity Gj (1j12). The parts located at any point of the close conveyor are heated by three adjacent heaters.The cumulative heating intensity along this conveyor should not be lower than w1. The parts located at any point of the remote conveyor are heated by five adjacent heaters.The cumulative heating intensity along this conveyor should not be lower than w2. The system fails if any three adjacent heaters fail to provide the desired heating intensity w1or if any five adjacent heaters fail to provide the desired heating intensity w2. The system acceptability function can be defined as:
for any group of riadjacent heaters starting with h-th one (r1=3, r2=5).
The system reliability takes the form:
R=Pr{-wi0 )}, r1=3, r2=5.
A variety of other systems also fit the model: quality control systems that detect deviations from given values of parameters in a sample of products, combat systems that should provide certain fire density along a defense line, etc.
2. MSWS model
All n ordered MEs of MSWS are mutually statistically independent. The functioning of each ME j is characterized by its random performance rate Gj. Each ME j can be in one of Hj different states. Each state h{1,…,Hj} of ME j is characterized by its probability pj,h and performance rate gj,h: pj,h=Pr{Gj = gj,h},.
The set contains different positive integer numbers not greater than n (note that the cardinality of cannot be greater than n). An acceptability function fr for each rmaps r real valued arguments to the set of real values such that negative values correspond to the system failure. The entire system fails if for any rat least one of the functions fr(G1,…,Gr), fr(G2,…,Gr+1),…, fr(Gn-r+1,…,Gn) produces a negative value.
The MSWS reliability is, therefore, defined as follows:
R=Pr{fr(Gi,…,Gi+r-1)0)}. (2)
The following section describes the algorithm for evaluating the MSWS reliability.
3. MSWS reliability evaluation algorithm
The algorithms [7-11] suggested for evaluating reliability of linear consecutive k-out-of-r-from-n:F system are based on the binary nature of the system elements and, therefore, cannot be used for MSWS. The procedure used in this paper for MSWS reliability evaluation is based on the universal z-transform, also called u-function or universal moment generating function technique, which was introduced in [22] and which proved to be very effective for the reliability evaluation of different types of multi-state systems [23-29]. The u-function extends the widely known ordinary moment generating function. The essential difference between the ordinary and universal generating functions is that the latter allows one to evaluate probabilistic distributions of overall performance for a wide range of systems characterized by different topology, the different nature of interaction among system elements, and the different physical nature of the elements' performance measures.
3.1. Determination of u-functions for individual MEs and their groups
The u-function of a discrete random variable X is defined as a polynomial
(3)
where the variable X has K possible values and qk is the probability that X is equal to xk.
In our case, the u-function can define a ME performance rate distribution (PRD), i.e. it represents all of the possible states of the ME j by relating the probabilities of each state pj,h to the performance rate gj,h of the ME in the form:
(4)
In order to represent the PRD of a group consisting of r MEs one has to modify the u-function by replacing the random value X with the random vector Y={Y(1),…,Y(r)} consisting of random performance values corresponding to all the MEs belonging to the group (this replacement produces a vector-u-function).
Element Y(j) of vector Y is equal to the performance rate of j-th one out of r consecutive MEs. When the i-th group of MEs is considered (the group of MEs numbered from i to i+r-1) the random variable Y(j) represents the random performance of the i+j-1-th ME and takes the values from the set {}. Each combination of states of MEs belonging to the group constitutes a state of the group. The total number of different states of the i-th group is equal to the number of possible combinations of the states of the individual MEs belonging to the group. Since all the MEs are statistically independent and each ME j has Hj states, the total number of states of the group is
Ei,r=.(5)
Therefore the vector-u-function Ui,r(z) corresponding to i-th group of r MEs consists of Ei,r different terms.
Consider a state m of the i-th group that corresponds to state hj of each individual ME j: iji+r-1. The performance values of the elements of the i-th group in state m are represented by the realization ym of the random vector Y: ym={}. The probability of any state of the group is equal to the product of the probabilities of the corresponding states of the individual independent MEs.
For example, the vector-u-function for a group of two MEs i and i+1 (r=2) takes the form:
,(6)
where is a probability of an event in which ME i is in state hi and ME i+1 is in state hi+1. It can be easily seen that for the statistically independent MEs . Therefore, the vector-u-function of the group can be obtained by applying the following operator over u-functions of individual MEs:
(7)
Applying the operator over u-functions of r consecutive MEs one obtains the vector-u-function corresponding to the group containing these MEs:
(8)
Simplifying this representation one obtains:
,(9)
where Qm is the probability that the i-th group is in state m and vector ym consists of values of MEs performance rates at state m. The obtained vector-u-function defines all of the possible states of the i-th group of r MEs. Having the vectors ym representing performance rates of MEs belonging to the i-th group in any state m one can obtain the acceptability function of the group in this state as fr(ym). By summing the probabilities of all of the states in which the acceptability function is negative, one can obtain the probability of failure of the i-th group of r consecutive MEs. To do so one can use the following operator r:
,(10)
where
.
Example 1.
Consider a system consisting of two MEs with random performances G1 and G2. The PRD of the elements are Pr{G1=3}=0.6,Pr{G1=1}=0.4 and Pr{G2=1}=0.2,Pr{G2=2}=0.6,Pr{G2=0}=0.2. According to Eq. (4) the u-functions of the elements take the form
u1(z)=0.6z3+0.4z1, u2(z)=0.2z1+0.6z2+0.2z0.
Following Eq. (8) we obtain the vector-u-function for the group of these two MEs as
3.2. Determination of u-functions for all the groups of r consecutive MEs
Note that the MSWS considered contains exactly n-r+1 groups of r consecutive MEs and each ME can belong to no more than r such groups. To obtain the u-functions corresponding to all the groups of r consecutive MEs the following procedure is introduced:
1. Define u-function U1-r,r(z) as follows
U1-r,r(z)=,(11)
where the vector y0 consists of r zeros.
2. Define the following operator over vector-u-function Ui,r(z) and u-function of individual ME ui+r(z):
,(12)
where operator over arbitrary vector y and value x shifts all the vector elements one position left: y(s-1)=y(s) for 1<sr and assigns the value x to the last element of y: y(r)=x (the first element of vector y disappears after applying the operator). The operator removes the performance value of the first ME of the group and adds the performance value of the next (not considered yet) ME to the group preserving the order of MEs belonging to the group. Therefore, applying the operator over vector-u-function representing performance distribution of the i-th group of r MEs one obtains the vector-u-function representing the performance distribution of the i+1-th group (when the MEs from 1 to i are in certain states).
- Using the operator in sequence as follows:
(13)
for j=1,…,n one obtains vector-u-functions for all of the possible groups of r consecutive MEs: U1,r(z), …, Un-r+1,r(z). Note that the vector-u-function for the first group U1,r(z) is obtained after applying the operator r times. In the vector-u-function Ui,r(z) (for i>0), value y(j) of vector y corresponds to the performance rate of ME i+j-1.
Consider a vector-u-function Ui,r(z). For each combination of values y(2),…,y(r) it contains exactly Hidifferent terms corresponding to different values of y(1), which takes all of the possible values of the performance rate of ME i. After applying operator, y(1) disappears from the vector y being replaced with y(2). This produces Hi terms with the same vector y in the vector-u-function Ui+1,r(z). The coefficient of each term corresponding to vector y is equal to the conditional probability that the i+1-th group of MEs has performance rates ygiven ME i has one of its possible performance rates. By summing these coefficients (collecting like terms in Ui+1,r(z)), one obtains a single term for each vector y with a coefficient equal to the overall probability that the i+1-th group of MEs has performance rates y. Therefore, the number of different terms in each vector-u-function Ui,r(z) is equal to.
Example 2.
Consider the previous example and add to the system a new element with PRD Pr{G3=4}=0.7,Pr{G1=0}=0.3. Using the recursive equation (13) and operator (12) we obtain the vector-u-functions corresponding to all of the groups of r=2 MEs.
U-1,2(z)=z{0,0}.
U0,2(z)=(U-1,2(z),u1(z))=(z{0,0},0.6z3+0.4z1)=0.6z{0,3}+0.4z{0,1};
U1,2(z)=(U0,2(z),u2(z))=(0.6z{0,3}+0.4z{1,2},0.2z1+0.6z2+0.2z0)=0.6z{0,3}+0.4z{1,2}=
.
This vector-u-function is equal to one obtained in Example 1 for the group of the two first MEs. Applying the operator once more we obtain the vector-u-function representing the PRD of the next group of MEs (second and third MEs)
U2,2(z)=(U1,2(z),u3(z))=
This procedure produced H1=2 terms for each value of the vector y (representing combination of values G2 and G3). The first term corresponds to the conditional probability
Pr{}
and the second term corresponds to the conditional probability
Pr{ }.
Collecting the like terms in U2,2(z) gives the unconditional PRD of the group of MEs 2 and 3:
Applying the operator r (9) to the vector-u-functions U1,r(z), …, Un-r+1,r(z) one can obtain the failure probability for each group of r consecutive MEs.