臺灣博碩士論文加值系統

本論文研究在 k-out-of-n 系統及 K 端點網路上之可靠度分析。從
1981 年起，在 k-out-of-n 系統上可靠度的研究，有三大系統被廣泛地
討論： (1) k-out-of-n:G 系統，(2) 連續 k-out-of-n:F系統，及 (3)
環形連續 k-out-of-n:F 系統。在本論文中，我們提出一個更一般化的模
組：權重 k-out-of-n 系統，產生在以下三個系統上之可靠度評估問題
： (1) 權重 k-out-of-n:G系統，(2) 連續權重 k-out-of-n:F系統，
及(3) 環形連續權重 k-out-of-n:F系統。我們設計出有效率的演算法來
計算這三個系統可靠度，並且得到和原來系統的演算法相同的時間複雜度
。在 K 端點網路上之可靠度的分析，早期的研究只考慮邊線會折損而結
點不會折損的新模組。在本論文中，我們提出一個邊線和結點均會折損的
新模組。並且設計出有一個可利用多邊形行程鏈形化簡法的演算法，來計
算當邊線和結點均折損時， K 端點網路上的可靠度。

In this dissertation, we study reliability analyses on both k-
out-of-n systems and K-terminals networks. For k-out-of-n
systems, computing reliabilities of k-out-of-n:G system,
consecutive-k-out-of-n:F system, and circular-consecutive-out-
of-n:F system has been widely discussed since 1981. Here, we
propose a more general model of :weighted k-out-of-n systems,
which lead to new reliability evaluation problems on three
systems: (1) weighted-k-out-of-n:G system, (2) consecutive-
weighted-k-out-of-n:F system, and (3) circular consecutive-
weighted-k-out-of-n:F system. To compute these system
reliabilities, we design efficient algorithms with the same
time complexities as the algorithms for the original model. For
K-terminal networks reliability, the early studies consider
that only edges may fail while vertices always function. In
this dissertation, we propose a new model: both edges and
vertices may fail. An algorithm using polygon-to-chain
reductions is constructed for computing the K-terminal networks
reliability with both edge and vertex failures.

Covers
Chinese Abstract
English Abstract
Acknowledgements
Contents
List of Figures
1 Introduction
1.1 Definitions
1.2 History
1.3 Outline of the Dissertation
2 Original k-out-of-n:G Systems
2.1 Introduction
2.2 Assumptions and Notation
2.3 k-out-of-n:G Systems
2.3.1 MaGrady''s Exponential Algorithm
2.3.2 Barlow and Heidtmann''s o(n2)Algorithm
2.3.3 Sarje and Prasd''so(nk)Algorithm
2.4 Consecutive-k-out-of-n:F Systems
2.4.1 Shanthikumar''so(nk)Algorithm
2.4.2 Hwang''s o(n)Algorithm
2.5 Circular Consecutive-k-out-of-n:F Systems
2.5.1 Hwang''so(nk2)Algorithm
2.5.2 Antonopoulou and Papastarvidis''s o(n2k)Algorithm
2.5.3 Our o(nk)Algorithm
2.5.4 Hwang''s o(nk)Algorithm
2.5.5 Our Another o(nk)Algorithm
3 Weighted k-out-of-n Systems
3.1 Introduction
3.2 Assumptions and Notation
3.3 Weighted-k-out-of-n:G Systems
3.3.1 An O(nk)Algorithm
3.3.2 An Example System
3.4 Consecutive-weighted-k-out-of-n:F Systems
3.4.1 An o(n)Algorithm
3.4.2 An System Example
3.5 Circular Consecutive-weighted-k-out-of-n:F Systems
3.5.1 An o(n.min(n,k)) Algorithm
4 K-terminal Networks Reliability
4.1 Introduction
4.2 Assumptions and Notation
4.3 A Factoring Algorithm
4.4 Reductions Methods
4.4.1 Parallel Reduction Method
4.4.2 Degree-1 Reduction Method
4.4.3 Degree-2 Reduction Method
4.4 Polygon-to-chain Reduction Methods
4.5 An Example Network
5 Conclusions
Bibliography
Vita
Publications List