Application of logical differential calculus and binary decision diagramin importance analysis

• Autorzy: Zaitseva E. , Levashenko V. , Kostolny J.

Warianty tytułu

PL

Zastosowanie logicznego rachunku różniczkowego oraz binarnego diagramu decyzyjnego w analizie ważności

• Języki publikacji: EN

Abstrakty

EN

System availability evaluation includes different aspects of system behaviour and one of them is the importance analysis. This analysis supposes the estimation of system component influence to system availability. There are different mathematical approaches to the development of this analysis. The structure function based approach is one of them. In this case system is presented in form of structure function that is defined the correlation of system availability and its components states. Structure function enables one to represent mathematically a system of any complexity. But computational complexity of structure function based methods is time consuming for large-scale system. Decision of this problem for the calculation of importance measures can be realized based on application of two mathematical approaches. One of them is Direct Partial Boolean Derivative. New equations for calculating the importance measures are obtained in terms of these derivatives. Other approach is Binary Decision Diagram (BDD), which supports efficient manipulation of Boolean algebra. In this paper new algorithms for calculating of importance measures by Direct Partial Boolean Derivative based on BDD are proposed. The experimental results of comparison these algorithms with other show the efficiency of new algorithms for calculating Direct Partial Boolean Derivative and importance measures.

PL

Ocena gotowości systemu, analiza czułości, miary ważności oraz optymalna konstrukcja to istotne zagadnienia, które stały się obiektem badań z zakresu inżynierii niezawodności. Istnieją różne podejścia matematyczne do owych problemów. Jednym z nich jest podejście oparte na funkcji struktury. Funkcja struktury umożliwia analizę systemów o wszelkim stopniu złożoności. Jednakże, w przypadku sieci o dużej skali, złożoność obliczeniowa metod opartych na funkcji struktury sprawia, że metody te są czasochłonne. W przedstawionej pracy proponujemy wykorzystanie dwóch metod matematycznych analizy ważności. Pierwszą z nich jest bezpośrednia cząstkowa pochodna boole'owska, w kategoriach której opracowano nowe równania do obliczania miar ważności. Drugą jest binarny diagram decyzyjny, który wspiera efektywną manipulację na wyrażeniach algebry Boole'a. W artykule zaproponowano dwa algorytmy służące do obliczania bezpośredniej cząstkowej pochodnej boole'owskiej w oparciu o binarny diagram decyzyjny funkcji struktury. Wyniki eksperymentów wykazują skuteczność nowo opracowanych algorytmów w obliczaniu bezpośredniej cząstkowej pochodnej boole'owskiej oraz miar ważności.

Słowa kluczowe

EN

decision diagram; importance analysis; logical differential calculus; reliability engineering

PL

diagram decyzyjny; analiza ważności; logiczny rachunek różniczkowy; inżynieria niezawodności

• Wydawca: Polskie Naukowo-Techniczne Towarzystwo Eksploatacyjne
• Czasopismo: Eksploatacja i Niezawodność
• Rocznik: 2015
• Tom: Vol. 17, no. 3
• Strony: 379--388
• Opis fizyczny: Bibliogr. 37 poz., rys., tab.

Twórcy

autor

Zaitseva E.

• Department of Informatics University of Zilina, Faculty of Management Science and Informatics Univerzitna 8215/1, 010 26 Zilina, Slovakia.

autor

Levashenko V.

• Department of Informatics University of Zilina, Faculty of Management Science and Informatics Univerzitna 8215/1, 010 26 Zilina, Slovakia.

autor

Kostolny J.

• Department of Informatics University of Zilina, Faculty of Management Science and Informatics Univerzitna 8215/1, 010 26 Zilina, Slovakia.

Bibliografia

