Search for d-MPs without duplicates in two-terminal multistate networks based on MPs

doi:10.23919/JSEE.2022.000152

Journal of Systems Engineering and Electronics ›› 2022, Vol. 33 ›› Issue (6): 1332-1341.doi: 10.23919/JSEE.2022.000152

• RELIABILITY • Previous Articles

Search for d-MPs without duplicates in two-terminal multistate networks based on MPs

Bei XU¹^,²(), Yining FANG¹^,*(), Guanghan BAI¹(), Yun’an ZHANG¹(), Junyong TAO¹()

¹ Laboratory of Science and Technology on Integrated Logistics Support, College of Intelligent Sciences and Technology, National University of Defense Technology, Changsha 410073, China
² School of General Aviation, Nanchang Hangkong University, Nanchang 330063, China

Received:2021-01-13 Online:2022-12-18 Published:2022-12-24
Contact: Yining FANG E-mail:70611@nchu.edu.cn;fangyining@nudt.edu.cn;baiguanghan@nudt.edu.cn;yazhang@nudt.edu.cn;taojunyong@nudt.edu.cn
About author:
XU Bei was born in 1987. She is currently working toward her Ph.D. degree with National University of Defense Technology, Changsha, China. She is also currently a lecturer with the School of General Aviation, Nanchang HangKong University, Jiangxi, China. Her current research interests focus on network reliability and system resilience. E-mail: 70611@nchu.edu.cn

FANG Yining was born in 1991. She received her Ph.D. degree in mechanical engineering from University of Alberta, Edmonton, AB, Canada, in 2019. She is currently a lecturer with the Laboratory of Science and Technology on Integrated Logistics Support, National University of Defense Technology. Her current research interests include system resilience. E-mail: fangyining@nudt.edu.cn

BAI Guanghan was born in 1986. He received the Ph.D. degree in mechanical engineering from University of Alberta, Edmonton, AB, Canada, in 2016. He is currently a lecturer with the Laboratory of Science and Technology on Integrated Logistics Support, National University of Defense Technology. His current research interests include network reliability and system resilience. E-mail: baiguanghan@nudt.edu.cn

ZHANG Yun’an was born in 1983. He received his Ph.D. degree in mechanical engineering from National University of Defense Technology, Changsha, China, in 2014. He is currently an associate professor with the Laboratory of Science and Technology on Integrated Logistics Support, National University of Defense Technology. His current research interest focuses on system reliability. E-mail: yazhang@nudt.edu.cn

TAO Junyong was born in 1969. He received his Ph.D. degree in mechanical engineering from National University of Defense Technology, Changsha, China, in 2000. He is currently a professor with the Laboratory of Science and Technology on Integrated Logistics Support, National University of Defense Technology. His current research interests include reliability test and evaluation. E-mail: taojunyong@nudt.edu.cn
Supported by:
This work was supported by the National Natural Science Foundation of China (71701207), the Science and Technology on Reliability & Environmental Engineering Laboratory (6142004004-2), and the Science and Technology Commission of the CMC (2019-JCJQ-JJ-180)

Abstract

Abstract:

The reliability evaluation of a multistate network is primarily based on d-minimal paths/cuts (d-MPs/d-MCs). However, being a nondeterminism polynomial hard (NP-hard) problem, searching for all d-MPs is a rather challenging task. In existing implicit enumeration algorithms based on minimal paths (MPs), duplicate d-MP candidates may be generated. An extra step is needed to locate and remove these duplicate d-MP candidates, which costs significant computational effort. This paper proposes an efficient method to prevent the generation of duplicate d-MP candidates for implicit enumeration algorithms for d-MPs. First, the mechanism of generating duplicate d-MP candidates in the implicit enumeration algorithms is discussed. Second, a direct and efficient avoiding-duplicates method is proposed. Third, an improved algorithm is developed, followed by complexity analysis and illustrative examples. Based on the computational experiments comparing with two existing algorithms, it is found that the proposed method can significantly improve the efficiency of generating d-MPs for a particular demand level d.

Key words: reliability, multistate network, d-minimal path (d-MP), duplicate

