Article Preview
Top1. 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.