IDEAS home Printed from https://ideas.repec.org/a/eee/reensy/v260y2025ics095183202500119x.html
   My bibliography  Save this article

GE-MBAT: An efficient algorithm for reliability assessment in multi-state flow networks

Author

Listed:
  • Hao, Zhifeng
  • Yeh, Wei-Chang

Abstract

Multi-state flow networks are increasingly critical across diverse applications such as network resilience, Internet of Things (IoT), and facility networks. These networks provide a more realistic representation of operational environments compared to binary-state models. Ensuring reliable network performance is crucial for the continuous and effective operation of these multi-state flow networks, especially as they grow in complexity. However, assessing reliability presents significant challenges due to the computational complexity involved. This paper introduces the "Greater than or Equal to" Multi-State Binary-Addition-Tree (GE-MBAT), designed to identify all vectors X of which (the maximum flow in the subgraph resulting from X) ≥ d rather than generating all possible multi-state vectors to enhance the efficiency and accuracy of reliability calculations in multi-state networks. The GE-MBAT reduces the generation of infeasible vectors, outperforming traditional methods in computational efficiency. This research contributes to the development of more reliable and robust network systems, with significant implications for critical infrastructure and advanced network technologies.

Suggested Citation

  • Hao, Zhifeng & Yeh, Wei-Chang, 2025. "GE-MBAT: An efficient algorithm for reliability assessment in multi-state flow networks," Reliability Engineering and System Safety, Elsevier, vol. 260(C).
    • Handle: RePEc:eee:reensy:v:260:y:2025:i:c:s095183202500119x
    DOI: 10.1016/j.ress.2025.110916
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S095183202500119X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ress.2025.110916?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Yeh, Wei-Chang & Tan, Shi-Yi & Zhu, Wenbo & Huang, Chia-Ling & Yang, Guang-yi, 2022. "Novel binary addition tree algorithm (BAT) for calculating the direct lower-bound of the highly reliable binary-state network reliability," Reliability Engineering and System Safety, Elsevier, vol. 223(C).
    2. Watson, Bryan C & Morris, Zack B & Weissburg, Marc & Bras, Bert, 2023. "System of system design-for-resilience heuristics derived from forestry case study variants," Reliability Engineering and System Safety, Elsevier, vol. 229(C).
    3. Lu, Qing-Chang & Li, Jing & Xu, Peng-Cheng & Zhang, Lei & Cui, Xin, 2024. "Modeling cascading failures of urban rail transit network based on passenger spatiotemporal heterogeneity," Reliability Engineering and System Safety, Elsevier, vol. 242(C).
    4. Yeh, Wei-Chang, 2021. "Novel binary-addition tree algorithm (BAT) for binary-state network reliability problem," Reliability Engineering and System Safety, Elsevier, vol. 208(C).
    5. Yeh, Wei-Chang, 2021. "A quick BAT for evaluating the reliability of binary-state networks," Reliability Engineering and System Safety, Elsevier, vol. 216(C).
    6. Hui Wu & Yan-Fu Li, 2024. "A multi-sensor fusion-based prognostic model for systems with partially observable failure modes," IISE Transactions, Taylor & Francis Journals, vol. 56(6), pages 624-637, June.
    7. Forghani-elahabad, Majid & Yeh, Wei-Chang, 2022. "An improved algorithm for reliability evaluation of flow networks," Reliability Engineering and System Safety, Elsevier, vol. 221(C).
    8. Yao, Jinyong & Gao, Zhanfei & He, Yihai & Peng, Chong, 2024. "Integrated mission reliability modeling for multistate manufacturing systems considering heterogeneous feedstocks based on extended stochastic flow manufacturing network," Reliability Engineering and System Safety, Elsevier, vol. 243(C).
    9. Koutras, Vasilis P., 2023. "A Markov Regenerative Process Model for the Dependability and Performance of a Two-Unit Multi-State System under Maintenance," Reliability Engineering and System Safety, Elsevier, vol. 238(C).
    10. Xia, Weifu & Wang, Yanhui & Hao, Yucheng & He, Zhichao & Yan, Kai & Zhao, Fan, 2024. "Reliability analysis for complex electromechanical multi-state systems utilizing universal generating function techniques," Reliability Engineering and System Safety, Elsevier, vol. 244(C).
    11. Yeh, Wei-Chang & Tan, Shi-Yi & Forghani-elahabad, Majid & Khadiri, Mohamed El & Jiang, Yunzhi & Lin, Chen-Shiun, 2022. "New binary-addition tree algorithm for the all-multiterminal binary-state network reliability problem," Reliability Engineering and System Safety, Elsevier, vol. 224(C).
    12. Yeh, Wei-Chang, 2023. "Novel recursive inclusion-exclusion technology based on BAT and MPs for heterogeneous-arc binary-state network reliability problems," Reliability Engineering and System Safety, Elsevier, vol. 231(C).
    13. Yeh, Wei-Chang & Chu, Ta-Chung, 2018. "A novel multi-distribution multi-state flow network and its reliability optimization problem," Reliability Engineering and System Safety, Elsevier, vol. 176(C), pages 209-217.
    14. Yeh, Wei-Chang & Du, Chia-Ming & Tan, Shi-Yi & Forghani-elahabad, Majid, 2023. "Application of LSTM based on the BAT-MCS for binary-state network approximated time-dependent reliability problems," Reliability Engineering and System Safety, Elsevier, vol. 235(C).
    15. Majid Forghani-Elahabad & Nezam Mahdavi-Amiri & Nelson Kagan, 2020. "On multi-state two separate minimal paths reliability problem with time and budget constraints," International Journal of Operational Research, Inderscience Enterprises Ltd, vol. 37(4), pages 479-490.
    16. Yeh, Wei-Chang, 2024. "A new hybrid inequality BAT for comprehensive all-level d-MP identification using minimal paths in Multistate Flow Network reliability analysis," Reliability Engineering and System Safety, Elsevier, vol. 244(C).
    17. Liu, Tao & Bai, Guanghan & Tao, Junyong & Zhang, Yun-An & Fang, Yining, 2024. "A Multistate Network Approach for Resilience Analysis of UAV Swarm considering Information Exchange Capacity," Reliability Engineering and System Safety, Elsevier, vol. 241(C).
    18. Hao, Zhifeng & Yeh, Wei-Chang & Tan, Shi-Yi, 2021. "One-batch preempt deterioration-effect multi-state multi-rework network reliability problem and algorithms," Reliability Engineering and System Safety, Elsevier, vol. 215(C).
    19. Zhang, Hanxiao & Sun, Muxia & Li, Yan-Fu, 2022. "Reliability–redundancy allocation problem in multi-state flow network: Minimal cut-based approximation scheme," Reliability Engineering and System Safety, Elsevier, vol. 225(C).
    20. Cao, Yingsai & Lu, Chen & Dong, Wenjie, 2024. "Importance measures for multi-state systems with multiple components under hierarchical dependences," Reliability Engineering and System Safety, Elsevier, vol. 248(C).
    21. Kozyra, Paweł Marcin, 2024. "A parallel algorithm for reliability assessment of multi-state flow networks based on simultaneous finding of all multi-state minimal paths and performing state space decomposition," Reliability Engineering and System Safety, Elsevier, vol. 251(C).
    22. Yeh, Wei-Chang, 2021. "Novel Algorithm for Computing All-Pairs Homogeneity-Arc Binary-State Undirected Network Reliability," Reliability Engineering and System Safety, Elsevier, vol. 216(C).
    23. Yeh, Wei-Chang, 2022. "Novel self-adaptive Monte Carlo simulation based on binary-addition-tree algorithm for binary-state network reliability approximation," Reliability Engineering and System Safety, Elsevier, vol. 228(C).
    24. Majid Forghani-elahabad & Omar Mutab Alsalami, 2023. "Using a Node–Child Matrix to Address the Quickest Path Problem in Multistate Flow Networks under Transmission Cost Constraints," Mathematics, MDPI, vol. 11(24), pages 1-15, December.
    25. Yeh, Wei-Chang, 2023. "Building reliable budget-based binary-state networks," Reliability Engineering and System Safety, Elsevier, vol. 240(C).
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Yeh, Wei-Chang, 2025. "Enhancing reliability calculation for one-output k-out-of-n binary-state networks using a new BAT," Reliability Engineering and System Safety, Elsevier, vol. 257(PA).
    2. Yeh, Wei-Chang, 2024. "Time-reliability optimization for the stochastic traveling salesman problem," Reliability Engineering and System Safety, Elsevier, vol. 248(C).
    3. Wu, Baichao, 2024. "A novel scanline algorithm for generating ordered variables," Reliability Engineering and System Safety, Elsevier, vol. 252(C).
    4. Yeh, Wei-Chang, 2024. "A new hybrid inequality BAT for comprehensive all-level d-MP identification using minimal paths in Multistate Flow Network reliability analysis," Reliability Engineering and System Safety, Elsevier, vol. 244(C).
    5. Yeh, Wei-Chang, 2022. "Novel direct algorithm for computing simultaneous all-level reliability of multistate flow networks," Reliability Engineering and System Safety, Elsevier, vol. 225(C).
    6. Yeh, Wei-Chang & Du, Chia-Ming & Tan, Shi-Yi & Forghani-elahabad, Majid, 2023. "Application of LSTM based on the BAT-MCS for binary-state network approximated time-dependent reliability problems," Reliability Engineering and System Safety, Elsevier, vol. 235(C).
    7. Yeh, Wei-Chang, 2022. "Novel self-adaptive Monte Carlo simulation based on binary-addition-tree algorithm for binary-state network reliability approximation," Reliability Engineering and System Safety, Elsevier, vol. 228(C).
    8. Wu, Baichao & Sun, Long, 2024. "A novel layer-by-layer recursive decomposition algorithm for calculation of network reliability," Reliability Engineering and System Safety, Elsevier, vol. 244(C).
    9. Yeh, Wei-Chang & Tan, Shi-Yi & Forghani-elahabad, Majid & Khadiri, Mohamed El & Jiang, Yunzhi & Lin, Chen-Shiun, 2022. "New binary-addition tree algorithm for the all-multiterminal binary-state network reliability problem," Reliability Engineering and System Safety, Elsevier, vol. 224(C).
    10. Niu, Yi-Feng & Xiang, Hai-Yan & Xu, Xiu-Zhen, 2024. "Expected performance evaluation and optimization of a multi-distribution multi-state logistics network based on network reliability," Reliability Engineering and System Safety, Elsevier, vol. 251(C).
    11. Yeh, Wei-Chang & Tan, Shi-Yi & Zhu, Wenbo & Huang, Chia-Ling & Yang, Guang-yi, 2022. "Novel binary addition tree algorithm (BAT) for calculating the direct lower-bound of the highly reliable binary-state network reliability," Reliability Engineering and System Safety, Elsevier, vol. 223(C).
    12. Huang, Ding-Hsiang, 2024. "An algorithm to generate all d-lower boundary points for a stochastic flow network using dynamic flow constraints," Reliability Engineering and System Safety, Elsevier, vol. 249(C).
    13. Davila-Frias, Alex & Yodo, Nita & Le, Trung & Yadav, Om Prakash, 2023. "A deep neural network and Bayesian method based framework for all-terminal network reliability estimation considering degradation," Reliability Engineering and System Safety, Elsevier, vol. 229(C).
    14. Yeh, Wei-Chang & Zhu, Wenbo & Tan, Shi-Yi & Wang, Gai-Ge & Yeh, Yuan-Hui, 2022. "Novel general active reliability redundancy allocation problems and algorithm," Reliability Engineering and System Safety, Elsevier, vol. 218(PA).
    15. Zhang, Shuai & Bai, Guanghan & Tao, Junyong & Wang, Yang & Xu, Bei, 2025. "An algorithm to search for multi-state minimal cuts in multi-state flow networks containing state heterogeneous components," Reliability Engineering and System Safety, Elsevier, vol. 256(C).
    16. Chen, Liwei & Cheng, Chunchun & Dui, Hongyan & Xing, Liudong, 2022. "Maintenance cost-based importance analysis under different maintenance strategies," Reliability Engineering and System Safety, Elsevier, vol. 222(C).
    17. Yeh, Wei-Chang, 2023. "Novel recursive inclusion-exclusion technology based on BAT and MPs for heterogeneous-arc binary-state network reliability problems," Reliability Engineering and System Safety, Elsevier, vol. 231(C).
    18. Zhou, Xinxin & Huang, Yun & Bai, Guanghan & Xu, Bei & Tao, Junyong, 2024. "The resilience evaluation of unmanned autonomous swarm with informed agents under partial failure," Reliability Engineering and System Safety, Elsevier, vol. 244(C).
    19. Shi, Yan & Behrensdorf, Jasper & Zhou, Jiayan & Hu, Yue & Broggi, Matteo & Beer, Michael, 2024. "Network reliability analysis through survival signature and machine learning techniques," Reliability Engineering and System Safety, Elsevier, vol. 242(C).
    20. Yeh, Wei-Chang & Hao, Zhifeng & Forghani-elahabad, Majid & Wang, Gai-Ge & Lin, Yih-Lon, 2021. "Novel Binary-Addition Tree Algorithm for Reliability Evaluation of Acyclic Multistate Information Networks," Reliability Engineering and System Safety, Elsevier, vol. 210(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:reensy:v:260:y:2025:i:c:s095183202500119x. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: https://www.journals.elsevier.com/reliability-engineering-and-system-safety .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.