Bei XU, Yining FANG, Guanghan BAI, Yun’an ZHANG, Junyong TAO. Search for d-MPs without duplicates in two-terminal multistate networks based on MPs[J]. Journal of Systems Engineering and Electronics, 2022, 33(6): 1332-1341.

Figures/Tables 10

Fig 1

Table 1

Table 2

Table 3

Fig 2

Table 4

Table 5

Fig 3

Fig 4

Fig 5

References 30

1	AVEN T Availability evaluation of oil/gas production and transportation systems. Reliability Engineering, 1987, 18 (1): 35- 54. doi: 10.1016/0143-8174(87)90050-3
2	ALAMOUDY M A, MOHAMED A Reliability evaluation of communication flow network considering a multi-state system. IOSR Journal of Electronics and Communication Engineering, 2019, 14 (1): 17- 25.
3	SHARMA U, PANIGRAHI S C, MISRA R B Reliability evaluation of a communication system considering a multistate model. Microelectronics Reliability, 1990, 30 (4): 701- 704. doi: 10.1016/0026-2714(90)90174-L
4	SAMAVATIAN V, IMAN-EINI H, AVENAS Y Reliability assessment of multistate degraded systems: an application to power electronic systems. IEEE Trans. on Power Electronics, 2020, 35 (4): 4024- 4032. doi: 10.1109/TPEL.2019.2933063
5	LIN Y K System reliability evaluation for a multistate supply chain network with failure nodes using minimal paths. IEEE Trans. on Reliability, 2009, 58 (1): 34- 40. doi: 10.1109/TR.2008.2011660
6	LIN Y K, HUANG C F, CHANG C C Reliability of spare routing via intersectional minimal paths within budget and time constraints by simulation. Annals of Operations Research, 2022, 312 (1): 345- 368. doi: 10.1007/s10479-020-03923-y
7	PENG R, LIU H L, XIE M A study of reliability of multi-state systems with two performance sharing groups. Quality and Reliability Engineering International, 2016, 32 (7): 2623- 2632. doi: 10.1002/qre.1963
8	JANE C C, LAIH Y W Computing multi-state two-terminal reliability through critical arc states that interrupt demand. IEEE Trans. on Reliability, 2010, 59 (2): 338- 345. doi: 10.1109/TR.2010.2046805
9	LEVITIN G. Multi-state vector-k-out-of-n systems. IEEE Trans. on Reliability, 2013, 62(3): 648–657.
10	FAN H H, SUN X H A multi-state reliability evaluation model for P2P networks. Reliability Engineering and System Safety, 2010, 95 (4): 402- 411. doi: 10.1016/j.ress.2009.11.011
11	BALL M O, COLBOURN C J, PROVAN J S. Network reliability. BALL M O, MAGNANTI T L, MONMA C L, et al. ed. Handbooks in operations research and management science. Amsterdam: North Holand, 1995, 7: 673–762.
12	JANE C C, LAIH Y W A practical algorithm for computing multi-state two-terminal reliability. IEEE Trans. on Reliability, 2008, 57 (2): 295- 302. doi: 10.1109/TR.2008.920792
13	JANE C C, LAIH Y W A dynamic bounding algorithm for approximating multi-state two-terminal reliability. European Journal of Operational Research, 2010, 205 (3): 625- 637. doi: 10.1016/j.ejor.2010.01.033
14	ZHANG T, GUO B Capacitated stochastic coloured Petri net-based approach for computing two-terminal reliability of multi-state network. Journal of Systems Engineering and Electronics, 2012, 23 (2): 304- 313. doi: 10.1109/JSEE.2012.00038
15	RAMIREZ-MARQUEZ J E, COIT D W A Monte-Carlo simulation approach for approximating multi-state two-terminal reliability. Reliability Engineering and System Safety, 2005, 87 (2): 253- 264. doi: 10.1016/j.ress.2004.05.002
16	JANE C C Reliability evaluation of a limited-flow network in terms of minimal cutsets. IEEE Trans. on Reliability, 1993, 42 (3): 354- 361. doi: 10.1109/24.257817
17	LIN J S, JANE C C, YUAN J On reliability evaluation of a capacitated‐flow network in terms of minimal pathsets. Networks, 1995, 25 (3): 131- 138. doi: 10.1002/net.3230250306
18	CHEN S G, LIN Y K Searching for d-MPs with fast enumeration . Journal of Computational Science, 2016, 17 (1): 139- 147.
19	LIN Y K A simple algorithm for reliability evaluation of a stochastic flow network with node failure. Operations Research, 2001, 28 (1): 1277- 1285.
20	YEH W C. A simple method to verify all d-minimal path candidates of a limited-flow network and its reliability. The International Journal of Advanced Manufacturing Technology, 2002, 20(1): 77–81.
21	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 and System Safety, 2015, 142, 300- 309. doi: 10.1016/j.ress.2015.04.013
22	YEH W C Fast algorithm for searching d-MPs for all possible d . IEEE Trans. on Reliability, 2018, 67 (1): 208- 315.
23	YEH W C, ZUO M J A new subtraction-based algorithm for the d-MPs for all d problem . IEEE Trans. on Reliability, 2019, 68 (3): 999- 1008. doi: 10.1109/TR.2019.2901057
24	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 (1): 1235- 1240.
25	YEH W C A novel node-based sequential implicit enumeration method for finding all d-MPs in a multistate flow network . Information Sciences, 2015, 297 (1): 283- 292.
26	NIU Y F, WAN X Y, XU X Z, et al Finding all multi-state minimal paths of a multi-state flow network via feasible circulations. Reliability Engineering and System Safety, 2020, 204 (2): 107188.
27	FORGHANI-ELAHABAD M, BONANI L H Finding all the lower boundary points in a multistate two-terminal network. IEEE Trans. on Reliability, 2017, 66 (3): 677- 688. doi: 10.1109/TR.2017.2712661
28	XU X Z, NIU Y F, HE C A minimal path-based method for computing multistate network reliability. Complexity, 2020, 2020, 8060794. doi: 10.1155/2020/8060794
29	BAI G H, XU B, CHEN X G, et al Searching for d-MPs for all level d in multistate two-terminal networks without duplicates . IEEE Trans. on Reliability, 2021, 70 (1): 319- 330. doi: 10.1109/TR.2020.3004971
30	COLBOURN J C. The combinatorics of network reliability. Oxford: Oxford University Press, 1987.

