An efficient algorithm for exact computation of system and survival signatures using binary decision diagrams
System and survival signatures are important and popular tools for studying and analysing the reliability of systems. However, it is difficult to compute these signatures for systems with complex reliability structure functions and large numbers of components. This paper presents a new algorithm tha...
| Main Author: | |
|---|---|
| Format: | Article |
| Published: |
Elsevier
2017
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/42221/ |
| _version_ | 1848796447531597824 |
|---|---|
| author | Reed, Sean |
| author_facet | Reed, Sean |
| author_sort | Reed, Sean |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | System and survival signatures are important and popular tools for studying and analysing the reliability of systems. However, it is difficult to compute these signatures for systems with complex reliability structure functions and large numbers of components. This paper presents a new algorithm that is able to compute exact signatures for systems that are far more complex than is feasible using existing approaches. This is based on the use of reduced order binary decision diagrams (ROBDDs), multidimensional arrays and the dynamic programming paradigm. Results comparing the computational efficiency of deriving signatures for some example systems (including complex benchmark systems from the literature) using the new algorithm and a comparison enumerative algorithm are presented and demonstrate a significant reduction in computation time and improvement in scalability with increasing system complexity. |
| first_indexed | 2025-11-14T19:48:08Z |
| format | Article |
| id | nottingham-42221 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:48:08Z |
| publishDate | 2017 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-422212020-05-04T18:41:22Z https://eprints.nottingham.ac.uk/42221/ An efficient algorithm for exact computation of system and survival signatures using binary decision diagrams Reed, Sean System and survival signatures are important and popular tools for studying and analysing the reliability of systems. However, it is difficult to compute these signatures for systems with complex reliability structure functions and large numbers of components. This paper presents a new algorithm that is able to compute exact signatures for systems that are far more complex than is feasible using existing approaches. This is based on the use of reduced order binary decision diagrams (ROBDDs), multidimensional arrays and the dynamic programming paradigm. Results comparing the computational efficiency of deriving signatures for some example systems (including complex benchmark systems from the literature) using the new algorithm and a comparison enumerative algorithm are presented and demonstrate a significant reduction in computation time and improvement in scalability with increasing system complexity. Elsevier 2017-04-09 Article PeerReviewed Reed, Sean (2017) An efficient algorithm for exact computation of system and survival signatures using binary decision diagrams. Reliability Engineering & System Safety, 165 . pp. 257-267. ISSN 0951-8320 System signature; Survival signature; Binary decision diagram; System reliability http://www.sciencedirect.com/science/article/pii/S095183201630120X doi:10.1016/j.ress.2017.03.036 doi:10.1016/j.ress.2017.03.036 |
| spellingShingle | System signature; Survival signature; Binary decision diagram; System reliability Reed, Sean An efficient algorithm for exact computation of system and survival signatures using binary decision diagrams |
| title | An efficient algorithm for exact computation of system and survival signatures using binary decision diagrams |
| title_full | An efficient algorithm for exact computation of system and survival signatures using binary decision diagrams |
| title_fullStr | An efficient algorithm for exact computation of system and survival signatures using binary decision diagrams |
| title_full_unstemmed | An efficient algorithm for exact computation of system and survival signatures using binary decision diagrams |
| title_short | An efficient algorithm for exact computation of system and survival signatures using binary decision diagrams |
| title_sort | efficient algorithm for exact computation of system and survival signatures using binary decision diagrams |
| topic | System signature; Survival signature; Binary decision diagram; System reliability |
| url | https://eprints.nottingham.ac.uk/42221/ https://eprints.nottingham.ac.uk/42221/ https://eprints.nottingham.ac.uk/42221/ |