Unification of mathematical concepts and algorithms of k-out-of-n system reliability: A perspective of improved disjoint products

Ali Muhammad Rushdi, Alaa Mohammad Alturki

Abstract


The k-out-of-n system model is the most prominent model of coherent system reliability, with a variety of important special cases, generalizations, and extensions thereof. In particular, the k-outof- n reliabilities (1 ≤ k ≤ n) constitute a basis for expressing the reliability of an n-order coherent
system in terms of its signature (destruction spectrum). A notable algorithm for computing the reliability of a k-out-of-n system is the Improved Disjoint Products (IMDP) algorithm. This paper has four goals, namely, (a) to present a detailed and novel exposition of the IMDP algorithm; (b) to demonstrate that the IMDP algorithm is derivable from the BH-2 algorithm, which is an enhancement of the BH-1 algorithm that is used for evaluating the probability of exactly k successes among n Bernoulli trials and, hence, for computing the probability mass function (pmf) of the generalized binomial distribution; (c) to demonstrate that the IMDP algorithm can be derived from the AR algorithm, which is the Reduced-Ordered-Binary-Decision-Diagram (ROBDD) algorithm for evaluating the k-out-of-n reliability and also for computing the Cumulative Distribution
Function (CDF) of the generalized binomial distribution; and (d) to show that the IMDP algorithm is a collective orthogonalization (disjointness) algorithm for a shellable sum-of-products formula (DNF) for k-out-of-n success. The paper plays a unifying role for a variety of concepts and algorithms and tries to emphasize similarities and interrelations among them, while pinpointing any subtle differences among them. A common denominator in explaining the various algorithms is the use of signal flow graphs that are compact, regular, and acyclic. For these loopless graphs, the gain formula requires only simple path enumeration, as well as a calculation of the transmittances of the paths.


Keywords


k-out-of-n, reliability, Improved disjoint products, Shellability, Signature, Unification, The AR algorithm, The BH-2 algorithm, Signal flow graphs.

Full Text:

PDF

References


Abraham, J. A. 1979. An improved algorithm for network reliability, IEEE Transactions on Reliability,

R-28(1): 58–61.

Agrawal, A. & Barlow, R. E. 1984. A survey of network reliability and domination theory. Operations Research,

(3): 478–492.

Akers, S. 1960. Binary decision diagrams, IEEE Transaction on Computers, C-27(6): 509–516.

Al-Qasimi, A.M. &. Rushdi, A.M. 2008. A tutorial on how to efficiently calculate and format tables of the

Binomial Distribution. Journal of King Abdulaziz University: Engineering Sciences, 19(1): 3–17.

Alturki, A. M. & Rushdi, A. M. 2016. Weighted voting systems: A threshold-Boolean perspective, Journal

of Engineering Research. 4(1): 125–143.

Amari, S. V. & Bergman, R. 2008. Reliability analysis of k-out-of-n load-sharing systems. In the Annual

IEEE Reliability and Maintainability Symposium, 2008 (RAMS 2008): 440–445.

Amari V., Misra B. Krishna & Pham Hoang. 2008. Tampered failure rate load-sharing systems: status and

perspectives. Handbook of performability engineering. Springer London,. 291–308.

Amari, S. V., Zuo, M. J. & Dill, G. 2008. O(kn) Algorithms for Analyzing Repairable and Non-Repairable

k-out-of-n: G Systems. Chapter 21 in: Handbook of Performability Engineering, Misra, K.B. (Editpor).

Springer, London, UK: 309–320.

Ball, M. O. & Provan, J. S. 1988. Disjoint products and efficient computation of reliability, Operations

Research, 36(5): 703–715.

Bamasak, S. M. & Rushdi, A. M. 2016. Uncertainty analysis of fault-tree models for power system protection.

Journal of Qassim University: Engineering and Computer Sciences, 8(1): 65–80.

Barlow, R. E. & Heidtmann, K. D. 1984. Comments and reply on ‘Computing k-out-of-n system reliability’,

IEEE Transactions on Reliability, R-33(4): 322–323.

Barlow, R. E. & Iyer, S. 1988. Computational complexity of coherent systems and the reliability polynomial.

