A generalized model to generate d-MP for a multi-state flow network. (May 2023)

• Record Type: Journal Article
• Authors: Huang, Ding-Hsiang
• Is Part Of: Computers & industrial engineering. Volume 179(2023)
• Publication Date: 2023-05
• Subjects: Network reliability -- D-MP -- Multi-state flow networks (MSFN) -- Generalized MSFN model, linear time complexity; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2023.109205
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: A MSFN model is developed to generate all d -MP. A property that any d -MP is acyclic is proved. The acyclic check is formulated for improving the d -MP generation. Recursive procedures are proposed to achieve the MSFN model. Experiments show the superiority of the d -MP generation by the MSFN model. Abstract: Network reliability is defined as the probability that a demand d can successfully be sent through a multi-state flow network (MSFN). Several practical systems, including manufacturing, supply chain, and computer networks, can be modeled as the MSFN for evaluating network reliability. Calculating network reliability belongs to an NP-hard problem. Existing algorithms based on minimal paths (MP) are developed to systematically obtain all d -MP for the further network reliability evaluation. The d -MP are minimal necessary capacity-state vectors for a demand level d in short. When facing more complex and practical MSFN, we always have a motivation to improve the efficiency to calculate network reliability by generating all the d -MP. A generalized MSFN model is proposed in this study to generate all the d -MP efficiently. All the solutions satisfying the constructed formulations are all the d -MP. That is, the evaluation of the network reliability can be accelerated based on the solutions generated from the proposed model. Besides, recursive procedures with a demonstrated example are provided to offer hints to implement the proposed model. Numerical experiments, including the MSFN from references and random generation, and time complexity analysis are conducted to show that the improvement of the d -MP generation by using the proposed generalized MSFN model, compared with the existing algorithm with the linear time complexity.