A Fast and Robust Reliability Evaluation Algorithm for Generalized Multi-State k-out-of-n Systems

The generalized multi-state k-out-of-n system model proposed recently provides more flexibility in describing practical systems. In this model, there are n components in the system where each component, as well as the system, can be in one of M + 1 possible states: 0, 1, ... , m. The system is in state j or above if there exists an integer value l(j <= l <= M) such that at least k(l) components are in state 1 or above. Although the model has several practical applications, existing methods for computing either the exact, or approximate reliability of these systems are computationally inefficient, and limited to very small systems. In this paper, we propose an efficient method, and a detailed algorithm to compute the exact reliability of multi-state k-out-of-n systems. The method is based on conditional probabilities, and is applicable to all cases of multi-state k-out-of-n systems: 1) constant, 2) decreasing, 3) increasing, and 4) non-monotone k values. The proposed algorithm is fast, and robust. The computational time complexity of the algorithm is O(knM), and the space complexity is O(n + M) where k = mean {k(i)}. Using this algorithm, the reliability of very large multi-state k-out-of-n systems can be computed in a short time. For example, the exact reliability of a system with 500 components with 200 possible states can be computed in less than one second. Several numerical examples, including the published examples, are considered to illustrate the effectiveness, and efficiency of the proposed method. In addition to the detailed algorithm, and theoretical background, we also provide the complete listing of the MATLAB code used in the calculations.