Probability in the Engineering and Informational Sciences, 2(4): 461–469.

Barlow, R. E. & Proschan, F. 1996. Mathematical Theory of Reliability, SIAM, New York, NY, USA.

Belfore, II, L. A. 1995. An O(n(log2n)2) Algorithm for Computing the Reliability of k-out-of-n:G & k-to-

-out-of-n:G Systems, IEEE Transactions on Reliability, 44(1): 132–136.

Bergman, B. 1985. On reliability theory and its applications (with discussion), Scandinavian Journal of

Statistics, 12(1): 1–41.

Birnbaum, Z. W., Esary, J. D. & Saunders, S. 1961. Multi-Component systems and structures and their

reliability, Technometrics, 3(1): 55–77.

Bjorkman k. 2013. Solving dynamic flow graph methodology models using binary decision diagrams. Reliability

Engineering & System Safety; 111:206–16.

Boland, P. J. 2001. Signatures of indirect majority systems, Journal of Applied Probability, 38: 597–603.

Boland, P. J. & Samaniego, F. J. 2004a. The Signature of a Coherent System and its Applications in Reliability.

In: Soyer, R., Mazzuchi, T. A., Singpurwalla, N. D. (Editors) Mathematical Reliability: An Expository

Perspective, pp. 3-30, Kluwer Academic Publishers, Boston, MA, USA.

Boland, P. J. & Samaniego, F. J. 2004b. Stochastic Ordering Results for Consecutive k-out-of-n Systems.

IEEE Transactions on Reliability, 53(1): 7–10.

Boland, P. J., Samaniego, F. J. & Vestrup, E. M. 2003. Linking Dominations and Signatures in Network

Reliabity Theory. In: Lindqvist, B., Doksum, K. (Editors) Mathematical and Statistical Methods in

Reliability. World Scientific, Singapore, pp.89–103.

Boutsikas, M. V. & Koutras, M. V. 2000. Reliability approximation for Markov chain imbeddable systems.

Methodology and Computing in Applied Probability, 2(4): 393–411.

Brown, F. M. 1990. Boolean Reasoning: The Logic of Boolean Equations, Kluwer Academic Publishers,

Boston, USA.

Bryant, R. 1986. Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers,

(8): 677–691.

Chao, M. T. & Fu, J. C. 1989. A limit theorem of certain repairable systems. Annals of the Institute of Statistical

Mathematics, 41: 809–818.

Chao, M. T. & Fu, J. C. 1991. The reliability of large series system under Markov structure, Advances of

Applied Probability, 41: 894–908.

Cochran, J. K. & Lewis, T. P. 2002. Computing small-fleet aircraft availabilities including redundancy and

spares. Computers & Operations Research, 29(5): 529–540.

Crama, Y. & Hammer, P. L. 2011. Boolean functions: Theory, Algorithms, and Applications, Cambridge,

United Kingdom, Cambridge University Press.

Cui, L., Xu, Y. & Zhao, X. 2010. Developments and applications of the finite Markov chain imbedding approach

in reliability. IEEE Transactions on Reliability, 4(59): 685–690.

Dotson, W. & Gobien J., 1979. A new analysis technique for probabilistic graphs, IEEE Transactions on

Circuits and Systems, CAS-26(10): 855–865.

Dutuit, Y. & Rauzy, A. 2001. New insight into the assessment of k-out-of-n and related systems, Reliability

Engineering & System Safety, 72(2): 303–314.

Fu, J. C. 1986. Reliability of consecutive-k-out-of-n: F systems with (k-1)-step Markov dependence. IEEE

Transactions on Reliability, 35(5): 602–606.

Fu, J. C. & Koutras, M. V. 1994. Distribution theory of runs: a Markov chain approach. Journal of the

American Statistical Association, 89(427): 1050–1058

Golnaraghi, F. & Kuo, B. C. 2009. Automatic Control Systems, Ninth Edition, John Wiley & Sons, New

York. NY, USA.

Hiroshima, T., Yamachi, H., Tsujimura, Y., Yamamoto, H. & Kambayashi, Y. 2006. Evaluating ability of

