(3.230.143.40) 您好!臺灣時間:2021/04/23 17:39
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:張晉嘉
研究生(外文):Chin-Chia Chang
論文名稱:應用蒙地卡羅演算法評估在時間限制下交集路徑之系統可靠度
論文名稱(外文):Study on system reliability for joint minimal paths under time constraint using Monte Carlo based algorithm
指導教授:林義貴林義貴引用關係
指導教授(外文):Yi-Kuei Lin
口試委員:林義貴
口試日期:2012-05-15
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:工業管理系
學門:商業及管理學門
學類:其他商業及管理學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:英文
論文頁數:70
中文關鍵詞:相交最小路徑蒙地卡羅模擬多階狀態網路時間限制阻塞現象
外文關鍵詞:Joint minimal pathsMonte Carlo Simulationmultistate flow networktime constraintcongestion
相關次數:
  • 被引用被引用:1
  • 點閱點閱:170
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:28
  • 收藏至我的研究室書目清單書目收藏:0
大部分的真實系統例如:電腦系統、電力系統、以及運籌系統等,皆可以被良好地建模成一個多階狀態流量網路。對於這類型的網路,系統可靠度是一個重要的績效衡量指標。在這篇論文中兩種不同版本的多階狀態最快路徑問題(multistate quickest path problem)被研究,從中我們發展出各自的蒙地卡羅演算法來評估系統可靠度。在過去的研究,多階狀態最快路徑問題的演算法已經被發展,但這些演算法都假設負責傳輸資料的最小路徑(minimal paths)彼此之間是不相交的(disjoint)。但這樣的假設似乎不太合理,因此我們所專注的兩個版本的多階狀態最快路徑問題皆不需要額外假設所使用的最小路徑是彼此不相交的。在最小路徑彼此相交(joint)的情形下,阻塞的現象(congestion phenomenon)可能會發生在傳輸的過程中,這是主要的麻煩所在。到目前為止,不論是分析的方法或數學手法都難以處理這樣的現象。
在提出的蒙地卡羅演算法中的每一次運行(run),一旦發現無法透過分析方法來求算資料的總傳輸時間,則應用一系列方程式來計算不同時間點的資料流分布(distribution of data flow)。直到最後一次運行完成,透過成功次數除以運行次數,近似的系統可靠度值被求得。由於所得到結果是近似值,因此,如何去論證我們所求得的近似系統可靠度值的可信度和加快演算法的演算效率變得十分重要。透過假設檢定來檢定近似值與精確值的差異是否為零以及建立其信賴區間,近似系統可靠度值的可信度被進一步證實。此外,演算法的演算效率是如何被運行次數、給定的資料量和時間限制影響也被進一步呈現在內文中。
The real system such as a computer system, an electric power system, or a logistics system can be modeled as a well-defined multistate flow network. In such a network, system reliability is an important performance index. In this thesis two variants of multistate quickest path problem (MQPP) are studied. We develop separate Monte Carlo based algorithms for evaluating the system reliability. In past studies, the algorithms have already been developed for MQPP assuming that minimal paths (MPs) being responsible for transmitting data are disjoint each other. This assumption seems unreasonable, and thus both two variants of MQPP we focus on do not assume that the assigned MPs are disjoint. In joint MPs, the main challenge is that a congestion phenomenon may happen in transmission process. No matter analytical approaches or mathematical means are difficult to deal with this phenomenon.
For each run the proposed Monte Carlo based algorithms apply a series of equations to compute distribution of data flow at different points in time once no analytical approaches can be utilized to calculate the transmission time. Until the final run, the approximate system reliability is obtained by number of success divided by number of runs. Owing to the result being an approximate value, and thus how to demonstrate the credibility of approximate system reliability and speed up the efficiency of algorithm are taken into account. Through doing hypothesis testing and building up the confidence interval, the credibility of the approximate values is verified. Furthermore, how the computation time of algorithm is influenced by number of runs, amount of data and time constraint are also displayed.
摘要 I
ABSTRACT II
ACKNOWLEDGMENTS III
CONTENT IV
LIST OF FIGURES VI
LIST OF TABLES VII
CHAPTER 1 INTRODUCTION 1
1.1 Background and motivation 1
1.2 Research objectives 2
1.3 Overview of this thesis 3
CHAPTER 2 LITERATURE REVIEW 5
2.1 System reliability analysis 5
2.2 Monte Carlo Methods 7
CHAPTER 3 PROBLEM MODELING AND DEVELOPMENT OF ALGORITHM 10
3.1 Model building for Model I 10
3.2 Simplification of network 13
3.3 System state 14
3.4 Simulation for distribution of data flow 15
3.4.1 Data assignment on minimal paths 16
3.4.2 Data at different positions 17
3.4.3 Equations for implementing simulation 18
A. Simulation in data buffer 18
B. Simulation at nodes 19
C. Simulation on arcs 20
3.5 The algorithm I for Model I 21
CHAPTER 4 EXTENSION OF MQPP 24
4.1 Model building for Model II 24
4.1.1 Spare routing policy 25
4.1.2 Budget limit 25
4.2 The algorithm II for Model II 26
CHAPTER 5 EXPERIMENT PROCEDURES AND RESULTS 29
5.1 An illustrative example to the algorithm II 29
5.2 The credibility of approximate system reliability 35
5.3 Discussion of algorithm efficiency 39
5.4 The algorithmic credibility in a large network 47
CHAPTER 6 CONCLUSIONS AND FUTURE RESEARCH 52
6.1 Conclusions 52
6.2 Future researches 53
REFERENCES 55
Ahrens, J. H., and Dieter, U., “Computer methods for sampling from the exponential and normal distributions”, Communications of the ACM, Vol. 15, Issue 10, pp. 873-882 (1972).
Ahrens, J. H., and Dieter, U., “Computer methods for sampling from the gamma, beta, poisson, and Binomial distributions”, Computing, Vol. 12, pp. 223-246 (1974).
Aven, T., “Reliability evaluation of multistate systems with multistate components”, IEEE Transactions on Reliability, Vol. 34, pp. 473-479 (1985).
Ahuja, R. K., “Minimum cost-reliability ratio path problem”, Computers and Operations Research, Vol. 15, pp. 83-89 (1998).
Ball, M. O., “Computing network reliability”, Operations Research, Vol. 27, pp. 823-838 (1979).
Bodin, L. D., Golden, B. L., Assad, A. A., and Ball, M. O., “Routing and scheduling of vehicles and crews: the state of the art”, Computers and Operations Research, Vol. 10, pp. 63-211 (1983).
Ball, M. O., Hagstrom, J., and Provan, J. S., “Threshold reliability of networks with small failure sets”, Networks, Vol. 25, pp. 101-115 (1995).
Bucklew J. A., Introduction to Rare Event Simulation, Springer, New York (2004).
Coveyou, R., and MacPherson, R.D.R., “Fourier analysis of uniform random number generators”, Journal of the Association for Computing Machinery, Vol. 14, Issue 1, pp. 100-119 (1967).
Colbourn, C. J., The Combinatorics of Network Reliability, Oxford University, New York (1987).
Chen, Y. L., and Chin, Y. H., “The quickest path problem”, Computers & Operations Research, Vol. 17, pp. 153-161 (1990).
Chen, Y. L., “An algorithm for finding the k quickest paths in a network”, Computers & Operations Research, Vol. 20, pp. 59-65 (1993).
Chen, Y. L., “Finding the k quickest simple paths in a network”, Information Processing Letters Vol. 50, pp. 89-92 (1994).
Chen, G. H., and Hung, Y. C., “On the quickest path problem”, Information Processing Letters, Vol. 46, pp. 125-128 (1993).
Chen, G. H., and Hung, Y. C., “Algorithms for the constrained quickest path problem and the enumeration of quickest paths”, Computers & Operations Research, Vol. 21, pp. 113-118 (1994).
Doullize, P., and Jamoulle, E., “Transportation networks with random arc capacities”, RAIRO, Vol. 3, pp.45-60 (1972).
Devroye, L., Non-Uniform Random Variable Generation, Springer, New York (1986).
Esary, J. D., and Proschan F., “Coherent structures of non-identical components”, Technometrics, Vol. 5, pp. 191-209 (1966).
Ford, L. R., and Fulkerson, D. R., Flows in networks, Princeton University, NJ (1962).
Fishman, G. S., “A Monte Carlo sampling plan for estimating network reliability”, Operation Research, Vol. 34, pp. 581-594 (1986a).
Fishman, G. S., “A comparison of four Monte Carlo methods for estimating the probability of s-t connectedness”, IEEE Transactions on Reliability, Vol. 35 pp. 145-155 (1986b).
Fredman, M. L., Tarjan, R. E., “Fibonacci heaps and their uses in improved network optimization algorithms”, Journal of the ACM, Vol. 34, pp. 596-615 (1987).
Golden, B. L., and Magnanti, T. L., “Deterministic network optimization: a bibliography”, Networks, Vol. 7, pp. 149-183 (1977).
Glasserman P., Monte Carlo methods in financial engineering, Springer, New York (2004).
Hudson, J. C., and Kapur, K. C., “Reliability bounds for multistate systems with multistate components”, Operations Research, Vol. 33, pp. 153-160 (1985).
Hung, Y. C., and Chen, G. H., “Distributed algorithms for the quickest path problem”, Parallel Computing, Vol. 18, pp. 823-834 (1992).
Hsieh, C. C. and Lin, M. H., “Reliability-oriented multi-resource allocation in a stochastic-flow network”, Reliability Engineering and System Safety, Vol. 81, pp. 155-161 (2003).
Hsieh, C. C. and Chen, Y. T., “Reliable and economic resource allocation in an unreliable flow network”, Computer and Operations Research, Vol. 32, pp. 613-628 (2005a).
Hsieh, C. C. and Chen, Y. T., “Resource allocation decisions under various demands and cost requirements in an unreliable flow network”, Computer and Operations Research, Vol. 32, pp. 2771-2784 (2005b).
Jane, C. C., Lin, J. S., and Yuan, J., “On reliability evaluation of a limited-flow network in terms of minimal cutsets”, IEEE Transactions on Reliability, Vol. 42, pp. 354-361 (1993).
Jane, C. C., and Yuan, J., “A sum of disjoint products algorithm for reliability evaluation of flow networks”, European Journal of Operational Research, Vol. 131, pp. 664-675 (2001).
Jane, C. C., and Laih, Y. W., “Algorithm to determine the threshold reliability of flow networks”, IIE Transactions, Vol. 36, pp. 46-479 (2004).
Kumamoto, H., Tanaka, K., Inoue, K., and Henley, E. J., “Dagger-sampling Monte Carlo for system unavailability evaluation”, IEEE Transactions on Reliability, Vol. R-29, pp. 122-125 (1980).
Karp, R., and Luby, M. G., “A new Monte Carlo method for estimating the failure probability of an n-component system”, Computer Science Division, University of California, Berkeley (1983).
Kuo, S., Lu, S., and Yeh, F., “Determining terminal pair reliability based on edge expansion diagrams using OBDD”, IEEE Transactions on Reliability, Vol. 48, pp. 234-246 (1999).
Kleijnen, J. P. C., Ridder, A. A. N., and Rubinstein, R.Y., Variance Reduction Techniques in Monte Carlo Methods, Encyclopedia of Operations Research and Management Sciences, third edition (by Gass, S and M. Fu), Kluwer (2011).
Lee, D. T., and Papadopoulou, E., “The all-pairs quickest path problem”, Information Processing Letters, Vol. 45, pp. 261-267 (1993).
Lin, J. S., Jane, C. C. and Yuan, J., “On reliability evaluation of a capacitated-flow network in terms of minimal pathsets”, Networks, Vol. 25, pp. 131-138 (1995).
Lin, Y. K., and Yuan, J., “A new algorithm to generate d-minimal paths in a multistate flow network with noninteger arc capacities”, International Journal of Reliability, Quality, and Safety Engineering, Vol. 5, pp. 269-285 (1998).
Lin, Y. K., and Yuan, J., “Study on the multicommodity transportation reliability by containers under budget constraint and probabilistic capacities”, Journal of Chinese Institute of Industrial Engineers Vol. 16 pp. 639-647 (1999).
Lin, Y. K., “A simple algorithm for reliability evaluation of a stochastic-flow network with node failure”, Computers & Operations Research, Vol. 28, pp. 1277-1285 (2001a).
Lin, Y. K., “On reliability evaluation of a stochastic-flow network in terms of minimal cuts”, Journal of Chinese Institute of Industrial Engineers, Vol. 18, pp. 49-54 (2001b).
Lin, Y. K., “Using minimal cuts to evaluate the system reliability of a stochastic-flow network with failures at nodes and arcs”, Reliability Engineering and System Safety, Vol. 75, pp. 41-46 (2002).
Lin, Y. K., “Extend the quickest path problem to the system reliability evaluation for a stochastic-flow network”, Computers & Operations Research, Vol. 30, pp. 567-575 (2003).
Lin, Y. K., “Reliability of a stochastic-flow network with unreliable branches and nodes under budget constraints”, IEEE Transactions on Reliability, Vol. 53, pp. 381-387 (2004).
Lin, Y. K., “Reliability evaluation for an information network with node failure under cost constraint”, IEEE Transactions on Systems, Man and Cybernetics – Part A: Systems and Humans, Vol. 37, pp. 180-188 (2007a).
Lin, Y. K., “On a multicommodity stochastic-flow network with unreliable nodes subject to budget constraint”, European Journal of Operational Research, Vol. 176, pp. 347-360 (2007b).
Lin, Y. K., “System reliability of a stochastic-flow network through two minimal paths under time threshold”, International Journal of Production Economics, Vol. 124, pp. 382-387 (2010a).
Lin, Y. K., “Spare Routing Reliability for a Stochastic Flow Network Through Two Minimal Paths Under Budget Constraint”, IEEE Transactions on Reliability, Vol. 59, pp. 2-10 (2010b).
Lin, Y. K., “Transmission reliability of k minimal paths within time threshold”, Computers & Industrial Engineering, Vol. 61, pp. 1160-1165 (2011a).
Lin, Y. K., “Stochastic flow networks via multiple paths under time threshold and budget constraint”, Computers & Mathematics with Applications, Vol. 62, pp. 2629-2638 (2011b).
Lin, Y. K., “Spare routing problem with p minimal paths for time-based stochastic flow networks”, Applied Mathematical Modelling, Vol. 35, pp. 1427-1438 (2011c)
Liu, Q., Zhang, H., Ma, X., and Zhao, Q., “Genetic algorithm-based study on flow allocation in a multi-commodity stochastic-flow network with unreliable nodes”, Proceedings of The 8th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, Tsinan, pp. 576-581 (2007).
Liu, Q., Zhao, Q., and Zang, W., “Study on multi-objective optimization of flow allocation in a multi-commodity stochastic-flow network with unreliable nodes”, Journal of Applied Mathematics and Computing, Vol. 28, pp. 185-198 (2008).
Lin, Y. K., and Yeh, C. T., “Evaluation of Optimal Network Reliability Under Components-Assignments Subject to a Transmission Budget”, IEEE Transactions on Reliability, Vol. 59, pp. 539-550 (2010).
Lin, Y. K., and Yeh, C. T., “Using minimal cuts to optimize network reliability for a stochastic computer subject to assignment budget”, Computers and Operations Research, Vol. 38, pp. 1175-1187 (2011a).
Lin, Y. K., and Yeh, C. T., “Computer network reliability optimization under double-resource assignments subject to a transmission budget”, Information Sciences, Vol. 181, pp. 582-599 (2011b).
Lin, Y. K., and Yeh, C. T., “Determining the optimal double-component assignment for a stochastic computer network”, Omega, Vol. 40, pp. 120-130 (2012).
Lin, C. H., and Yang, W. N., “A simple and efficient importance sampling scheme for stochastic network unreliability estimation”, Simulation Modelling Practice and Theory, Vol. 19, pp. 924-935 (2011).
Metropolis, N., and Ulam, S., “The Monte Carlo method”, Journal of the American Statistical Association, Vol. 44, Issue 247, pp. 335-341 (1949).
Martins, E. D. Q. V., and Santos, J. L. E. D., “An algorithm for the quickest path problem”, Operations Research Letters, Vol. 20, pp. 195-198 (1997).
Provan, J. S., and Ball, M. O., “Computing network reliability in time polynomial in the number of cuts”, Operations Research, Vol. 32, pp. 516-526 (1984).
Rueger, W. J., “Reliability analysis of networks with capacity constraints and failure at branches & nodes”, IEEE Transactions on Reliability, Vol. 35, pp. 523-528 (1986).
Rosen, J. B., Sun, S. Z., and Xue, G. L., “Algorithms for the quickest path problem and the quickest paths”, Computers & Operations Research, Vol. 18, pp. 579-584 (1991).
Ramirez-Marquez, J. E., and Coit, D. W., “A monte-carlo simulation approach for approximating multi-state two-terminal reliability”, Reliability Engineering and System Safety, Vol. 87, pp. 253-264 (2005).
Soh, S., and Rai, S., “An efficient cuset approach for evaluating communication-network reliability with heterogeneous link-capacities”, IEEE Transactions on Reliability, Vol. 54, pp. 133-144 (2005).
Xue, J., “On multistate system analysis”, IEEE Transactions on Reliability, Vol. 34, pp. 329-337 (1985).
Xu, W., He, S., Song, R., and Li, J., “Reliability based assignment in stochastic-flow freight network”, Applied Mathematics and Computation, Vol. 211, pp. 85-94 (2009).
Yeh, W. C., “A revised layered-network algorithm to search for all d-Minpaths of a limited-flow acyclic network”, IEEE Transactions on Reliability, Vol. 47, pp. 436-442 (1998).
Yeh, W. C., “A simple algorithm to search for all d-MPs with unreliable nodes”, Reliability Engineering & System Safety, Vol. 73, pp. 49-54 (2001).
Yeh, W. C., “Multistate network reliability evaluation under the maintenance cost constraint”, International Journal of Production Economics, Vol. 88, pp. 73-83 (2004).
Yeh, W. C., “A simple minimal path method for estimating the weighted multi-commodity multistate unreliable networks reliability”, Reliability Engineering and System Safety, Vol. 93, pp. 125-136 (2008).
Yeh, W. C., “An Improved Method for the Multistate Flow Network Reliability with Unreliable Nodes and the Budget Constraint Based on Path Set”, IEEE Transactions on Systems, Man, and Cybernetics--Part A: Systems and Humans, Vol. 41, pp. 350-355 (2011).
Zuo, M. J., Tian, Z., and Huang, H. Z., “An efficient method for reliability evaluation of multistate networks given all minimal path vectors”, IIE Transactions, Vol. 39, pp. 811-817 (2007).
Zenklusen, R., and Laumanns, M., “High-confidence estimation of small s-t reliabilities in directed acyclic networks”, Networks, Vol. 57, pp. 376-388 (2011).
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