在一個製造系統的網路中，時常可見零組件經由一些作業程序而產生品質不相同的成品或半成品，由於這些不同品質的成品或半成品之總數量通常存在著某種特定的比例關係，因此可利用Fang and Qi (2003) 所導入的特殊D-node 來將製造過程描述成一個分餾的餾化(distillation) 過程。其中，進入D-node 的所有流量必須依照某個既定的比例自D-node 的流出弧分餾出去。由於D-node 的分餾比例固定了流量之間的相依關係，導致此製造網路的分析過程較為複雜。另外，因為流量經過D-node 就必須分送到其所有的流出弧，因此自起源點至需求點的運送過程將不再僅是經過一條簡單路徑，而是一個包含許多條簡單路徑的網路子圖。當網路圖中每一條弧的容量符合一個多狀態的機率分配時，計算不含D-node 之一般網路的可靠度已是一個NP-hard 的問題，因此計算含有D-node 的製造網路之可靠度將更具挑戰性，而此亦為本論文之主要研究議題。本論文首先提出一套前置處理程序對原問題加以簡化，進而提出一套新演算法以計算含有D-node 的製造網路之網路可靠度，其後亦將探討如何在滿足給定的可靠度門檻值之下計算含有D-node 的製造網路之最小成本，以及多狀態弧容量之分配網路在最短路徑問題上的相關議題。

Abstract
In a manufacturing network, there often exist operations that produce the same products or semi-products of diferent qualities. Such a phenomenon can be described by a distillation process using a specialized D-node introduced by Fang and Qi (2003) where the flow enters a D-node has to be distributed according to a pre-specified vector of ratios associated with its outgoing arcs. The existence of D-node complicates the manufacturing process since it creates the relation of flow dependency. In particular, to send flow successfully from a source node to a sink node, an augmenting subgraph containing many paths instead of an augmenting simple path has to be constructed, since the flow passing through a D-node has to be distributed to all of its outgoing arcs. As a result, when the capacity associated with each arc obeys a multi-state probability distribution, calculating the system reliability of shipping a given amount of flows for a multi-state capacitated manufacturing network containing D-nodes becomes a difficult task. This paper focuses on techniques to derive the system reliability for such a multi-state capacitated manufacturing network containing D-nodes. We will first introduce polynomial-time preprocessing techniques that simplify the problem structure, and then propose algorithms for calculating the network reliability. In addition, we also investigate the problem of constructing a manufacturing network with multi-state arc capacity that satisfies the reliability lower bound with minimum total cost, and study the problem of stochastic shortest path using our proposed solution methods as well.

參考文獻
Alexopoulos, C. State space partitioning methods for stochastic shortest path problems.Networks, 30(1), 9-21, 1997.
Chang, C. C.-H. J., M. D. and Engquist, M. An improved primal simplex variant for pure processing networks. ACM Transactions on Mathematical Software, 15(1), 64-78, 1989.
Chen, C.-H. J. and Engquist, M. A primal simplex approach to pure processing networks. Management Science, 32(12), 1582-1589, 1986.
Colbourn, C. J. The combinatorics of network reliability. Oxford, New York: Oxford University Press, 1987.
Daly, M. S. 2001. State space partition techniques for multiterminal and multicommodity flows in stochastic networks. Unpublished doctoral dissertation, Georgia Institute of Technology.
Daly, M. S. and Alexopoulos, C. State space partition techniques for multiterminal flows in stochastic networks. Networks, 48(2), 90-111, 2006.
Douilliez, P. and Jamoulle, E. Transportation networks with random arc capacities. R.A.I.R.O., 3, 45-49, 1972.
Fang, S. C. and Qi, L. Manufacturing network flows: A generalized network flow model for manufacturing process modeling. Optimization Methods and Software, 18, 143-165, 2003.
Frank, H. and Hakimi, S. L. Probabilistic flow through a communications network. IEEE Trans. Circuit Theor, CT-12, 413-414, 1965.
Hsieh, C. C. and Lin, M. H. Reliability-oriented multi-resource allocation in a stochastic-flow network. Reliability Engineering and System Safety, 81, 155-161, 2003.
Koene, J. 1982. Minimal cost flow in processing networks. a primal approach. Unpublished doctoral dissertation, Eindhoven University of Technology, Eindhoven, The Netherlands.
Lin, J. C. 2005. Maximum flows in distribution networks: problem generator and algorithms. Unpublished master's thesis, National Cheng Kung University.
Lin, J. C. C., J. S. and Yuan, J. On reliability evaluation of a capacitated-flow network in terms of minimal pathsets. Networks, 25, 131-138, 1995.
Lin, S. J. 2006. A network simplex algorithm for the minimum distribution cost problem. Unpublished master's thesis, National Cheng Kung University.
Lin, Y. K. On reliability evaluation of a stochastic-flow network in terms of minimal cuts. Journal of Chinese Institute of Industrial Engineers, 18(3), 49-54, 2001.
Lin, Y. K. Study on the system capacity for a multicommodity stochastic-flow network with node failure. Reliability Engineering and System Safety, 78, 57-62, 2002a.
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, 75, 41-46, 2002b.
Lin, Y. K. On the multicommodity reliability for a stochastic-flow network with node failure under budget constraint. Journal of the Chinese Institute of Industrial Engineers, 20(1), 42-48, 2003.
Lin, Y. K. Reliability of a stochastic-flow network with unreliable branches nodes, under budget constraints. IEEE Transactions on Reliability, 53(3), 381-387, 2004.
Lin, Y. K. Generate upper boundary vectors meeting the demand and budget for a p-commodity network with unreliable nodes. European Journal of Operational Research, 183, 253-262, 2007a.
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, 37(2), 180-188, 2007b.
Mine, H. Reliability of physical systems. IRE Trans. Circuit Theor., CT-6, 138-151,
1959.
Moore, E. F. and Shannon, C. E. Reliable circuit using less reliable relays. J. Franklin Inst., 262,263, 191-208,281-297, 1956.
Moskowitz, F. The analysis of redundancy networks. AIEE Trans. Commun. Electron., 39, 627-632, 1958.
Provan, J. S. and Ball, M. O. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM Journal on Computing, 12, 777-788, 1983.
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, 87, 253-264, 2005.
Satyanarayana, A. and Prabhakar, A. New topological formula and rapid algorithm for reliability analysis of complex networks. IEEE Transactions on Reliability, R-27, 82-100, 1978.
Sheu, T. M. J., R. L. and Wang, I. L. Maximum flow problem in the distribution network. Journal of Industrial and Management Optimization, 2(3), 237-254,
2006.
Yeh, W. C. A revised layered-network algorithm to search for all d-minpaths of a limited-flow acyclic network. IEEE Transactions on Reliability, 47, 436-442, 1998.
Yeh, W. C. A simple algorithm to search for all d-mps with unreliable nodes. Reliability Engineering and System Safety, 73, 49-54, 2001.
Yeh, W. C. A novel method for the network reliability in terms of capacitated- minimum-paths without knowing minimum-paths in advance. Journal of the Operation Research Society, 56, 1235-1240, 2005.
Yeh, W. C. A simple algorithm to search for all mcs in networks. European Journal of Operational Research, 174, 1694-1705, 2006.
Yeh, W. C. A simple minimal path method for estimating the weighted multi-commodity multistate unreliable networks reliability. Reliability Engineering and System Safety, 93, 125-136, 2008.