An O(k3·log(n/k)) algorithm for theconsecutive-k-out-of-n:F system

The fastest generally-recognized algorithms for computing the reliability of consecutive-k-out-of-n:F systems require O(n) time, for both the linear and circular systems. The authors' new algorithm requires O(k³·log(n/k)) time. The algorithm can be extended to yield an O(n·max{k³·log(n/k), log(n))} total time procedure for solving the combinatorial problem of counting the number of working states, with w working and n-w failed components, w=1,2,...,n     

Reliability of a linear connected-(r,s)-out-of-(m,n):F latticesystem

A linear connected-(r,s)-out-of-(m,n):F lattice system has its components ordered like the elements of a (m,n)-matrix such that the system fails if all components in a connected (r,s)-submatrix fail. This paper proposes a recursive algorithm, named Yamamoto-Miyakawa (YM), for the system reliability. The YM algorithm requires O(s^m-r·m²·r·n) computing time. Comparisons with the existing methods show its usefulness. We prove that the reliability of the large system tends to exp(-μ·λ^r·s) as n=μ·M^η-1, m→∞ if every component has failure probability λ·M^η(r·s/), where μ, λ, η are constant, μ>0, λ>0, η>s, or r/(r-1)>η>1     

An Efficient Algorithm for Computing the Reliability of Consecutive-$k$-Out-Of-$n$:F Systems

Many algorithms for computing the reliability of linear or circular consecutive-k-out-of-n:F systems appeared in this Transactions. The best complexity estimate obtained for solving this problem is O(k³ log(n/k)) operations in the case of i.i.d. components. Using fast algorithms for computing a selected term of a linear recurrence with constant coefficients, we provide an algorithm having arithmetic complexity O(k log (k) log(log(k)) log(n)+k^omega) where 2相似文献   

Reliability of a connected-(r1, s1)-or-(r2, s2)-or-..-or-(rk, sk)-out-of-(m,n): F lattice system

A (linear or circular) connected-(r₁, s₁)-or-(r₂, s₂)-or-^{. .}-or-(r_k, s_k)-out-of-(m, n): F lattice system is the (linear or circular) (m, n)-lattice system if the system fails whenever all components in a connected-(r₁, s₁)-submatrix or all components in a connected-(r₂, s₂)-submatrix or ^{. .} or all components in a connected-(r_k, s_k)-submatrix fail. This paper presents a recursive algorithm for the reliability of the (linear or circular) connected-(r₁, s₁)-or-(r₂, s₂)or-^{. .}-or-(r_k,s_k)-out- of-(m, n):F lattice system. The recursive algorithm requires time and time in the linear case and the circular case, respectively Furthermore, we can reduce the more computing time in the statistically independent and identically distributed case or considering some special systems. Especially, the closed formula is given for the reliability of the linear connected-(2, 1)-or-(1, 2)-out-of-(m, 2): F lattice system in the statistically independent and identically distributed case.     

Efficient algorithms for k-out-of-n andconsecutive-weighted-k-out-of-n:F system

A new reliability model, consecutive-weighted-k-out-of-n:F system, is proposed and an O(n) algorithm is provided to evaluate its reliability. An O(n·min(n,k)) algorithm is also presented for the circular case of this model. The authors design an O(n) parallel algorithm using k processors to compute the reliability of k-out-of-n systems, that achieves linear speedup     

An O(n·(log2(n))2) algorithm forcomputing the reliability of k-out-of-n:G and k-to-l-out-of-n:G systems

This paper presents the RAFFT-GFP (Recursively Applied Fast Fourier Transform for Generator Function Products) algorithm as a computationally superior algorithm for expressing and computing the reliability of k-out-of-n:G and k-to-l-out-of-n:G systems using the fast Fourier transform. Originally suggested by Barlow and Heidtmann (1984), generating functions provide a clear, concise method for computing the reliabilities of such systems. By recursively applying the FFT to computing generator function products, the RAFFT-GFP achieves an overall asymptotic computational complexity of O(n·(log₂(n)) ²) for computing system reliability. Algebraic manipulations suggested by Upadhyaya and Pham (1993) are reformulated in the context of generator functions to reduce the number of computations. The number of computations and the CPU time are used to compare the performance of the RAFFT-GFP algorithm to the best found in the literature. Due to larger overheads required, the RAFFT-GFP algorithm is superior for problem sizes larger than about 4000 components, in terms of both computation and CPU time for the examples studied in this paper. Lastly, studies of very large systems with unequal reliabilities indicate that the binomial distribution gives a good approximation for generating function coefficients, allowing algebraic solutions for system reliability     