• 1. Akers SB. Binary Decision Diagrams. IEEE Transaction on Computers 1978; 27: 509–16, http://dx.doi.org/10.1109/TC.1978.1675141.
• 2. Akers SB. On a Theory of Boolean Functions. Journal of the Society for Industrial and Applied Mathematics 1959; 7: 487–98, http://dx.doi.org/10.1137/0107041.
• 3. Armstrong MJ. Reliability-importance and dual failure-mode components. IEEE Transaction on Reliability 1997; 46: 212–21, http://dx.doi.org/10.1109/24.589949.
• 4. Barlow RE, Proschan F. Importance of system components and fault tree events. Stochastic Processes and their Applications 1975; 3: 153–73, http://dx.doi.org/10.1016/0304-4149(75)90013-7.
• 5. Beeson S, Andrews JD. Importance measures for noncoherent-system analysis. IEEE Transactions on Reliability 2003; 52: 301–10, http://dx.doi.org/10.1109/TR.2003.816397.
• 6. Birnbaum ZW. On importance of difference components in a multi-component system. Multi-Variant Anal 2 1969: 581–92.
• 7. Bochmann D, Posthoff C. Binäre dynamische Systeme. Berlin: Akademie-Verlag; 1981.
• 8. Borgonovo E. The reliability importance of components and prime implicants in coherent and non-coherent systems including total-order interactions. European Journal of Operational Research 2010; 204: 485–95, http://dx.doi.org/10.1016/j.ejor.2009.10.021.
• 9. Bryant RE. Graph-Based Algorithms for Boolean Function Manipulation. IEEE Transactions on Computers 1986; C-35: 677–91, http://dx.doi.org/10.1109/TC.1986.1676819.
• 10. Davio M., J.-P. Deschamps, A. Thayse, Discrete and switching functions. St. Saphorin, Switzerland: Georgi Pub. Co.; New York: McGraw-Hill International Book Co; 1978.
• 11. Duflot N, Bérenguer C, Dieulle L, Vasseur D. A min cut-set-wise truncation procedure for importance measures computation in probabilistic safety assessment. Reliability Engineering & System Safety 2009; 94: 1827–37, http://dx.doi.org/10.1016/j.ress.2009.05.015.
• 13. Gao X, Cui L, Li J. Analysis for joint importance of components in a coherent system. European Journal of Operational Research 2007; 182: 282–99, http://dx.doi.org/10.1016/j.ejor.2006.07.022.
• 14. Chang Y-R, Amari S V, Kuo S-Y. Computing system failure frequencies and reliability importance measures using OBDD. IEEE Transaction on Computers 2004; 53: 54–68, http://dx.doi.org/10.1109/TC.2004.1255790.
• 15. Chang Y-RY, Huang CY, Kuo S. Performance assessment and reliability analysis of dependable and distributed computing systems based on BDD and recursive merge. Applied Mathematics and Computation 2010; 217: 403–13, http://dx.doi.org/10.1016/j.amc.2010.05.075.
• 16. Changqian W, Chenghua W. A Method for Logic Circuit Test Generation Based on Boolean Partial Derivative and BDD. 2009 WRI World Congress on Computer Science and Information Engineering 2009; 3: 499–504, http://dx.doi.org/10.1109/CSIE.2009.44.
• 17. Jung WS, Han SH, Ha J. A fast BDD algorithm for large coherent fault trees analysis. Reliability Engineering & System Safety 2003; 83 (3): 369-374, http://dx.doi.org/10.1016/j.ress.2003.10.009
• 18. Kim Bjorkman, Solving dynamic flowgraph methodology models using binary decision diagrams, Reliability Engineering & System Safety, 2013; 111: 206-216, http://dx.doi.org/10.1016/j.ress.2012.11.009.
• 19. Kuo W, Zhu X. Importance Measures in Reliability, Risk, and Optimization. Chichester, UK: John Wiley & Sons, Ltd; 2012, http://dx.doi.org/10.1002/9781118314593.
• 20. Laboratory CB and EA. The Benchmark Archives at CBL 2013.
• 21. Liudong Xing, Akhilesh Shrestha, Yuanshun Dai, Exact combinatorial reliability analysis of dynamic systems with sequence-dependent failures, Reliability Engineering & System Safety 2011; 96 ( 10): 1375-1385, http://dx.doi.org/10.1016/j.ress.2011.05.007.
• 22. Liudong Xing, An Efficient Binary-Decision-Diagram-Based Approach for Network Reliability and Sensitivity Analysis, IEEE Transactions on System, Man and Cybernetics – Part A: System and Humans 2008; 38(1).
• 23. Liudong Xing, Gregory Levitin, BDD-based reliability evaluation of phased-mission systems with internal/external common-cause Reliability Engineering & System Safety 2013; 112:145-153, http://dx.doi.org/10.1016/j.ress.2012.12.003.
• 24. Moret BME, Thomason MG. Boolean Difference Techniques for Time-Sequence and Common-Cause Analysis of Fault-Trees. IEEE Transaction on Reliability 1984; R-33: 399–405, http://dx.doi.org/10.1109/TR.1984.5221879.
• 25. Nokland TE, Aven T. On selection of importance measures in risk and reliability analysis. International Journal of Performability Engineering 2013; 9: 133–47.
• 26. Posthoff C, Steinbach B. Logic Functions and Equations. Binary Models for Computer Science 2004, http://dx.doi.org/10.1007/978-1-4020-2938-7.
• 27. Rausand M, Hyland A, editors. System Reliability Theory. Hoboken, NJ, USA: John Wiley & Sons, Inc.; 1994, http://dx.doi.org/10.1002/9780470316900.
• 28. Rauzy A. Mathematical foundations of minimal cut sets. IEEE Transactions on Reliability 2001; 50: 389–96, http://dx.doi.org/10.1109/24.983400.
• 29. Ryabinin, IA. and Parfenov, YuM., Determination of "Weight" and "Importance" of Individual Elements at Reliability Estimation of a Complex System. Energetics Transport 1978, 6: 22–32.
• 30. Shmerko V, Lyshevski S, Yanushkevich S. Computer Arithmetics for Nanoelectronics. CRC Press 2009, http://dx.doi.org/10.1201/b15950.
• 31. Shumin Li, Shubin Si, Hongyan Dui, Zhiqiang Cai, Shudong Sun, A novel decision diagrams extension method, Reliability Engineering & System Safety 2014; 126: 107-115, http://dx.doi.org/10.1016/j.ress.2014.01.017.
• 32. Schneeweiss WG. A short Boolean derivation of mean failure frequency for any (also non-coherent) system. Reliability Engineering & System Safety 2009; 94: 1363–7, http://dx.doi.org/10.1016/j.ress.2008.12.001.
• 33. Talansev A. Analysis and synthesis of some electrical circuits by means of special logical operators. Automation and Remote Control 1959; 20; 898–907.
• 34. Tucker JH, Tapia MA, Bennett AW. Boolean Integral Calculus for Digital Systems. IEEE Transactions on Computers 1985; C-34; 78–81, http://dx.doi.org/10.1109/TC.1985.1676517.
• 35. Zaitseva E, Levashenko V. Multiple-Valued Logic mathematical approaches for multi-state system reliability analysis. Journal of Applied Logic 2013; 11: 350-362, http://dx.doi.org/10.1016/j.jal.2013.05.005.
• 36. Zaitseva E. Importance Analysis of a Multi-State System Based on Multiple-Valued Logic Methods. Recent Advances in System Reliability - Signatures, Multi-State System, Statistical Inference - Springer 2012; 113–34.
• 37. Zaitseva E., Levashenko V. Importance analysis by logical differential calculus. Automation and Remote Control - Springer 2013; 74: 171–82, http://dx.doi.org/10.1134/S000511791302001X.
• 38. Zaitseva E., Levashenko V., Kostolny J. Multi-State System Importance Analysis based on Direct Partial Logic Derivative. International Conference on Quality, Reliability, Risk, Maintenance and Safety Engineering 2012; 1514 – 1519, http://dx.doi.org/10.1109/ ICQR2MSE.2012.6246513.