A simple algorithm for evaluating the k-out-of-n network reliability

Evaluating the network reliability is an important topic in the planning, designing, and control of systems. The minimal cut set (MC, an edge set) is one of the major and fundamental tools for evaluating network reliability. A k-out-of-n MC is a special MC in a k-out-of-n network in which some nodes must receive at least k flows from their n input edges, where k is an integer number between 1 and n. In this study, an alternative method is given first to define a MC using a node set (called MCN) in k-out-of-n networks. A very simple algorithm based on some intuitive theorems that characterize the structure of the MCN and the relationship between MC and MCN is developed to solve the k-out-of-n network reliability by finding the k-out-of-n MCs between two special nodes. The proposed algorithm is not only easier to understand and implement, but is also better than the existing algorithm. The correctness of the proposed algorithm will be analyzed and proven. Two examples are illustrated to show how all k-out-of-n MCs are generated and verified in a k-out-of-n network using the proposed algorithm. The reliability of one example is then computing using one example.     

Search for all MCs in networks with unreliable nodes and arcs

A simple method is proposed to search for all minimal cutsets (MCs ) for imperfect networks reliability subject to both arc and node failures under the condition that all of the MCs in the network with perfect nodes are given in advance. The proposed method does not require re-enumeration for all of the MCs for additional node failure consideration. All of the MC candidates found in the proposed algorithm are actual MCs without any need for further verification. This algorithm is more effective than the existing algorithm in which every MC candidate is not verified as a MC. No identical MCs are found using the proposed algorithm, which does not duplicate MCs and is more efficient than the existing methods. Only simple concepts are used to implement the proposed algorithm, which makes it easier to understand and implement. With considering unreliable nodes, the proposed method is also more realistic and valuable for reliability analysis in an existing network. The correctness of the proposed algorithm will be analyzed and proven. One example is used to illustrate how all MCs are generated in a network with arc and node failures solved using the proposed algorithm.     

A simple approach to search for all d-MCs of a limited-flow network

Many real-world systems are multistate systems composed of multistate components in which the reliability can be computed in terms of the lower bound points of level d, called d-MCs. Such systems (electric power, transportation, etc.) may be regarded as flow networks whose arcs have independent, discrete, limited and multivalued random capacities. In this study, all MCs are assumed to be known in advance and we focused on how to find the entire d-MCs before calculating the reliability value of a network. Just based on the definition of d-MC, we develop an intuitive algorithm which is better than the best-known existing method. Analysis of our algorithm and comparison to existing algorithms shows that our proposed method is easier to understand and implement. Finally, the computational complexity of the proposed algorithm is analysed and compared with the existing methods.     

Reliability-oriented multi-resource allocation in a stochastic-flow network

A stochastic-flow network consists of a set of nodes, including source nodes which supply various resources and sink nodes at which resource demands take place, and a collection of arcs whose capacities have multiple operational states. The network reliability of such a stochastic-flow network is the probability that resources can be successfully transmitted from source nodes through multi-capacitated arcs to sink nodes. Although the evaluation schemes of network reliability in stochastic-flow networks have been extensively studied in the literature, how to allocate various resources at source nodes in a reliable means remains unanswered. In this study, a resource allocation problem in a stochastic-flow network is formulated that aims to determine the optimal resource allocation policy at source nodes subject to given resource demands at sink nodes such that the network reliability of the stochastic-flow network is maximized, and an algorithm for computing the optimal resource allocation is proposed that incorporates the principle of minimal path vectors. A numerical example is given to illustrate the proposed algorithm.     

A new algorithm for generating minimal cut sets in k-out-of-n networks

Evaluating the network reliability is an important topic in the planning, designing, and control of systems. A k-out-of-n network is a special network in that some nodes must receive at least k (>1) flows from all of their input edges (n). In real-life cases, many networks such as computer and telecommunications include k-out-of-n nodes for redundancy. The minimal-cut-node-set (MCN) is the major and fundamental tools for evaluating the k-out-of-n network reliability. In this study, a very simple algorithm based on some intuitive theorems that characterize the structure of the MCN is developed to solve the k-out-of-n network reliability. Compared to the existing algorithms, the proposed algorithm generates all k-out-of-n MCs without duplication based on fewer MCNs and fewer (k-out-of-n MC) candidates. The proposed algorithm is not only easier to understand and implement, but is also better than the existing algorithms. The correctness of the proposed algorithm will be analyzed and proven. One example is illustrated to show how all k-out-of-n MCs are generated, verified, and implemented to evaluate the k-out-of-n network reliability using the proposed algorithm.     

