A Comparative Study of Different Approaches for Finding the Upper Boundary Points in Stochastic-Flow Networks

A Comparative Study of Different Approaches for Finding the Upper Boundary Points in Stochastic-Flow Networks

Seyed Mehdi Mansourzadeh (Department of Mathematics, University of Mazandaran, Babolsar, Iran), Seyed Hadi Nasseri (Department of Mathematics, University of Mazandaran, Babolsar, Iran), Majid Forghani-elahabad (Faculty of Mathematical Sciences, Sharif University of Technology, Tehran, Iran) and Ali Ebrahimnejad (Department of Mathematics, Qaemshahr Branch, Islamic Azad University, Qaemshahr, Iran)
Copyright: © 2014 |Pages: 11
DOI: 10.4018/ijeis.2014070102
OnDemand PDF Download:
No Current Special Offers


An information system network (ISN) can be modeled as a stochastic-flow network (SFN). There are several algorithms to evaluate reliability of an SFN in terms of Minimal Cuts (MCs). The existing algorithms commonly first find all the upper boundary points (called d-MCs) in an SFN, and then determine the reliability of the network using some approaches such as inclusion-exclusion method, sum of disjoint products, etc. However, most of the algorithms have been compared via complexity results or through one or two benchmark networks. Thus, comparing those algorithms through random test problems can be desired. Here, the authors first state a simple improved algorithm. Then, by generating a number of random test problems and implementing the algorithms in MATLAB, the proposed algorithm is demonstrated to be more efficient than some existing ones in medium-sized networks. The performance profile introduced by Dolan and More is used for analyzing the output of programs.
Article Preview

1. Introduction

The concept of reliability for a network is less than 80 years old (Rausand & Hoyland, 1994). In a binary-state information system, each arc/node and so the network has two states, functional (working state) and failed. In such a system, reliability is the probability that the system is functional. Several algorithms have been proposed to evaluate the reliability of a binary-state network (Buzacott & Chang, 1984; Kuo et al., 1994). However, there are a variety of real-life networks whose arcs or nodes have more than two states, and so a binary-state does not seem to be reasonable to return certain real-world systems. The system reliability of a multi-state information system network is the probability that at least d units of data can be sent through the system from the source node to the sink node. Recently, system reliability theory has extensively been applied to a variety of real-world systems such as information systems (Bargiela et.al, 2006), computer and communication (Ramirez-Marquez, 2005), neural system (Alam et al., 2006; Jenab et al., 2013), transportation (Laframboise & Reyes, 2007) etc. The network reliability problem is NP-hard (Ball, 1980).

In the most proposed algorithm in recent years, the system reliability has been computed in terms of either upper boundary points for demand level d, called d-MinCuts (d-MCs) (Forghani & Mahdavi, 2013a,b; Forghani & Mahvadi-Amiri, 2010; Forghani & Mahvadi-Amiri, 2014; Jane et al., 1993; Lin, 2002; Salehi & Forghani, 2009; Yan & Qian, 2007; Yeh, 2002; Yeh, 2008;) or lower boundary points for demand level d, called d-MinPaths (d-MPs) (Lin et al., 1995). Since the number of MCs is usually less than the number of MPs (Rubino, 1998), working on MCs is preferred. Jane et al. (1993) introduced the notion of d-MC candidate and then proposed an algorithm (denoted by Algorithm 1 here). Algorithm 1 first finds all the d-MC candidates obtained from each minimal cut (MC) and then checks every candidate for being a d-MC. Demonstrating the maxi-mal vectors of all the candidates equal to d-MCs, Lin (2002) proposed a different algorithm (denoted by Algorithm 2 here). Algorithm 2 uses a comparative method to determine the set of maximal elements, d-MCs, among all the d-MC candidates. Employing the max-ow algorithm and the residual network (Ahuja, 1993), Yeh (2002) presented an algorithm that checks every d-MC candidate for being a d-MC. Proving some new results, Yan and Qian (2007) proposed an improved algorithm (denoted by Algorithm 3 here). Algorithm 3 is more efficient than algorithms 1 and 2 (Yan & Qian, 2007). For the first time, Yeh (2008) proposed an algorithm (denoted by Algorithm 4 here) that avoided the production of the duplicate d-MCs. In fact, Algorithm 4 finds all the d-MCs without any duplicate. Salehi-Fathabadi and Forghani (2009) proposed an algorithm merely in accordance with the de_nition of d-MC. Forghani and Mahdavi-Amiri (2013a) presented some new results to decrease the number of candidates and to avoid generation of duplicate d-MCs. Then, they proposed an improved algorithm to search for and determine all the d-MCs. However, in all the proposed works in (Forghani & Mahvadi, 2013a; Jane et al., 1993; Lin, 2002; Yan & Qian, 2007; Yeh, 2002; Yeh, 2008;), there are not any comparisons via generating a number of random test problems. Thus, the need for comparing those algorithms through the CPU time arises.

Complete Article List

Search this Journal:
Volume 18: 4 Issues (2022): Forthcoming, Available for Pre-Order
Volume 17: 4 Issues (2021)
Volume 16: 4 Issues (2020)
Volume 15: 4 Issues (2019)
Volume 14: 4 Issues (2018)
Volume 13: 4 Issues (2017)
Volume 12: 4 Issues (2016)
Volume 11: 4 Issues (2015)
Volume 10: 4 Issues (2014)
Volume 9: 4 Issues (2013)
Volume 8: 4 Issues (2012)
Volume 7: 4 Issues (2011)
Volume 6: 4 Issues (2010)
Volume 5: 4 Issues (2009)
Volume 4: 4 Issues (2008)
Volume 3: 4 Issues (2007)
Volume 2: 4 Issues (2006)
Volume 1: 4 Issues (2005)
View Complete Journal Contents Listing