臺灣博碩士論文加值系統

二十一世紀是一個知識爆炸且各類資訊能快速傳遞之時代。欲瞭解這些資訊的傳遞情況，可由現今在作業研究、資訊科學等相關網路議題進行探索，而目前又以供應鏈管理、交通運輸、電腦通訊及商品物流等網路流量之問題最為熱門。藉由以往在網路問題的相關研究內得知，需判斷某一網路系統是否優劣可透過系統可靠度進行分析，故系統可靠度在網路流量問題中扮演極重要之角色。然而，與系統可靠度相關之研究大多以確定型之流量網路系統作為探討對象，但實際生活中確定型流量網路系統卻是相當有限，反而隨機型流量網路系統較常發生於現實生活當中，如電腦網路系統、電子通訊系統等。另外，現今的社會環境對於資源有效分配與時間掌握非常重視，故隨機型流量網路系統往往會加入與資源或時間相關之限制元素（如：各邊 (edge)容量、總傳輸量、傳輸時間等），使該流量網路系統更符合現今各式流量網路之問題，以便人們更加了解問題本身，進而讓人們對於該問題找出對應之解決方案。
但上述流量網路問題中（如：最快路徑問題），目前並無一簡便之演算法可供人們使用（即搜尋符合限制條件之路徑）。絕大多數對於最快路徑問題之演算法乃需先求出所有MPs (minimal paths)後，再藉由最小容量的方式才得知該系統之所有可行路徑，進而求得此系統之可靠度，故本研究期望發展Binary Decision Diagram (BDD)為基之演算法 (The BDD-QP algorithm)，該演算法可直接求算出於隨機型流量網路中可將特定數量之資料在固定的限制時間內完整由起點傳送至終點的所有可行路徑。之後，只需計算此流量網路系統所有可行路徑中各邊 (edge)容量所對應之機率，即可得知該流量網路之系統可靠度，以作為後續了解此流量網路是否具穩定可靠之基礎。最後，本研究將以兩個實際範例說明此BDD-QP演算法，並評估其對應之系統可靠度。

Table of Contents

中文摘要 7
Abstract 8
Chapter 1－Introduction 9
1.1 Background and Motivation 9
1.2 Objectives 12
1.3 Organization of this thesis 12
Chapter 2－Literature Review 14
2.1 Multi-state flow network 14
2.1.1 Quickest Path Problem 16
2.2 Binary Decision Diagram (BDD) 18
Chapter 3－Definition & The BDD-QP algorithm 22
3.1 Definition 22
3.1.1 Acronyms 22
3.1.2 Notations 22
3.1.3 Nomenclature 24
3.1.4 Assumption 25
3.1.5 Lemmas and Theorems 25
3.2 The BDD-QP algorithm for Multi-state Flow Network Reliability 28
3.2.1 Pseudo code of the BDD-QP algorithm 28
3.3 The Complexity of the BDD-QP algorithm 29
Chapter 4－Illustrative Examples 31
4.1 An example for Quickest Paths in the MFN Reliability 31
4.2 An example for Quickest Paths in the MMFN Reliability 38
Chapter 5－Conclusions & Future Prospect 49
5.1 Conclusions 49
5.2 Future Prospect 49
Reference 51