Improving efficiency of solving d-MC problem in stochastic-flow network

Solving d-MC problem is often a tedious process. Three ways are suggested to improve the efficiency of solving d-MC problem. The first way is to make the best use of some special properties of network. A property of Network with Joint Parallel Part, which is more common than series–parallel network, is illustrated. The second way is to reduce the number of d-MC candidates and then to reduce the cost of testing. Two theorems on how to find the d-MCs with only one element unsaturated and on how to set the Lower Capacity Limits (LCLs) of elements to some values higher than zero are proved. These two theorems will be helpful to reduce d-MC candidates without any loss of real d-MC. The third way is to efficiently remove the duplicated d-MCs. A theorem, elucidating which Minimal Cuts (MCs) the duplicated d-MCs will be generated from, is proved. Finally, an algorithm is proposed by adding a pre-numerating step to the algorithm presented in Yeh [A new approach to the d-MC problem. Reliab Eng Syst Safety 2002;77(2):201–6], and two examples are employed to illustrate the proposed algorithm, especially the pre-numerating step.     

A path-based algorithm for evaluating the k-out-of-n flow network reliability

Evaluating the network reliability is an important topic in the planning, designing and control of systems. The minimal path (MP, an edge set) set is one of the major, fundamental tools for evaluating network reliability. A k-out-of-n MP is a union of some MPs in a k-out-of-n flow network in which some nodes must receive flows from their k input distinctive edges (each input edge has one flow) to generate one flow, where k is an integer number between 2 and n. In this study, a very simple a-lgorithm based on some intuitive theorems that characterize the k-out-of-n MP structure and the relationship between k-out-of-n MPs and k-out-of-n MP candidates is developed to solve the k-out-of-n flow network reliability by finding the k-out-of-n MPs between two special nodes. The proposed algorithm is easier to understand and implement. The correctness of the proposed algorithm will be analyzed and proven. One example is illustrated to show how all k-out-of-n MPs are generated and verified in a k-out-of-n flow network using the proposed algorithm. The reliability of one example is then computing using the same example.     

Using minimal cuts to evaluate the system reliability of a stochastic-flow network with failures at nodes and arcs

This paper deals with a stochastic-flow network in which each node and arc has a designated capacity, which will have different lower levels due to various partial and complete failures. We try to evaluate the system reliability that the maximum flow of the network is not less than a demand (d+1). A simple algorithm in terms of minimal cuts is first proposed to generate all upper boundary points for d, and then the system reliability can be calculated in terms of such points. The upper boundary point for d is a maximal vector, which represents the capacity of each component (arc or node), such that the maximum flow of the network is d. A computer example is shown to illustrate the solution procedure.     

A simple minimal path method for estimating the weighted multi-commodity multistate unreliable networks reliability

The weighted multicommodity multistate unreliable network (WMMUN) is a novel network composed of multistate unreliable components (arcs and nodes) capable of transmitting different types of commodities in which capacity weight varies with components. It is an extension of the multistate network. The current method for evaluating the directed WMMUN reliability has been derived from minimal cut (MC) based algorithm. The existing best-known method needed extensive comparison and verification, and failed to find the real directed WMMUN reliability. A very simple algorithm based on minimal paths (MPs) is developed for the WMMUN reliability problem. The correctness and computational complexity of the proposed algorithm will be analyzed and proven. An example is given to illustrate how the WMMUN reliability is evaluated using the proposed algorithm. The relationships among all different versions of MPs are also clarified.     

Multistate-node acyclic networks reliability evaluation based on MC

A multistate-node acyclic network (MNAN) is a generalization of the tree-structured multistate-node system that does not satisfy the flow conservation law. The current known existing methods used to evaluate MNAN reliability are based on the minimal tree (MT) set. Instead of using the MT, an intuitive algorithm was developed in this to find the minimal cut (MC) set. The MNAN reliability can then be computed in terms of MCs. The proposed algorithm is simpler and more efficient compared to the best-known existing methods. The computational complexity of the proposed algorithm is analyzed and compared with the best-known existing methods. One example is used to show how all MCs are generated using the proposed algorithm. The corresponding reliabilities in this example are computed.     

