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

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

林義貴(Yi-Kuei Lin)

《工業工程學刊》 20卷1期 (2003/01) Pp. 42-48

https://doi.org/10.29977/JCIIE.200301.0007

摘要

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

關鍵字

可靠度 ； 多商品 ； 隨機流量網路 ； 失效節點 ； 預算限制

並列摘要

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.

並列關鍵字

reliability ； multicommodity ； stochastic-flow networks ； node failure ； budget constraint

參考文獻

Aggarwal, K. K.,Chopra, Y. C.,Bajwa, J. S.(1982).Capacity consideration in reliability analysis of communication systems.IEEE Transactions on Reliability.31

Al-Ghanim, A. M.(1999).A heuristic technique for generating minimal path and cutsets of a general network.Computers and Industrial Engineering.36

Cremeans, J. E.,Smith, R. A.,Tyndall, G. R.(1970).Optimal multicommodity network flows with resource allocation.Naval Research Logistics Quarterly.17

Evans, J. R.(1976).A combinatorial equivalence between a class of multicommodity flow problems and the capacitated transportation problem.Mathematical Programming.10

Ford, L. R.,Fulkerson, D. R.(1962).Flows in Networks.Princeton, New Jersey:Princeton University Press.