An efficient algorithm for the multi-state two separate minimal paths reliability problem with budget constraint. (October 2015)

• Record Type: Journal Article
• Authors: Forghani-elahabad, Majid; Mahdavi-Amiri, Nezam
• Is Part Of: Reliability engineering & system safety. Volume 142(2015:Oct.)
• Page Start: 472
• Page End: 481
• Publication Date: 2015-10
• Subjects: Stochastic quickest path problem -- Transmission time -- Budget constraint -- Minimal paths (MPs) -- (d, T, b, P1, P2)-MP; Reliability (Engineering) -- Periodicals; System safety -- Periodicals; Industrial safety -- Periodicals; Fiabilité -- Périodiques; Sécurité des systèmes -- Périodiques; Sécurité du travail -- Périodiques; 620.00452
• DOI: 10.1016/j.ress.2015.06.012
• Languages: English
• ISSNs: 0951-8320

Abstract

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 10 000 generated random test problems, the practical efficiency of our algorithm is demonstrated in comparison with a recently proposed algorithm. Abstract : Highlights: Presenting some new results for 2SMPR problem with budget constraint. Proposing an efficient algorithm to solve the problem. Showing the algorithm to be more efficient than a recently proposed one. Comparing both algorithms through 10 920 randomly generated test problems. Stating an approach to find the optimal 2 SMPs having the highest reliability.