a branch and bound method designed for solving bi-objective NVP design problem. In Advanced Reliability

Modeling II: Reliability Testing and Improvement: Proceedings of the 2nd Asian International

Workshop (AIWARM 2006), Busan, Korea, 24–26 August 2006 (p. 124). World Scientific.

Heidtmann, K. D. 1982. Improved method of inclusion-exclusion applied to k-out-of-n systems, IEEE

Transactions on Reliability, 31(1): 36–40.

Kaufmann, A., Grouchko D. & Cruon R., 1977. Mathematical Methods for the Study of the Reliability of

Systems, Academic Press, New York, NY, USA.

Kochar, K., Mukerjee, H. & Samaniego, F.J. 1999. The ‘signature’ of a coherent system and its application

to comparisons among systems, Naval Research Logistics, 46: 507–523.

Koutras, M. V. 1996. On a Markov chain approach for the study of reliability structures. Journal of Applied

Probability, 33(2): 357–367.

Kuo, W. & Zuo, M. J. 2003. The k-out-of-n System Model. In: Optimal Reliability Modelling: Principles and

Applications, Kuo, W. and M.J. Zuo (Eds.). Chapter 7, John Wiley and Sons, New York, USA, pp: 231–280.

Kvam, P. H. & Pena, E. A. 2005. Estimating load-sharing properties in a dynamic reliability system. Journal

of the American Statistical Association, 100(469), 262–272.

Levitin, G., Xing, L. & Amari, S. V. 2012. Recursive algorithm for reliability evaluation of non-repairable

phased mission systems with binary elements. IEEE Transactions on Reliability, 61(2), 533–542.

Li, S., Si, S., Dui H, Cai Z. & Sun S. 2014. A novel decision diagrams extension method. Reliability

Engineering & System Safety, 126: 107–115.

Liu, H. 1998. Reliability of a load-sharing k-out-of-n: G system: non-iid components with arbitrary distributions.

IEEE Transactions on Reliability, 47(3), 279–284.

Locks, M. O. & Heidtmann, K. D. 1984. Comments and reply on : Improved method of inclusion-exclusion

applied to k-out-of-n systems, IEEE Transaction on Reliability, 33(4): 321–322.

Marichal, J. - L. & Mathonet, P., 2013. Computing system signatures through reliability functions, Statistics

and Probability Letters, 83: 710–717.

Marichal, J. – L., Mathonet, P. & Waldhauser. T. 2011. On signature – based expressions of system reliability,

Journal of Multivariate Analysis, 102(10): 1410–1416.

Milad, M. S., Feceniuk, A. P. & Romankevich, V. A. 2012. The probability of multiprocessor system falling

into dangerous state estimation. Радіоелектронні і комп’ютерні системи (Radio Electronics and Com�-

puter Systems: Journal of the National Technical University of Ukraine), (6): 38–41.

Misra, K. B. 1992. Reliability Analysis and Prediction : A Methodology Oriented Treatment. Elsevier

Science Publishers, Amsterdam, The Netherlands.

Misra, K. B. (Editor), 2008. Handbook of Performability Engineering, Springer, London, UK.

Mo, Y. 2014. A multiple-valued decision-based approach to solve dynamic fault tree. IEEE Transactions on

Reliability, 63(1): 81–93.

Mo, Y., Xing , L. & Amari, S. V. 2014. A multiple-valued decision diagram based method for efficient reliability

analysis of non-repairable phased-mission systems. IEEE Transaction Reliability; 63(1): 320–30.

Mo, Y., Xing , L., Amari, S. V. & Dugan, J. B. 2015. Efficient analysis of multi-state k-out-of-n system,

Reliability Engineering and System Safety, 133: 95–105.

Muroga, S. 1979. Logic Design and Switching Theory, Wiley, New York, NY, USA.

Papadimitratos, P. & Haas, Z. J. 2006. Secure data communication in mobile ad hoc networks. IEEE Jour�-

nal on Selected Areas in Communications, 24(2): 343–356.

Pock M, Malass EO & Walter M. 2011. Combining different binary decision diagram techniques for solving

models with multiple failure states. Journal of Risk and Reliability, 225(1): 18–27.

