Usage of task and data parallelism for finding the lower boundary vectors in a stochastic-flow network

Majid Forghani-elahabad and Emilio Francesquini

Reliability Engineering and System Safety, 2023, vol. 238, issue C

Abstract: In a stochastic-flow network, a minimal system state vector under which the maximum flow of the network from a source node to a destination node is equal to d is called a lower boundary vector (LBV). As the number of LBVs increases exponentially with the size of the network, the available algorithms in the literature could be improved to be more practical for real-world large-sized systems. We employ task and data parallelism to propose an efficient algorithm for determining all the LBVs to tackle this problem. We present an efficient approach for removing duplicate solutions to improve an available algorithm to find all the LBVs. We show the correctness and compute the complexity results of the proposed approach and demonstrate its efficiency. Then, we propose vectorized, parallelized, and vectorized–parallelized versions of the main algorithm. We illustrate the standard version through a benchmark example and discuss the other proposed versions’ correctness. We conduct several experimental results on two known benchmark networks and more than one thousand random problems to demonstrate the practical efficiency of the vectorized–parallelized version. Moreover, Dolan and Moré’s performance profile is used to provide a more intuitive comparison between all four versions.

Keywords: Multistate flow networks; Lower boundary vectors; System reliability; Parallelization and vectorization techniques (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0951832023003319
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:238:y:2023:i:c:s0951832023003319

DOI: 10.1016/j.ress.2023.109417

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 ().