An efficient algorithm for the multi-state two separate minimal paths reliability problem with budget constraint

Majid Forghani-elahabad and Nezam Mahdavi-Amiri

Reliability Engineering and System Safety, 2015, vol. 142, issue C, 472-481

Abstract: Several researchers have worked on transmitting a given amount of flow through a network flow within fastest possible time, allowing flow to be transmitted through one or more paths. Extending this problem to the system reliability problem, the quickest path reliability problem has been introduced. The problem evaluates the probability of transmitting some given amount of flow from a source node to a sink node through a single minimal path in a stochastic-flow network within some specified units of time. Later, the problem has been extended to allow flow to be transmitted through two or more separate minimal paths (SMPs). Here, we consider the problem of sending flow through two SMPs with budget constraint. Presenting some new results, an efficient algorithm is proposed to solve the problem. The algorithm is illustrated through a benchmark ARPANET example. Computing complexity results, the algorithm is shown to be significantly more efficient than the existing ones. We also state how the optimal two SMPs with the best system reliability can be determined based on our proposed algorithm. Finally, testing on more than 10000 generated random test problems, the practical efficiency of our algorithm is demonstrated in comparison with a recently proposed algorithm.

Keywords: Stochastic quickest path problem; Transmission time; Budget constraint; Minimal paths (MPs); (d,T,b,P1,P2)-MP (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0951832015001878
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:142:y:2015:i:c:p:472-481

DOI: 10.1016/j.ress.2015.06.012

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