Bounds for reliability of k-within connected-(r, s)-out-of-(m, n) failure systems

A k-within linear connected-(r, s)-out-of-(m, n) failure system is a two-dimensional grid whose components are ordered like the elements of an (m, n)-matrix. A k-within circular connected-(r, s)-out-of (m, n) failure system consists of the intersection points of m circles centered at the same point with n rays starting from that point and crossing the circles. The components of both systems either operate or fail. By definition, a k-within (linear or circular) connected-(r, s)-out-of-(m, n) failure system fails if at least one (r, s)-submatrix contains k or more failed components. These systems are used as mathematical models for design and operation of many engineering systems. For systems with statistically independent and identically distributed components, a lower and upper bound of system reliability are derived using improved Bonferroni inequalities. These bounds are easy to compute and provide good estimates for system reliability. New bounds for the reliability of other connected-(r, s)-out-of-(m, n) failure systems existing in the current literature are also obtained. Several failure systems with various values of the parameters k, r, s, m, n and p are used as numerical examples for comparison and illustrative purposes.     

Fast optimal diagnosis procedures for k-out-of-n:G systems

A k-out-of-n:G system consists of a set of components, where each component is either faulty or fault-free. The system is working if at least k components are fault-free. The problem of finding an optimal diagnosis procedure for a given k-out-of-n:G system has been considered in several research fields including medical diagnosis, redundant-system testing, and searching data-files. A polynomial-time algorithm for this problem was presented first by Salloum, and later by Salloum and Breuer, and independently by Ben-Dov. This paper implements the Salloum-Breuer-Ben-Dov algorithm, leading to an optimal diagnosis procedure that can determine the state of any given system in O(n·log(n)) time complexity and O(n) space complexity. The efficiency is achieved by using a generalized radix sorting procedure that uses a heap data structure. For some k-out-of-n:G systems, including those with equal testing costs for all components, the components along the leftmost and rightmost paths in the optimal diagnostic tree uniquely determine the other components in the tree. This property is used to devise a faster optimal diagnosis procedure than the one for the general k-out-of-n:G system. With regard to complexity, these procedures are the best solutions for the problem under consideration. This conjecture is supported by the fact that all these procedures require a sorting operation which has O(n·log(n)) as a lower bound on its time complexity     

Reliability Analysis of the k-out-of-n:F System

A class of repairable systems known as k-out-of-n:F systems, 1 ? k ? n, consists of n units in parallel redundancy which are serviced by a single repairman; system failure occurs when k units are simultaneously inoperable for the first time. In this paper, assuming constant failure rates and general repair distributions, reliability characteristics of the k-out-of-n:F system are treated using two different methods. In Part I, a conditional transform approach is applied to the 2-out-of-n:F system. Transforms of distributions are obtained for T (the time to system failure), the time spent on repairs during (0, T) and the free time of the repairman during (0, T). In Part II, the supplementary variable technique is used to investigate time to failure characteristics of the k-out-of-n:F system for k = 2 and k = 3. A model of an airport limousine service illustrates the use of the results.     

Stochastic ordering results for consecutive k-out-of-n:F systems

A linear (circular) consecutive k-out-of-n:F system is a system of n linearly (circularly) ordered components which fails if and only if at least k consecutive components fail. We use recursive relationships on the reliability of such systems with independent identically distributed components to show that for any fixed k, the lifetime of a (linear or circular) consecutive k-out-of-n:F system is stochastically decreasing in n. This result also holds for linear systems when the components are independent and not necessarily identically distributed, but not in general for circular systems.     

