An algorithm to generate all d-lower boundary points for a stochastic flow network using dynamic flow constraints

Ding-Hsiang Huang

Reliability Engineering and System Safety, 2024, vol. 249, issue C

Abstract: Several practical systems, including manufacturing and computer networks, can be modeled as stochastic flow networks (SFNs). In order to learn the performance of the SFNs, network reliability is defined as the probability that a demand d can successfully be transmitted through an SFN. Nevertheless, calculating network reliability belongs to an NP-hard problem. For further probability evaluation (network reliability), existing algorithms based on minimal paths (MPs) are developed to systematically obtain all lower boundary points for d termed d-LBPs. When facing more complex SFNs, our perpetual motivation lies in enhancing the efficiency of generating all d-LBPs. Based on the dominant property of capacity constraints over flow constraints, this study develops a series of techniques to dynamically adjust the flow constraints to generate available (remaining) capacity state vectors. All the generated solutions would directly satisfy the capacity constraints, ignoring the flow constraints. Besides, the exact d-LBPs are calculated using element-wise addition and cycle check constraints. An algorithm is collected with an illustrative example. Furthermore, numerical experiments, including a practical network, are conducted to show at least two times faster for the d-LBP generation using the proposed algorithm compared with the newest algorithm.

Keywords: Network reliability; d-Lower Boundary Points (d-LBPs); Stochastic Flow Networks (SFNs); Dynamic flow constraints (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0951832024002904
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:reensy:v:249:y:2024:i:c:s0951832024002904

DOI: 10.1016/j.ress.2024.110217

Access Statistics for this article

Reliability Engineering and System Safety is currently edited by Carlos Guedes Soares

More articles in Reliability Engineering and System Safety from Elsevier
Bibliographic data for series maintained by Catherine Liu ().