Rauzy, A. 2008. Binary Decision Diagrams for Reliability Studies, Chapter 25 in Misra, K. B. (Editor), Handbook

of Performability Engineering, Springer, London, UK, pp. 381–396.

Rushdi, A. M. 1983. Symbolic reliability analysis with the aid of variable-entered Karnaugh maps, IEEE

Transactions on Reliability, R-32(2): 134–139.

Rushdi, A. M. 1985. Uncertainty analysis of fault-tree outputs, IEEE Transactions on Reliability, R-34(5):

–462.

Rushdi, A. M. 1986. Utilization of symmetric switching functions in the computation of k-out-of-n system

reliability, Microelectronics and Reliability, 26(5): 973–987.

Rushdi, A. M. 1987. Efficient computation of k-to-l-out-of-n system reliability, Reliability Engineering, vol.

, no. 3, pp. 157 -163, 1987, Erratum : ibid, 19(4): 321, 1987.

Rushdi, A. M. 1990. Threshold systems and their reliability, Microelectronics and Reliability, 30(2):

–312.

Rushdi, A. M. 1991. Comments on : An efficient non-recursive algorithm for computing the reliability of

k-out-of-n systems, IEEE Transactions on Reliability, 40(1): 60–61.

Rushdi, A. M. 1993. Reliability of k-out-of-n Systems, Chapter 5 in Misra, K. B. (Editor), New Trends in

System Reliability Evaluation, Vol. 16, Fundamental Studies in Engineering, Elsevier Science Publishers,

Amsterdam, The Netherlands, pp. 185–227.

Rushdi, A. M. 2010. Partially-redundant systems: Examples, reliability, and life expectancy, International

Magazine on Advances in Computer Science and Telecommunications, 1(1): 1–13.

Rushdi, A. M. & Abdul Ghani, A. A. 1993. A comparison between reliability analyses based primarily on

disjointness or statistical independence : The case of the generalized INDRA network, Microelectronics

and Reliability, 33(7): 965–978.

Rushdi, A.M. & Al-Hindi, K.A. 1993, A table for the lower boundary of the region of useful redundancy for

k-out-of-n systems, Microelectronics and Reliability, 33: 979–992.

Rushdi, A. M. & Al-Khateeb, D. L. 1983. A review of methods for system reliability analysis: A Karnaughmap

perspective, Proceedings of the First Saudi Engineering Conference, Jeddah, Saudi Arabia, 1: 57–95.

Rushdi, A.M. & Al-Qasimi, A.M. 1994. Efficient computation of the P.M.F. and the C.D.F. of the generalized

binomial distribution. Microelectronics and Reliability, 34: 1489–1499.

Rushdi, A. M. & Al-Thubaity, A. O. 1993. Efficient computation of the sensitivity of k-out-of-n system

reliability, Microelectronics and Reliability, 33: 1963–1979.

Rushdi, A. M. & Alturki, A.M. 2015. Reliability of coherent threshold systems. Journal of Applied Science

(3): 431–443.

Rushdi, A. M. & Al-Yahya, 2001. , Derivation of the complete sum of a switching function with the aid

of the variable-entered Karnaugh map, Journal of King Saud University: Engineering Sciences, 13(2):

–269, 2001.

Rushdi, A. M. & Ba-Rukab O. M. 2005a. A doubly-stochastic fault-tree assessment of the probabilities of

security breaches in computer systems, Proceedings of the Second Saudi Science Conference, Part Four:

Computer, Mathematics, and Statistics, Jeddah, Saudi Arabia, pp. 1–17.

Rushdi, A. M. & Ba-Rukab O. M. 2005b. Fault-tree modelling of computer system security, International

Journal of Computer Mathematics, 82(7): 805–819.

Rushdi, A. M. & Ba-Rukab O. M. 2014. Map derivation of the closures for dependency and attribute sets

and all candidate keys for a relational Database, Journal of King Abdulaziz University: Engineering

Sciences, 25(2): 3–34

Rushdi, A. M. & Dehlawi, F. M.-A. 1988. Optimal computation of k-to-l-out-of-n system reliability,