An O(k/sup 2//spl middot/log(n)) algorithm for computing the reliability of consecutive-k-out-of-n: F systems

This study presents an O(k/sup 2//spl middot/log(n)) algorithm for computing the reliability of a linear as well as a circular consecutive-k-out-of-n: F system. The proposed algorithm is more efficient and much simpler than the O(k/sup 3//spl middot/log(n/k)) algorithm of Hwang & Wright.     

Failure Probability of Strict Consecutive-k-out-of-n:F Systems

A system with n components in sequence is a strict consecutive-k-out-of-n:F system if and only if it fails when at least k consecutive components are failed, but isolated strings of component failures of length less than k do not occur. This paper gives the failure probability function of a strict linear consecutive-k-out-of-n:F system in a closed form. The calculation of the failure probability of a strict circular consecutive-k-out-of-n:F system is reduced to the linear case.     

Reliability of Combined $k{hbox{-out-of-}}n$ and Consecutive $k_{c}{hbox{-out-of-}}n$ Systems of Markov Dependent Components

A combined $k{hbox{-out-of-}}n$ :$F(G)$ & consecutive $k_{c}{hbox{-out-of-}}n{hbox{:}}F(G)$ system fails (functions) iff at least $k$ components fail (function), or at least $k_{c}$ consecutive components fail (function). These models involve two common failure criteria, and can be used in various situations depending on the actual failure criteria involving consecutive components, or all components. Explicit formulas for the reliabilities of these systems are obtained for Markov dependent components using the distribution theory of runs. Some numerical results are also presented.      

Fuzzy consecutive-k-out-of-n:F system reliability

In this paper, we propose a new method to analyze fuzzy consecutive-k-out-of-n:F system reliability using fuzzy GERT. The triangular fuzzy numbers are used to fuzzify probabilities of the consecutive-k-out-of-n:F system and the interval arithmetic, α-cuts and an index of optimism λ are applied to compute fuzzy consecutive-k-out-of-n:F system reliability on fuzzy the GERT network. Futhermore, we can obtain all computation results by “MATHEMATICA” package.     

Direct Computation for Consecutive-k-out-of-n: F Systems

A consecutive-k-out-of-n: F system has n i.i.d. components; the system fails if any k consecutive components fail. This paper gives a simple, direct combinatorial method for determining the system failure probability.     

Reliability of linear consecutively-connected systems withmultistate components

A linear consecutively-connected system with multistate components (LCCSMC) consists of n+2 linear ordered statistically independent multistate components C_i, i∈[0,n], and the sink C_n+1 (which is absolutely reliable in a certain sense). System failure is caused by the C_i. If C_i is in state 0 then it is failed, if it is in the state j (1⩽j⩽k_j for a given k_j) then there are paths from C_i to the next min(j,n-i+1) components. The system fails if there is no path from C₀ to C_n+1. This system generalizes the linear consecutive-k-out-of-n:F system and the consecutively-connected system of Shanthikumar (1987). The paper gives recursive algorithms for determining the LCCSMC reliability     

顺序k/n(F)系统可靠性算法改进

在元件可靠性不相同的一般情况下,本文给出了线状/环状顺序k/n(F)系统可靠性的计算方法,算法完全排除了所有可能出现的相消项,使系统可靠性公式中项数降到最少,且具有极强的规律性,从而大大减少了计算复杂度。     

Strict Consecutive-k-out-of-n:F Systems

A method is given for calculating the failure probability function for consecutive-k-out-of-n:F systems which operate in such a way that isolated strings of failures of length less than k (which do not cause system failure) do not occur, or are immedately corrected; ie, when system failure occurs it is because all failures present are in strings of length at least k.     

Reliability of a large consecutive-k-out-of-r-from-n:F system withunequal component-reliability

For a consecutive-k-out-of-r-from-n:F system with unequal component reliability: (1) upper and lower reliability bounds are obtained; and (2) a limit formula and a life distribution for the reliability of a large system are derived under certain conditions. Many previous results on the reliability of the consecutive-k-out-of-n:F system are special cases of this paper     

On Reliability of a Large Consecutive-k-out-of-n:F System with (k - 1)-step Markov Dependence

This paper studies the reliability of a large consecutive-k-out-of-n:F system when the component failure states have (k - 1)-step Markov dependence.