j	The components in ${ {\bf{MP} } }_{j}$	${ {\bf{MP} } }_{j}$
1	$ \left\{{a}_{1},{a}_{4},{a}_{8}\right\} $	(1,0,0,1,0,0,0,1,0)
2	$ \left\{{a}_{1},{a}_{4},{a}_{7},{a}_{9}\right\} $	(1,0,0,1,0,0,1,0,1)
3	$ \left\{{a}_{1},{a}_{3},{a}_{5},{a}_{8}\right\} $	(1,0,1,0,1,0,0,1,0)
4	$ \left\{{a}_{1},{a}_{3},{a}_{5},{a}_{7},{a}_{9}\right\} $	(1,0,1,0,1,0,1,0,1)
5	$ \left\{{a}_{1},{a}_{3},{a}_{6},{a}_{9}\right\} $	(1,0,1,0,0,1,0,0,1)
6	$ \left\{{a}_{2},{a}_{5},{a}_{8}\right\} $	(0,1,0,0,1,0,0,1,0)
7	$ \left\{{a}_{2},{a}_{5},{a}_{7},{a}_{9}\right\} $	(0,1,0,0,1,0,1,0,1)
8	$ \left\{{a}_{2},{a}_{6},{a}_{9}\right\} $	(0,1,0,0,0,1,0,0,1)