A simple algorithm to generate all (d,B)-MCs of a multicommodity stochastic-flow network

Both minimal paths and minimal cuts are important media to evaluate the performance indexes, the system reliability or unreliability, for a single-commodity stochastic-flow network. This paper concentrates on a multicommodity stochastic-flow network in which each arc has both the capacity and cost attributes. Different from the single-commodity case, the system capacity is a pattern for multicommodity case. Since the traditional performance indexes are not suitable for multicommodity case, we propose a new performance index, the probability that the system capacity is less than or equal to a given pattern under the budget constraint. A simple algorithm based on minimal cuts is presented to generate all (d,B)-MCs that are the maximal capacity vectors meeting the demand d and budget B. The proposed performance index can be evaluated in terms of (d,B)-MCs.     

Evaluation of the reliability of transport networks based on the stochastic flow of moving objects

In transport networks, human beings are moving objects whose moving direction is stochastic in emergency situations. Based on this idea, a new model—stochastic moving network (SMN) is proposed. It is different from binary-state networks and stochastic-flow networks. The flow of SMNs has multiple-saturated states, that correspond to different flow values in each arc. In this paper, we try to evaluate the system reliability, defined as the probability that the saturated flow of the network is not less than a given demand d. Based on this new model, we obtain the flow probability distribution of every arc by simulation. An algorithm based on the blocking cutset of the SMN is proposed to evaluate the network reliability. An example is used to show how to calculate the corresponding reliabilities for different given demands of the SMN. Simulation experiments of different size were made and the system reliability precision was calculated. The precision of simulation results also discussed.     

Minimal cut sets of s–t networks with k-out-of-n nodes

In this paper, we extend traditional directed s–t network by letting nodes have k-out-of-n property: To generate output flows, a node must receive at least k flows from its n input links, where k is an integer assigned for the node and its value can be any number from 1 to n. To evaluate the system reliability, minimal cut sets for the extended network are defined for nodes. Under this definition, an extended network and its sink node have the same minimal cut sets. A new algorithm is designed to generate minimal cut sets for all nodes, starting with the source node and ending with the sink node. With different initializations, the algorithm can be applied for extended s–t networks with or without node failures.     

An improved algorithm for searching all minimal cuts in modified networks

A modified network is an updated network after inserting a branch string (a special path) between two nodes in the original network. Modifications are common for network expansion or reinforcement evaluation and planning. The problem of searching all minimal cuts (MCs) in a modified network is discussed and solved in this study. The existing best-known methods for solving this problem either needed extensive comparison and verification or failed to solve some special but important cases. Therefore, a more efficient, intuitive and generalized method for searching all MCs without an extensive research procedure is proposed. In this study, we first develop an intuitive algorithm based upon the reformation of all MCs in the original network to search for all MCs in a modified network. Next, the correctness of the proposed algorithm will be analyzed and proven. The computational complexity of the proposed algorithm is analyzed and compared with the existing best-known methods. Finally, two examples illustrate how all MCs are generated in a modified network using the information of all of the MCs in the corresponding original network.     

Evaluate the performance of a stochastic-flow network with cost attribute in terms of minimal cuts

This paper proposes a performance index to measure the quality level of a stochastic-flow network in which each node has a designated capacity, which will have different lower levels due to various partial and complete failures. The performance index is the probability that the maximum flow of the network equals the demand d without exceeding the budget b. A simple algorithm in terms of minimal cuts is first proposed to generate all upper boundary points for (d, b), and then the probability that the maximum flow is less than or equal to d can be calculated in terms of such points. The upper boundary point for (d, b) is a maximal vector representing the capacity of each arc such that the maximum flow of the network under the budget b is d. The performance index can be calculated by repeating the proposed algorithm to obtain all upper boundary point for (d−1, b). A benchmark example is shown to illustrate the solution procedure.     

Reliability assessment for a stochastic manufacturing system with reworking actions

