Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-26T04:57:27.440Z Has data issue: false hasContentIssue false
  • English
  • Français

PERMUTATIONAL METHODS FOR PERFORMANCE ANALYSIS OF STOCHASTIC FLOW NETWORKS

Published online by Cambridge University Press:  19 November 2013

Ilya Gertsbakh ,
Reuven Rubinstein ,
Yoseph Shpungin  and
Radislav Vaisman
Ilya Gertsbakh
Affiliation:
Department of Mathematics, Ben Gurion University, Beer-Sheva 84105, Israel. E-mail: [email protected]
Reuven Rubinstein
Affiliation:
Department of Mathematics, Ben Gurion University, Beer-Sheva 84105, Israel. E-mail: [email protected]
Yoseph Shpungin
Affiliation:
Department of Software Engineering, Shamoon College of Engineering, Beer-Sheva 84105, Israel. E-mail: [email protected]
Radislav Vaisman
Affiliation:
Faculty of Industrial Engineering and Management, Technion, Israel Institute of Technology, Haifa, Israel. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we show how the permutation Monte Carlo method, originally developed for reliability networks, can be successfully adapted for stochastic flow networks, and in particular for estimation of the probability that the maximal flow in such a network is above some fixed level, called the threshold. A stochastic flow network is defined as one, where the edges are subject to random failures. A failed edge is assumed to be erased (broken) and, thus, not able to deliver any flow. We consider two models; one where the edges fail with the same failure probability and another where they fail with different failure probabilities. For each model we construct a different algorithm for estimation of the desired probability; in the former case it is based on the well known notion of the D-spectrum and in the later one—on the permutational Monte Carlo. We discuss the convergence properties of our estimators and present supportive numerical results.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 28 , Issue 1 , January 2014 , pp. 21 - 38
Copyright
Copyright © Cambridge University Press 2013 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Ravindra Ahuja, K., Thomas Magnanti, L. & James Orlin, B. (1993). Network Flows: Theory, Algorithms, and Applications. NJ, Englewood Cliffs: Prentice Hall.Google Scholar
2.Botev, Z.I. & Kroese, D.P. (2012). Efficient monte carlo simulation via the generalized splitting method. Statistics and Computing 22: 1–16.CrossRefGoogle Scholar
3.Botev, Z.I., L'Ecuyer, P., Rubino, G., Simard, R. & Tuffin, B. (2013). Static network reliability estimation via generalized splitting. INFORMS Journal on Computing 25: 56–71.CrossRefGoogle Scholar
4.Elperin, T., Gertsbakh, I. & Lomonosov, M. (1992). An evolution model for Monte Carlo estimation of equilibrium network renewal parameters. Probability in the Engineering and Informational Sciences 6: 457–469.CrossRefGoogle Scholar
5.Elperin, T., Gertsbakh, I.B. & Lomonosov, M. (1991). Estimation of network reliability using graph evolution models. IEEE Transactions on Reliability 40(5): 572–581.CrossRefGoogle Scholar
6.Erdos, P. & Renyi, A. (1959). On random graphs. i. Publicationes Mathematicae 6: 290–297.CrossRefGoogle Scholar
7.Gertsbakh, I. & Shpungin, Y. (2004). Combinatorial approaches to monte carlo estimation of network lifetime distribution. Applied Stochastic Models in Business and Industry 20: 49–57.CrossRefGoogle Scholar
8.Gertsbakh, I. and Shpungin, Y. (2007). Network reliability importance measures: combinatorics and monte carlo based computations. WSEAS Trans Comp 4: 21–23.Google Scholar
9.Gertsbakh, I. & Shpungin, Y. (2009). Models of network reliability: analysis, combinatorics, and Monte Carlo. New York: CRC Press.Google Scholar
10.Gertsbakh, I. & Shpungin, Y. (2010). Network reliability design: combinatorial and Monte Carlo approach. Proceedings of the International Conference on Modeling and Simulation, Canada, pp. 88–94.CrossRefGoogle Scholar
11.Gertsbakh, I. & Shpungin, Y. (2011). Network Reliability and Resilience. 1st ednBerlin, Heidelberg: Springer.CrossRefGoogle Scholar
12.Gertsbakh, I. & Shpungin, Y. (2012). Spectral Approach to Reliability Evaluation of Flow Networks. Proceedings of the European Modeling and Simulation Symposium, Vienna, pp. 68–73.Google Scholar
13.Goldberg, A.V. & Rao, S. (1998). Beyond the flow decomposition barrier. Journal of Alternative and Complementary Medicine, 45(5): 783–797.Google Scholar
14.Kroese, D.P., Hui, K.-P. & Nariai, S. (2007). Network reliability optimization via the cross-entropy method. IEEE Transactions on Reliability, 56(2): 275–287.CrossRefGoogle Scholar
15.Kroese, D.P., Taimre, T. & Botev, Z.I. (2011). Handbook of Monte Carlo methods. New York: John Wiley & Sons.CrossRefGoogle Scholar
16.Lin, Y. (2004). Reliability of a stochastic-flow network with unreliable branches & nodes, under budget constraints. IEEE Transactions on Reliability, 53(3): 381–387.CrossRefGoogle Scholar
17.Rubinstein, R., Vaisman, R. & Botev, Z. (2012). Hanging edges for fast reliability estimation. Technical report, Technion, Haifa, Israel.Google Scholar
18.Rubinstein, R.Y. & Kroese, D.P. (2007). Simulation and the Monte Carlo Method, 2nd ednNew York: John Wiley and Sons.CrossRefGoogle Scholar
19.Samaniego, F.J. (1985). On closure of the ifr under formation of coherent systems. IEEE Trans Reliab, 34: 69–72.CrossRefGoogle Scholar