ID	${\boldsymbol{F}^2_k }=({f}_{1},{f}_{2},\cdots ,{f}_{m})$	MP index	${\boldsymbol{X}}=({x}_{1},{x}_{2},\cdots ,{x}_{m})$
1	(1,0,0,1,0,0,0,0)	{1,4}	(2,0,1,1,1,0,1,1,1)
1	(0,1,1,0,0,0,0,0)*	{2,3}*	(2,0,1,1,1,0,1,1,1)
2	(1,0,0,0,0,0,1,0)	{1,7}	(1,1,0,1,1,0,1,1,1)
2	(0,1,0,0,0,1,0,0)*	{2,6}*	(1,1,0,1,1,0,1,1,1)
3	(0,0,1,0,0,0,1,0)	{3,7}	(1,1,1,0,2,0,1,1,1)
3	(0,0,0,1,0,1,0,0)*	{4,6}*	(1,1,1,0,2,0,1,1,1)
4	(0,0,1,0,0,0,0,1)	{3,8}	(1,1,1,0,1,1,0,1,1)
4	(0,0,0,0,1,1,0,0)*	{5,6}*	(1,1,1,0,1,1,0,1,1)
5	(0,0,0,1,0,0,0,1)	{4,8}	(1,1,1,0,1,1,1,0,2)
5	(0,0,0,0,1,0,1,0)*	{5,7}*	(1,1,1,0,1,1,1,0,2)

ID	${\boldsymbol{F}^3_k }=({f}_{1},{f}_{2},\cdots ,{f}_{8})$	MP index	${\boldsymbol{X}}=({x}_{1},{x}_{2},\cdots ,{x}_{9})$
1	(1,0,1,0,0,0,1,0)	{1,3,7}	(2,1,1,1,2,0,1,2,1)
	(1,0,0,1,0,1,0,0)	{1,4,6}*
	(0,1,1,0,0,1,0,0)	{2,3,6}*
2	(1,0,1,0,0,0,0,1)	{1,3,8}	(2,1,1,1,1,1,0,2,1)
	(1,0,0,0,1,1,0,0)	{1,5,6}*
	(1,0,0,1,0,0,0,1)	{1,4,8}
3	(1,0,0,0,1,0,1,0)	{1,5,7}*	(2,1,1,1,1,1,1,1,2)
	(0,1,0,0,1,1,0,0)	{2,5,6}*
	(0,1,1,0,0,0,0,1)	{2,3,8}*
4	(1,0,0,0,0,1,1,0)	{1,6,7}	(1,2,0,1,2,0,1,2,1)
4	(0,1,0,0,0,2,0,0)	{2,6,6}*	(1,2,0,1,2,0,1,2,1)
5	(1,0,0,0,0,0,1,1)	{1,7,8}	(1,2,0,1,1,1,1,1,2)
5	(0,1,0,0,0,1,0,1)	{2,6,8}*	(1,2,0,1,1,1,1,1,2)
6	(0,0,1,0,0,1,0,1)	{3,6,8}	(1,2,1,0,2,1,0,2,1)
6	(0,0,0,0,1,2,0,0)	{5,6,6}*	(1,2,1,0,2,1,0,2,1)
7	(0,0,1,0,0,0,1,1)	{3,7,8}	(1,2,1,0,2,1,1,1,2)
	(0,0,0,1,0,1,0,1)	{4,6,8}*
	(0,0,0,0,1,1,1,0)	{5,6,7}*

d	$\left\|{{\rm{MP}}}^{d}\right\|$	$\left\|{{\rm{MP}}}_{{\rm{dup}}}^{d}\right\|$	Ratio
d	$\left\|{{\rm{MP}}}^{d}\right\|$	$\left\|{{\rm{MP}}}_{{\rm{dup}}}^{d}\right\|$	${T}_{{\rm{Chen}}}/T$	${T}_{{\rm{Xu}}}/T$
2	59	9	1.3342	0.9576
4	410	1561	2.4797	0.9903
6	1498	7855	46.0948	1.4050
8	3975	24577	50.3055	2.2351
10	8701	59518	78.7186	6.8827
12	6972	81833	31.9020	5.7790
14	4536	58551	19.2290	4.6038
16	2285	33569	10.2332	3.6003
18	743	13932	8.0433	2.8418
20	66	3098	8.8775	2.6143

3×n	$\left\|{\rm{MP}}\right\|$	$\left\|{{\rm{MP}}}^{4}\right\|$	$\left\|{{\rm{MP}}}_{{\rm{dup}}}^{4}\right\|$	Ratio
3×n	$\left\|{\rm{MP}}\right\|$	$\left\|{{\rm{MP}}}^{4}\right\|$	$\left\|{{\rm{MP}}}_{{\rm{dup}}}^{4}\right\|$	${T}_{{\rm{Chen}}}/T$	${T}_{{\rm{Xu}}}/T$
3×3	12	345	1166	2.4195	1.0318
3×4	38	5020	39932	6.0711	1.6278
3×5	125	78884	1460928	38.2126	6.8699
3×6	414	750231	41687596	47.6668	9.7894

