On the Multicommodity Reliability for a Stochastic-Flow Network with Node Failure under Budget Constraint

針對失效節點之隨機流量網路求算預算限制下之多商品可靠度

10.29977/JCIIE.200301.0007

林義貴(Yi-Kuei Lin)

可靠度 ； 多商品 ； 隨機流量網路 ； 失效節點 ； 預算限制 ； reliability ； multicommodity ； stochastic-flow networks ； node failure ； budget constraint

工業工程學刊

20卷1期（2003 / 01 / 01）

42 - 48

英文

就品質管理的觀點而言，評估流量網路的績效是一項重要的課題。本文探討的對象爲一隨機型流量網路的流量分配問題，特別是當中每個節點與傳輸線皆有多種容量。考慮有多種類商品經由同一個網路輸送，競爭傳輸綫與節點的容量，求算在預算的限制下給定的需求量皆能成功送達的機率，稱爲多商品可靠度。方法上先採用最小路徑的性質以求出符合需求的下界點，此些下界點代表每個節點與傳輸邊必須持有的容量，再利用此些下界點便可以求出多商品可靠度。

System reliability evaluation for flow networks is an important issue for quality performance. This paper studies the system reliability that a given amount of multicommodity can be transmitted through a stochastic-flow network under the budget constraint, where each node and each arc has several possible capacities. Such reliability is named multicommodity reliability throughout this paper. A simple algorithm is proposed to generate all lower boundary points for (d^1, d^2,…,d(superscript p);C) where d(superscript i) is the demand of commodity i and C is the budget. The multicommodity reliability can then be calculated in terms of such points.

1. Aggarwal, K. K.,Chopra, Y. C.,Bajwa, J. S.(1982).Capacity consideration in reliability analysis of communication systems.IEEE Transactions on Reliability,31
2. Al-Ghanim, A. M.(1999).A heuristic technique for generating minimal path and cutsets of a general network.Computers and Industrial Engineering,36
3. Cremeans, J. E.,Smith, R. A.,Tyndall, G. R.(1970).Optimal multicommodity network flows with resource allocation.Naval Research Logistics Quarterly,17
4. Evans, J. R.(1976).A combinatorial equivalence between a class of multicommodity flow problems and the capacitated transportation problem.Mathematical Programming,10
5. Ford, L. R.,Fulkerson, D. R.(1962).Flows in Networks.Princeton, New Jersey:Princeton University Press.
6. Griffith, W. S.(1980).Multistate reliability models.Journal of Applied Probability,17
7. Hudson, J. C.,Kapur, K. C.(1985).Reliability bounds for multistate systems with multistate components.Operations Research,33
8. Kennington, J. L.(1977).Solving multicommodity transportation problems using a primal partitioning simplex technique.Naval Research Logistics Quarterly,24
9. Kobayashi, K.,Yamamoto, H.(1999).A new algorithm in enumerating all minimal paths in a sparse network.Reliability Engineering and System Safety,65
10. Lee, D. W.,Yum, B. J.(1993).Determination of minimal upper paths for reliability analysis of planar flow networks.Reliability Engineering ＆ System Safety,39
11. Rueger, W. J.(1986).Reliability analysis of networks with capacity-constraints and failures at branches and nodes.IEEE Transactions on Reliability,35
12. Shen, Yuanlong(1995).A new simple algorithm for enumerating all minimal paths and cuts of a graph.Microelectronics and Reliability,35
13. Soh, Sieteng,Rai, S.(1991).CAREL: Computer aided reliability evaluator for distributed computing networks.IEEE Transactions on Parallel ＆ Distributed Systems,2
14. Tomlin, J. A.(1966).Minimum-cost multicommodity network flows.Operations Research,14
15. Weigel, H. S.,Cremeans, J. E.(1972).The multicommodity network flow model revised to include vehicle per time period and node constraints.Naval Research Logistics Quarterly,19
16. Xue, J.(1985).On multistate system analysis.IEEE Transactions on Reliability,34
17. 林曾祥 Lin, Jsen-Shung,Jane, C. C.,阮約翰 Yuan, John(1995).On reliability evaluation of a capacitated-flow network in terms of minimal pathsets.Networks,25(3)
18. 林義貴 Lin, Yi-Kuei(2001).A Simple Algorithm for Reliability Evaluation of a Stochastic-Flow Network with Node Failure.Computers and Operations Research,28(13)
19. 林義貴 Lin, Yi-Kuei(2001)。採用最小割集求算隨機性流量網路之可靠度 On Reliability Evaluation of a Stochastic-Flow Network in Terms of Minimal Cuts。工業工程學刊 Journal of the Chinese Institute of Industrial Engineers，18(3)
20. 林義貴 Lin, Yi-Kuei,阮約翰 Yuan, John(1998).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,5(3)
21. 葉維彰 Yeh, Wei-Chang(1998).A revised layered-network algorithm to search for all d-minpaths of a limited-flow acyclic network.IEEE Transactions on Reliability,47
22. 葉維彰 Yeh, Wei-Chang(2001).A simple algorithm to search for all d-MPs with unreliable nodes.Reliability Engineering ＆ System Safety,73

1. (2010).The stochastic quickest path problem via minimal paths.工業工程學刊,27(2),132-139.
2. (2011).Lagrangian relaxation heuristics for deterministic transshipment problems.工業工程學刊,28(4),256-269.
3. (2012).A multi-state computer network within transmission error rate and time constraints.台灣管理學刊,29(7),477-484.
4. (2012).Evaluation of system reliability of electronic transaction in commercial banks.工業工程學刊,29(5),324-336.
5. (2014).Considering retransmission mechanism and latency for network reliability evaluation in a stochastic computer network.工業工程學刊,31(6),350-358.