This article evaluates the system reliability of a manufacturing system with reworking actions, where the system reliability is an essential indicator to determine whether the manufacturing system is capable or not. Based on the path concept, we transformed the manufacturing system into a stochastic-flow network in which the capacity of each machine is stochastic (i.e., multistate) due to failure, partial failure, and maintenance. In such a manufacturing network, the input flow (raw materials/WIP; work-in-process) processed by each machine might be defective and thus the output flow (WIP/products) would be less than the input amount. To analyze the different sources processed by the manufacturing network, we decomposed the network into one general processing path and several reworking paths by a graphical technique. Subsequently, an algorithm for the manufacturing network was proposed to generate the lower boundary vector which allows sufficient products to satisfy the demand. In terms of such a vector, the system reliability can be derived easily.     

System reliability of a manufacturing network with reworking action and different failure rates

From the perspective of network analysis, the manufacturing system can be constructed as a stochastic-flow network, since the capacity of each machine is stochastic (i.e. multistate) owing to the failure, partial failure, and maintenance. Considering reworking action and different failure rates of machines, the input flow (raw materials/work in process) processed by each machine might be defective, and therefore the output flow (work in process/products) would be less than the input amount. To evaluate the capability of the manufacturing system, we measure the probability that the manufacturing network can satisfy demand. Such a probability is defined as the system reliability. A decomposition method is first proposed to divide the manufacturing network into one general processing path and one reworking path. Subsequently, two algorithms are utilised for different network models to generate the lower boundary vector of machine capacity to guarantee that the manufacturing network is able to produce sufficient products fulfilling the demand. The system reliability of the manufacturing network can be derived in terms of such a capacity vector afterwards.     

Network reliability assessment using a cellular automata approach

Two cellular automata (CA) models that evaluate the s–t connectedness and shortest path in a network are presented. CA based algorithms enhance the performance of classical algorithms, since they allow a more reliable and straightforward parallel implementation resulting in a dynamic network evaluation, where changes in the connectivity and/or link costs can readily be incorporated avoiding recalculation from scratch. The paper also demonstrates how these algorithms can be applied for network reliability evaluation (based on Monte-Carlo approach) and for finding s–t path with maximal reliability.     

Element substitution algorithm for general two-terminal network reliability analyses

The computation of the reliability of two-terminal networks is a classical reliability problem. For these types of problems, one is interested, from a general perspective, in obtaining the probability that two specific nodes can communicate. This paper presents a holistic algorithm for the analysis of general networks that follow a two-terminal rationale. The algorithm is based on a set replacement approach and an element inheritance strategy that effectively obtains the minimal cut sets associated with a given network. The vast majority of methods available for obtaining two-terminal reliability are generally based on assumptions about the performance of the network. Some methods assume network components can be in one of two states: (i) either completely failed; or (ii) perfectly functioning, others usually assume that nodes are perfectly reliable and thus, these methods have to be complemented or transformed to account for node failure, and the remaining methods assume minimal cut sets can be readily computed in order to analyze more complex network and component behavior. The algorithm presented in this paper significantly differs from previous approaches available in the literature in the sense that it is based on a predecessor matrix and an element substitution technique that allows for the exact computation of minimal cut sets and the immediate inclusion of node failure without any changes to the pseudo-code. Several case networks are used to validate and illustrate the algorithms.     

A new reliability evaluation method for networks with imperfect vertices using BDD

As an efficient data structure for representation and manipulation of Boolean functions, binary decision diagrams (BDDs) have been applied to network reliability analysis. However, most of the existing BDD methods on network reliability analysis have assumed perfectly reliable vertices, which is often not true for real‐world networks where the vertices can fail because of factors such as limited resources (eg, power and memory) or harsh operating environments. Extensions have been made to the existing BDD methods (particularly, edge expansion diagram and boundary set–based methods) to address imperfect vertices. But these extended methods have various constraints leading to problems in accuracy or space efficiency. To overcome these constraints, in this paper, we propose a new BDD‐based algorithm called ordered BDD dependency test for K‐terminal network reliability analysis considering both edge and vertex failures. Based on a newly defined concept “dependency set”, the proposed algorithm can accurately compute the reliability of networks with imperfect vertices. In addition, the proposed algorithm has no restrictions on the starting vertex for the BDD model construction. Comprehensive examples and experiments are provided to show effectiveness of the proposed approach.