Search for d-MPs without duplicates in two-terminal multistate networks based on MPs

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 10

References 30

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	ZHANG Ao, Zhihua WANG, Qiong WU, Chengrui LIU. Generalized degradation reliability model considering phase transition [J]. Journal of Systems Engineering and Electronics, 2022, 33(3): 748-758.
[2]	Xiaomei LIU, Naiming XIE. Grey-based approach for estimating software reliability under nonhomogeneous Poisson process [J]. Journal of Systems Engineering and Electronics, 2022, 33(2): 360-369.
[3]	Ying CHEN, Yanfang WANG, Song YANG, Rui KANG. System reliability evaluation method considering physical dependency with FMT and BDD analytical algorithm [J]. Journal of Systems Engineering and Electronics, 2022, 33(1): 222-232.
[4]	Yun LI, Kaige JIANG, Ting ZENG, Wenbin CHEN, Xiaoyang LI, Deyong LI, Zhiqiang ZHANG. Belief reliability modeling and analysis for planetary reducer considering multi-source uncertainties and wear [J]. Journal of Systems Engineering and Electronics, 2021, 32(5): 1246-1262.
[5]	Qingan QIU, Lirong CUI. Reliability modelling based on dependent two-stage virtual age processes [J]. Journal of Systems Engineering and Electronics, 2021, 32(3): 711-721.
[6]	Junliang LI, Yueliang CHEN, Yong ZHANG, Zhuzhu ZHANG, Weijie FAN. Availability modelling for periodically inspected systems under mixed maintenance policies [J]. Journal of Systems Engineering and Electronics, 2021, 32(3): 722-730.
[7]	Tianpei ZU, Rui KANG, Meilin WEN. Graduation formula: a new method to construct belief reliability distribution under epistemic uncertainty [J]. Journal of Systems Engineering and Electronics, 2020, 31(3): 626-633.
[8]	Tao WANG, Jinyan CAI, Yafeng MENG, Sai ZHU. A reliability evaluation method for embryonic cellular array based on Markov status graph model [J]. Journal of Systems Engineering and Electronics, 2020, 31(2): 432-446.
[9]	Junru REN, Wenhao GUI. A statistical inference for generalized Rayleigh model under Type-Ⅱ progressive censoring with binomial removals [J]. Journal of Systems Engineering and Electronics, 2020, 31(1): 206-223.
[10]	Xing PAN, Huixiong WANG, Ye LIN, Tun LIU, Xiaoxia WANG. HEP quantification strategy based on modified CREAM [J]. Journal of Systems Engineering and Electronics, 2019, 30(4): 815-822.
[11]	Xujun SU, Xuezhi LYU. Reliability simulation and analysis of phased-mission system with multiple states [J]. Journal of Systems Engineering and Electronics, 2019, 30(3): 624-632.
[12]	Xu Wang, Quan Sun. Consistency check of degradation mechanism between natural storage and enhancement test for missile servo system [J]. Journal of Systems Engineering and Electronics, 2019, 30(2): 415-424.
[13]	Yuehua CHENG, Liang JIANG, Bin JIANG, Ningyun LU. Useful life prediction using a stochastic hybrid automata model for an ACS multi-gyro subsystem [J]. Journal of Systems Engineering and Electronics, 2019, 30(1): 154-166.
[14]	Chengkun LUO, Yunxiang CHEN, Huachun XIANG, Weijia WANG, Zezhou WANG. Evidence combination method in time domain based on reliability and importance [J]. Journal of Systems Engineering and Electronics, 2018, 29(6): 1308-1316.
[15]	Qiang QIN, Yunwen FENG, Feng LI. Structural reliability analysis using enhanced cuckoo search algorithm and artificial neural network [J]. Journal of Systems Engineering and Electronics, 2018, 29(6): 1317-1326.