Microelectron. Reliab., vol. 27, no. 5, pp. 875-896, 1987, Erratum : ibid, 28(4): 671.

Rushdi, A. M. & Ghaleb, F. A. 2014. The Walsh spectrum and the real transform of a switching function: A

review with a Karnaugh-map perspective, Journal of Engineering and Computer Sciences, Qassim University,

(2): 73–112.

Rushdi, A. M. & Goda, A. S. 1985. Symbolic reliability analysis via Shannon's expansion and statistical

independence, Microelectronics and Reliability, 25(6): 1041–1053.

Rushdi, A. M. & Hassan, A. K. 2015. Reliability of migration between habitat patches with heterogeneous

ecological corridors, Ecological Modelling, 304: 1-10.

Rushdi, A. M. & Hassan, A. K. 2016a. An exposition of system reliability analysis with an ecological perspective,

Ecological Indicators, 63: 282–295.

Rushdi, A. M. & Hassan, A. K. 2016b. Quantification of uncertainty in the reliability of migration between

habitat patches. Computational Ecology and Software, 6(3): 66–82.

Rushdi, A. M. & Rushdi, M. A. 2016. Switching-Algebraic Analysis of System Reliability. Chapter 6 in M.

Ram and P. Davim (Editors), Advances in Reliability and System Engineering, Management and Industrial

Engineering Series, Springer International Publishing, Cham, Switzerland, pp. 139-161.

Samaniego, F. J. 1985. On Closure of the IFR Class Under Formation of Coherent Systems. IEEE Transactions

on Reliability Theory, R-34: 69–72.

Samaniego, F. J. 2007. System Signatures and their Applications in Engineering Reliability, Springer

Science+Business Media, LLC, New York, NY,USA

Satyanarayana, A. & Prabhakar, A. 1978. A new topological formula and rapid algorithm for reliability

analysis of complex networks. IEEE Transactions on Reliability, R-30: 82–100.

Satyanarayana, A. & Chang, M. K. 1983. Network reliability and the factoring theorem. Networks, 13:

–120.

Scheuer, E. M. 1988. Reliability of an m-out of-n system when component failure induces higher failure rates

in survivors, IEEE Transctions on Reliability, 37(1): 73–74.

Shao, J. & Lamberson, L. R. 1991. Modeling a shared-load k-out-of-n: G system. IEEE Transactions on

Reliability, 40(2): 205–209.

Tian, Z., Zuo, M. J. & Yam, R. C. 2008. Multi-state k-out-of-n systems and their performance evaluation.

IIE Transactions, 41(1): 32–44.

Trivedi, K. S. 2002. Probability and Statistics with Reliability, Queuing, and Computer Science Applications,

nd Ed., Prentice-Hall, Englewood Cliffs, NJ, USA.

Wang, J., Ding, M. & Li, S. 2010. Reliability analysis of converter valves for VSC-HVDC power transmission

system. In 2010 IEEE Asia-Pacific Power and Energy Engineering Conference: 1–4.

Wu, J.-S. & Chen R.-J. 1994. An Algorithm for Computing the Reliability of Weighted-k-out-of-n Systems,

IEEE Transactions on Reliability, 43(2): 327–328.

Yamachi, H. & Yamamoto, H. 2006. Searching Pareto solutions of bi-objective NVP system design problem

with breadth first search method. In 5th IEEE/ACIS International Conference on Computer and Information

Science and 1st IEEE/ACIS International Workshop on Component-Based Software Engineering,

Software Architecture and Reuse (ICIS-COMSAR'06): 252–258.

Yinghui, T. & Jing, Z. 2008. New model for load-sharing k-out-of-n: G system with different components.

Journal of Systems Engineering and Electronics, 19(4), 748–751.

Zhegalov, S. I. 1986. A method of calculating the probability of failure-free operation of a system with

different elements, Soviet Journal of Computer Systems Sciences (Formerly, Engineering. Cybernetics),

(1): 147–149.

Zuo, M., Chiovelli, S. & Huang, J. 1999. Reliability evaluation of furnace systems. Reliability Engineering

& System Safety, 65(3): 283–287.


Refbacks

  • There are currently no refbacks.