連續k系統之可靠度演算法

Abstract

可靠度演算法是可靠度分析與可靠度最佳化等研究領域中很有用的工具。在本論文中，我們對許多系統進行可靠度分析，並設計出快速而有效率的可靠度演算法。我們研究的系統包括：n中連續k系統、n中加權連續k系統、n中連續k或f系統、n中連續k包含f系統、n中連續k網路系統、n中連續k流量網路系統、n中連續k, r雙故障模式系統，還有其他許多不具備『連續k』特性的系統。我們使用兩種通用的方法來設計可靠度演算法：第一種通用方法是遞迴方程式法，第二種方法是馬可夫鍊法。透過精心設計的遞迴方程式與異質馬可夫鍊，加上計算理論、自動機理論、與稀疏矩陣資料結構的輔助，我們提出來的許多可靠度演算法都比以前文獻上的演算法更簡單更有效率。 後來，我們又覺得每次面對一個系統就要個別去設計一種可靠度演算法非常辛苦，為了一勞永逸，我們便提出了『正規可靠度模型』。這個模型並不是一個系統，而是可以用來描述各種系統結構的工具，同時被描述的系統也不再需要有『連續k』特性。分析可靠度時只要使用這個模型先把系統結構描述出來，然後運用自動機理論找出最少狀態的異質馬可夫鍊，再配合稀疏矩陣資料結構就可以得到非常有效率的可靠度演算法。

Reliability algorithms are useful tools in reliability analyses and reliability optimizations. In this dissertation, we study and design efficient reliability algorithms for consecutive-k-out-of-n:F systems, weighted-consecutive-k-out-of-n:F systems, f-or-consecutive-k-out-of-n:F systems, f-within-consecutive-k-out-of-n:F systems, consecutive-k-out-of-n:F networks, consecutive-k-out-of-n:F flow networks, consecutive-k-r-out-of-n:DFM systems, and other reliability systems which do not have the “consecutive-k” property. We use two general approaches to develop our reliability algorithms: the first is the recursive equation approach, and second is the Markov chain approach. By carefully designed recursive equations and heterogeneous Markov chains, and under the supports of computation theory, automata theory, and sparse matrix data structures, our reliability algorithms are simpler and (or) more efficient than other published corresponding ones. In addition, we think that designing reliability algorithms case by case is a messy work. Therefore, we propose a “regular reliability model”. It is not a system, but a tool to specify the structures of various systems which may not have the “consecutive-k” property. When analyzing the reliability of a system, we first specify the system structure with the regular reliability model, and apply the automata theory to derive a minimal state heterogeneous Markov chain, then an efficient reliability algorithm can be obtained by implementing the Markov chain approach with the sparse matrix data structure. English Abstract ii Acknowledgements iii Contents iv 1. Introduction 1 1.1 Historical background 1 1.2 The problems and the methodologies 3 1.3 Outline of this dissertation 4 2. The consecutive-k-out-of-n:F system 6 2.1 Assumptions and notation 8 2.2 The linear consecutive-k-out-of-n:F system 10 2.2.1 Shanthikumar’s O(nk) time algorithm 11 2.2.2 Hwang’s O(n) time algorithm 12 2.2.3 A linear component replacement algorithm 13 2.3 The circular consecutive-k-out-of-n:F system 16 2.3.1 Hwang’s O(nk2) time algorithm 17 2.3.2 Antonopoulou and Papastavridis’s O(n2k) time algorithm 18 2.3.3 Wu and Chen’s O(nk) time algorithm 19 2.3.4 Hwang’s O(nk) time algorithm 20 2.3.5 Wu and Chen’s second O(nk) time algorithm 21 2.3.6 A simpler O(nk) time algorithm 22 2.3.7 A circular component replacement algorithm 25 3. The weighted-consecutive-k-out-of-n:F system 30 3.1 Assumptions and notation 32 3.2 The linear weighted-consecutive-k-out-of-n:F system 34 3.2.1 Wu and Chen’s O(n) time algorithm 35 3.3 The circular weighted-consecutive-k-out-of-n:F system 37 3.3.1 Wu and Chen’s incomplete O(min{n, k}·n) time algorithm 38 3.3.2 An O(Tn) time algorithm 41 4. The f-or-consecutive-k-out-of-n:F system ……………………………...…… 46 4.1 Assumptions and notation 47 4.2 Chang, Cui and Hwang’s O(f2k2n) time algorithm 49 4.3 An O(fkn) time algorithm 52 4.4 Another O(fkn) time algorithm 53 4.5 An O((f□k)kn) time algorithm 55 5. The f-within-consecutive-k-out-of-n:F system 59 5.1 Assumptions and notation 61 5.2 Hwang and Wright’s O(23kn) time algorithm 62 5.3 An O( n) time algorithm 64 6. The consecutive-k-out-of-n:F network 76 6.1 Assumptions and notation 78 6.2 Chen, Hwang and Li’s algorithm for k = 2 80 6.3 An O(2kn) time algorithm 83 7. The consecutive-k-out-of-n:F flow network 91 7.1 Assumptions and notation 92 7.2 An O( n) time f-flow-reliability algorithm 93 7.3 An O(k) time on-line routing algorithm 96 8. The consecutive-k-r-out-of-n:DFM system 99 8.1 Assumptions and notation 101 8.2 Koutras’s O((k+r)n) time algorithm 102 8.3 An O((k+r)n) time algorithm 103 8.4 An O(n) time algorithm 108 9. The regular reliability model 111 9.1 The regular reliability model 113 9.2 The F reliability model and the G reliability model 115 9.3 The relations among F models, G models, and regular models 118 9.4 An efficient reliability algorithm for the regular model 120 9.5 Applications 121 9.5.1 The f-or-consecutive-k:F model 121 9.5.2 The f-within-consecutive-k:F model 123 9.5.3 The k-mod-q model 125 9.5.4 Logic circuits 126 10. Conclusions 128 Bibliography 130 Vita 141 Publications 143