A simple vectorization algorithm to address the d-MP problem without generating duplicate candidates
DOI:
https://doi.org/10.5540/03.2021.008.01.0346Palavras-chave:
System reliability, Vectorization algorithm, d-MP problem, Multistate flow networkResumo
The reliability of a multistate flow network (MFN) can be evaluated indirectly based on d-minimal paths (d-MPs). In fact, with all the d-MPs at hand, an MFN’s reliability can be computed by calculating a union probability. Hence the determination of all d-MPs in an MFN has been a very attractive problem in the last decades. As a result, many algorithms have been proposed to solve the d-MP problem. However, as the number of d-MPs grows exponentially with the size of the network, the available algorithms in the literature are not so practical. Here, we propose a vectorization algorithm to address the problem and show its practical efficiency using three benchmarks. The numerical results show that the vectorization algorithm solves the problem more than three times faster than the non-vectorization one in some cases.
Downloads
Referências
Bentley, J. L. Multidimensional divide-and-conquer. Communications of the ACM 23, 4 (1980), 214-229.
Chen, X., Tao, J., Bai, G., and Zhang, Y. Search for d-mps without duplications in multistate two-terminal networks. In 2017 Second International Conference on Reliability Systems Engineering (ICRSE) (2017), IEEE, pp. 1-7.
Forghani-elahabad, M. 1 exact reliability evaluation of multistate flow networks. In Systems Reliability Engineering. De Gruyter, 2021, pp. 1-24.
Forghani-elahabad, M., and Bonani, L. H. Finding all the lower boundary points in a multistate two-terminal network. IEEE Transactions on Reliability 66, 3 (2017), 677-688.
Forghani-elahabad, M., and Kagan, N. Assessing reliability of multistate flow networks under cost constraint in terms of minimal cuts. International Journal of Reliability, Quality and Safety Engineering 26, 05 (2019), 1950025.
Forghani-elahabad, M., and Kagan, N. Reliability evaluation of a stochastic-flow net work in terms of minimal paths with budget constraint. IISE Transactions 51, 5 (2019), 547-558.
Forghani-elahabad, M., Kagan, N., and Mahdavi-Amiri, N. An mp-based approxi- mation algorithm on reliability evaluation of multistate flow networks. Reliability Engineering and System Safety 191 (2019), 106566.
Forghani-Elahabad, M., and Mahdavi-Amiri, N. On search for all d-mcs in a network flow. Iranian Journal of Operations Research 4, 2 (2013), 108-126.
Forghani-elahabad, M., and Mahdavi-Amiri, N. A new efficient approach to search for all multi-state minimal cuts. IEEE Transactions on Reliability 63, 1 (2014), 154-166.
Forghani-elahabad, M., and Mahdavi-Amiri, N. An improved algorithm for finding all upper boundary points in a stochastic-flow network. Applied Mathematical Modelling 40, 4 (2016), 3221-3229.
Forghani-elahabad, M., and Mahdavi-Amiri, N. An algorithm to search for all minimal cuts in a flow network. Advances in Systems Science and Applications 20, 4 (2020), 1-10.
Hennessy, J. L., and Patterson, D. A. Computer architecture: a quantitative approach. Elsevier, 2011.
Lamalem, Y., Housni, K., and Mbarki, S. An efficient method to find all d-mps in multistate two-terminal networks. IEEE Access 8 (2020), 205618-205624.
Lin, J.-S., Jane, C.-C., and Yuan, J. On reliability evaluation of a capacitated-flow network in terms of minimal pathsets. Networks 25, 3 (1995), 131-138.
Mansourzadeh, S. M., Nasseri, S. H., Forghani-elahabad, M., and Ebrahimnejad, A. A comparative study of different approaches for finding the upper boundary points in stochastic-flow networks. International Journal of Enterprise Information Systems (IJEIS) 10, 3 (2014), 13-23.
Niu, Y.-F., Xu, X.-Z., He, C., Ding, D., and Liu, Z.-Z. Capacity reliability calculation and sensitivity analysis for a stochastic transport network. IEEE Access 8 (2020), 133161— 133169.
Rauber, T., and Rünger, G. Parallel programming: for multicore and cluster systems. Springer-Verlag, 2010. [18] Yeh, W.-C., and Zuo, M. J. A new subtraction-based algorithm for the d-mps for all d problem. IEEE Transactions on Reliability 68, 3 (2019), 999-1008.
