An improved algorithm for solving all d-MPs in multi-state networks

Abstract

Reliability is a desirable performance indicator of many real-world systems to measure the quality level. One general method for evaluating multi-state reliability is using d-minimal paths (d-MPs). However, being an NP-hard problem, searching for all d-MPs is a rather challenging task. This paper proposes an improved algorithm to solve the d-MP problem. To reduce the search space of d-MPs, a concept of lower capacity bound is introduced into the d-MP problem, and an effective technique is developed to find lower capacity bounds. Meanwhile, the fast enumeration method which is a recent improvement to the traditional enumeration method is employed to solve d-MPs. In addition, by introducing the operation of transforming undirected edges into directed edges, the proposed algorithm is applicable to solving both directed networks and undirected networks. Through numerical experiments, it is found that the proposed algorithm holds a distinct advantage over the existing methods in solving all d-MPs.

Keywords

Reliability / multi-state network / d-minimal paths / state vector

References

[1] Ahuja R.K., Magnanti T.L., Orlin J.B.. Network Flows–Theory, Algorithms, and Applications, 1993, Englewood Cliffs, NJ: Prentice-Hall International.

[2] Ahuja R.K., Kodialam M., Mishra A.K., Orlin J.B.. Computational investigations of maximum flow algorithms. European Journal of Operational Research, 1997, 97: 509-542.

[3] Aggarwa K.K., Misra K.B., Gupta J.S.. A simple method for reliability evaluation of a communication system. IEEE Transaction on Communications, 1975, 23: 563-565.

[4] Alexopoulos C.. Note on state-space decomposition methods for analyzing stochastic flow networks. IEEE Transaction on Communications, 1995, 44: 354-357.

[5] Ball M.O.. Computational complexity of network reliability analysis an overview. IEEE Transaction on Reliability, 1993, 35: 230-239.

[6] Bai G.H., Zuo M.J., Tian Z.G.. Ordering heuristics for reliability evaluation of multistate networks. IEEE Transaction on Reliability, 2015, 64: 1015-1023.

[7] Bai G.H., Tian Z.G., Zuo M.J.. An improved algorithm for finding all minimal paths in a network. Reliability Engineering and System Safety, 2016, 150: 1-10.

[8] Bai G.H., Zuo M.J., Tian Z.G.. Search for all d-MPs for all d levels in multistate two-terminal networks. Reliability Engineering & System Safety, 2015, 142: 300-309.

[9] Colbourn, C.J. (1987). The Combinatorics of Network Reliability. New York: Oxford University Press.

[10] Cook J., Ramirez-Marquez J.E.. Two-terminal reliability analyses for a mobile ad hoc wireless network. Reliability Engineering and System Safety, 2007, 92: 821-829.

[11] Chen S.G.. Efficiency improvement in explicit enumeration for integer programming problems. IEEE International Conference on Industrial Engineering and Engineering Management, 2013 98-100.

[12] Chen S.G., Lin Y.K.. Searching for d-MPs with fast enumeration. Journal of Computational Science, 2016, 17: 139-147.

[13] Chen S.G., Lin Y.K.. Search for all minimal paths in a general large flow network. IEEE Transaction on Reliability, 2012, 61: 949-956.

[14] Chen S.G.. Search for all minimal paths in a general directed flow network with unreliable nodes. International Journal of Reliability and Quality Performance, 2011, 2: 63-70.

[15] Doulliez P., Jamoulle E.. Transportation networks with random arc capacities. RAIRO, 1972, 6: 45-60.

[16] Forghani-elahabad M., Mahdavi-Amiri N.. A new efficient approach to search for all multi-state minimal cuts. IEEE Transaction on Reliability, 2014, 63: 154-66.

[17] Gebre B.A., Ramirez-Marquez J.E.. Element substitution algorithm for general two-terminal network reliability analyses. IIE Transaction, 2007, 39: 265-275.

[18] Hagstrom J.N.. Note on independence of arcs in antiparallel for network flow problems. Networks, 1984, 14: 567-570.

[19] Jane C.C., Lin J.S., Yuan J.. On reliability evaluation of a limited-flow network in terms of minimal cutsets. IEEE Transaction on Reliability, 1993, 42: 354-361.

[20] Jane C.C., Laih Y.W.. A practical algorithm for computing multi-state two-terminal reliability. IEEE Transaction on Reliability, 2008, 57: 295-302.

[21] Jane C.C., Laih Y.W.. Computing multi-state two-terminal reliability through critical arc states that interrupt demand. IEEE Transaction on Reliability, 2010, 59: 338-344.

[22] Jiang, T. & Liu, Y. (2017). Parameter inference for non-repairable multi-state system reliability models by multi-level observation sequences. Reliability Engineering and System Safety. DOI: 10.1016/J.ress.2016.11.019.

[23] Levitin, G. (2003). The Universal Generating Function in Reliability Analysis and Optimization. London: Springer-Verlag.

[24] Levitin G.. A universal generating function approach for the analysis of multi-state systems with dependent elements. Reliability Engineering and System Safety, 2004, 84: 285-292.

