大部分的真實系統例如:電腦系統、電力系統、以及運籌系統等，皆可以被良好地建模成一個多階狀態流量網路。對於這類型的網路，系統可靠度是一個重要的績效衡量指標。在這篇論文中兩種不同版本的多階狀態最快路徑問題(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.

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).