[1] A. Rauzy. New algorithms for fault tree analysis. Reliability Engineering and System Safety, 40:203-211, 1993.
[2] B. Bolling, I. Wegener. Improving the variable ordering of OBDDs is NP-complete. IEEE Trans. Computer. vol 45, pp 993-1002, Sep. 1996.
[3] C. Meinel, T. Theobald, Algorithms and Data Structures in VLSI Design OBDD—Foundations and Applications, Springer, Berlin, 1998.
[4] Chen YL, Chin YH. The quickest path problem. Computers & Operations Research, 17:153-61, 1990.
[5] Chen YL. An algorithm for finding the k quickest paths in a network. Computers & Operations Research, 20:59-65, 1993.
[6] Chen YL. Finding the k quickest simples paths in a network. Information Processing Letters, 50:89-92, 1994.
[7] Chen GH, Hung YC. Algorithms for the constrained quickest path problem and the enumeration of quickest paths. Computers & Operations Research, 21:113-8, 1994.
[8] Chen GH, Hung YC. On the quickest path problem. Information Processing Letters, 46:125-8, 1993.
[9] Douglas R. Shier. Network reliability and Algebraic structures. Microelectronics Reliability, Volume 32, Issue 5, Page 745, May 1992.
[10] Gen-Huey Chen and Yung-Chen Hung. On the quickest path problem. Information Processing Letters 46, 125-128, 1993.
[11] Golden BL, Magnanti TL. Deterministic network optimization: a bibliography. Networks, 7:149-83, 1977.
[12] Herminia I. Calvete. The quickest path problem with interval lead times. Computers & Operations Research 31, 383-395, 2004.
[13] H. Singh, S. Vaithilingam, R. K. Anne and L. Anneberg. Terminal reliability using binary decision diagrams. Microelectron. Reliab, Vol. 36, No 3, pp 363-365, 1996.
[14] Hung YC, Chen GH. Distributed algorithms for the quickest path problem. Parallel Computing, 18:823-34, 1992.
[15] Henrik Reif Andersen. An Introduction to Binary Decision Diagrams. Lecture notes for 49285 Advanced Algorithms E97, October 1997.
[16] Hudson JC, Kapur KC. Reliability bounds for multistate systems with multistate components. Operations Research, 33:153-60, 1985.
[17] I. Wegener, Branching Programs and Binary Decision Diagrams, Monographs on Discrete Mathematics and Applications, SIAM, Philadelphia, PA, 2000.
[18] Jane CC, Lin JS, Yuan J. On reliability evaluation of a limited-flow network in terms of minimal cutsets. IEEE Transactions on Reliability 42:354-61, 1993.
[19] K. Brace, R. Rudell and R. Bryant. Efficient implementation of a BDD package. Proc. 27th ACM/IEEM Design Automation Conference, pages 40-45, 1990.
[20] Lin YK. Reliability evaluation of a revised stochastic-flow network with uncertain minimum time. Physica A 389, 1253-1258, 2010.
[21] Lin YK. Extend the quickest path problem to the system reliability evaluation for a stochastic-flow network. Computers & Operations Research 30, 567–575, 2003.
[22] Lin YK, Yuan J. A new algorithm to generate d-minimal paths in a multi-state flow network with non-integer arc capacities. International Journal of Reliability, Quality, and Safety Engineering, 5:269-85, 1998.
[23] Lin YK, Yuan J. Study on the multi-commodity transportation reliability by containers under budget constraint and probabilistic capacities. Journal of Chinese Institute of Industrial Engineers, 16:639-47, 1999.
[24] L.M. Bartlett, J.D. Andrews. An ordering heuristic to develop the binary decision diagram based on structural importance. Reliability Engineering and System Safety 72, 31-38, 2001.
[25] Lin JS, Jane CC, Yuan J. On reliability evaluation of a capacity-flow network in terms of minimal pathsets. Network 25:131-8, 1995.
[26] Lee DT, Papadopoulou E. The all-pairs quickest path problem. Information Processing Letters, 45:261-7, 1993.
[27] L.D. Bodin, B.L. Golden, A.A. Assad, M.O. Ball, Routing and scheduling of vehicles and crews: The state of the art, Computers & Operations Research 10, 63-211, 1982.
[28] Martins EDQV, Santos JLED. An algorithm for the quickest path problem. Operations Research Letters, 20:195-8, 1997.
[29] M.L. Fredman, R.E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of ACM 34, 596-615, 1987.
[30] M.H. Moore. On the fastest route for convoy-type traffic in flowrate-constrained networks. Transportation Science, 10:113-24, 1976.
[31] M. Bouissou. An ordering heuristic for building binary decision diagrams from fault-trees. Proc. 1996 Annual Reliability and Maintainability Symposium, pp 208-214, 1996.
[32] O. Coudert and J.C. Madre. Metaprime: An interactive fault-tree analyzer. IEEE Transactions on Reliability, 43(1):121-127, 1994.
[33] Randal E. Bryant. Graph-Based Algorithms for Boolean Function Manipulation. IEEE Transactions on Computers, C-35-8, pp 677-691, August, 1986.
[34] Randal E. Bryant, Symbolic boolean manipulation with ordered binary-decision diagrams, ACM Computer. Surveys 24 (3) 293-318, 1992.
[35] Rosen JB, Sun SZ, Xue GL. Algorithms for the quickest path problem and the enumeration of quickest paths. Computers & Operations Research, 18:579-84, 1991.
[36] R.K. Ahuja, Minimum cost-reliability ratio problem, Computers & Operations Research 16, 83-89, 1998.
[37] R.M. Sinnamon and J.D. Andrews. Improved accuracy in quantitative fault tree analysis. Quality and Reliability Engineering International, 13:285-292, 1997.
[38] R.M. Sinnamon and J.D. Andrews. Improved efficiency in quantitative fault tree analysis. Quality and Reliability Engineering International, 13:293-298, 1997.
[39] Sheldon B. Akers, Fellow, IEEE. Binary Decision Diagrams. IEEE Transactions on Computers. Vol. c-27, No. 6, June 1978.
[40] S.A. Doyle and J.B. Dugan. Dependability assessment using binary decision diagrams. Proc. 25th International Symposium on Fault-Tolerant Computing, pages 249-258, 1995.
[41] Xinyu Zang, Hairong Sun and Kishor S. Trivedi. A BDD-Based Algorithm for Reliability Graph Analysis. National Science Foundation under Grant No. EEC 9418765, February, 2000.
[42] Yeh WC. A revised layered-network algorithm to search for all d-Minpaths of a limited-flow acyclic network. IEEE Transactions on Reliability, 47:436–42, 1998.
[43] Yeh WC. A simple algorithm to search for all d-MPs with unreliable nodes. Reliability Engineering & System Safety, 73:49–54, 2001.
[44] Yeh WC. Search for minimal paths in modified networks. Reliability Engineering & System Safety, Volume 75, Issue 3, Pages 389-395, March 2002.
[45] Yeh WC. A new approach to evaluate reliability of multistate networks under the cost constraint. Omega, Volume 33, Issue 3, Pages 203-209, June 2005.
[46] Yeh WC. Multistate network reliability evaluation under the maintenance cost constraint. International Journal of Production Economics, Volume 88, Issue 1, 8, Pages 73-83, March 2004.
[47] Y.H. Kim, K.E. Case, and P.M. Ghare. A method for computing complex system reliability. IEEE Transaction on Reliability, R-21:215-219, 1972.
[48] Yasuhiko Takenaga, Shuzo Yajima. Hardness of identifying the minimum ordered binary decision diagram. Discrete Applied Mathematics 107, 191-201, 2000.
[49] Yarlagadda R, Hershey J. Fast algorithm for computing the reliability of communication network. International Journal of Electronics, 70:549-64, 1991.
[50] 林順喜、魏君任. BDD最小化問題之改良演算法. Department of Computer Science and Information Engineering, 2006