[25] Levitin G., Lisnianski A.. Importance and sensitivity analysis of multi-state systems using the universal generating function method. Reliability Engineering and System Safety, 1999, 65: 271-282.

[26] Lisnianski, A & Levitin, G. (2003). Multi-state System Reliability:Assessment, Optimization and Applications. Singapore: World Scientific.

[27] Lin J.S., Jane C.C., Yuan J.. On reliability evaluation of a capacitated-flow network in terms of minimal pathsets. Network, 1995, 25: 131-138.

[28] Lin Y. K., Chang P. C.. Estimated and exact system reliabilities of a maintainable computer network. Journal of Systems Science and Systems Engineering, 2011, 20: 229-248.

[29] Lin Y. K., Huang C. F.. System reliability of assured accuracy rate for multi-state computer networks from service level agreements viewpoint. Journal of Systems Science and Systems Engineering, 2014, 23: 196-211.

[30] Lin Y. K., Chang P. C.. Predecessor-set technique for reliability evaluation of a stochastic manufacturing system. Journal of Systems Science and Systems Engineering, 2015, 24: 190-210.

[31] Lin Y. K.. A simple algorithm for reliability evaluation of a stochastic-flow network with node failure. Computers & Operations Research, 2001, 28: 1277-1285.

[32] 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, 2002, 75: 41-46.

[33] Mishra R., Saifi M.A., Chaturvedi S.K.. Enumeration of minimal cutsets for directed networks with comparative reliability study for paths or cuts. Quality and Reliability Engineering International, 2015, 32: 555-565.

[34] Mo, Y., Xing, L., Cui, L. & Si, S. (2017). MDD-based performability analysis of multi-state linear consecutive-k-out-of-n: F systems. Reliability Engineering and System Safety. DOI: 10.1016/J.ress.2016.08.027.

[35] Niu Y. F., Shao F. M.. A practical bounding algorithm for computing two-terminal reliability based on decomposition technique. Computers and Mathematics with Application, 2011, 61: 2241-2246.

[36] Niu Y. F., Xu X. Z.. Reliability evaluation of multi-state systems under cost consideration. Applied Mathematical Modelling, 2012, 36: 4261-4270.

[37] Volkanovski A., Cepin M., Mavko B.. Application of the fault tree analysis for assessment of power system reliability. Reliability Engineering and System Safety, 2009, 94: 1116-1127.

[38] Wu W. W., Ning A., Ning X. X.. Evaluation of the reliability of transport networks based on the stochastic flow of moving objects. Reliability Engineering and System Safety, 2008, 93: 838-844.

[39] Ramirez J.E., Coit D.W.. A Monte-Carlo simulation approach for approximating multi-state two-terminal reliability. Reliability Engineering and System Safety, 2005, 87: 253-264.

[40] Ramirez-Marquez J. E., Coit D. W., Tortorella M.. A generalized multi-state-based path vector approach to multi-state two-terminal reliability. IIE Transaction, 2006, 38: 477-488.

[41] Satitsatian S., Kapur K. C.. An algorithm for lower reliability bounds of multi-state two-terminal networks. IEEE Transaction on Reliability, 2006, 55: 199-206.

[42] Yeh W. C.. A simple method to verify all d-minimal path candidates of a limited-flow network and its reliability. International Journal of Advanced Manufacturing Technology, 2002, 20: 77-81.

[43] 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 Operational Research Society, 2005, 56: 1235-1240.

[44] Yeh W. C., Bae C., Huang C. L.. A new cut-based algorithm for the multi-state flow network reliability problem. Reliability Engineering and System Safety, 2015, 136: 1-7.

[45] Yeh W. C.. A fast algorithm for searching all multi-state minimal cuts. IEEE Transaction on Reliability, 2008, 57: 581-588.

[46] Yeh W. C.. An improved sum-of-disjoint-products technique for symbolic multi-state flow network reliability. IEEE Transaction on Reliability, 2015, 64: 1185-1193.

[47] Yeh W. C.. A simple universal generating function method to search for all minimal paths in networks. IEEE Transaction on System Man Cybernetics -Part A: System Humans, 2009, 39: 1247-1254.

[48] Yeh W. C.. New method in searching for all minimal paths for the directed acyclic network reliability problem. IEEE Transaction on Reliability, 2016, 65: 1263-1270.

[49] Yeh, W. C. (2017). Evaluation of the one-to-all-target-subsets reliability of a novel deterioration-effect acyclic multi-state information network. Reliability Engineering and System Safety. DOI: 10.1016/J.ress.2016.11.012.

[50] Zuo M. J., Tian Z. G., Huang H. Z.. An efficient method for reliability evaluation of multistate networks given all minimal path vectors. IIE Transaction, 2007, 39: 811-817.

[51] Zhou Y., Meng Q.. Improving efficiency of solving d-MC problem in stochastic-flow network. Reliability Engineering and System Safety, 2007, 92: 30-39.