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.     

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.     

An improved sum-of-disjoint-products technique for the symbolic network reliability analysis with known minimal paths

Evaluating the network reliability is an important topic in the planning, designing, and control of systems. The sum-of-disjoint products technique (SDP) is a major fundamental tool for evaluating stochastic network reliability. In this study, a new SDP based on some intuitive properties that characterize the structure of minimal paths (MPs), and the relationships between MPs and subpaths are developed to improved SDP. The proposed SDP is easier to understand and implement, and better than the existing best- known SDP based algorithms under some special situation. The correctness of the proposed algorithm will be analyzed and proven. One bench example is illustrated to show how the network reliability with known MPs is determined using the proposed SDP.     

Non-binary decomposition trees—a method of reliability computation for systems with known minimal paths/cuts

A coherent system with independent components and known minimal paths (cuts) is considered. In order to compute its reliability, a tree structure T is constructed whose nodes contain the modified minimal paths (cuts) and numerical values. The value of a non-leaf node is a function of its child nodes' values. The values of leaf nodes are calculated from a simple formula. The value of the root node is the system's failure probability (reliability). Subsequently, an algorithm computing the system's failure probability (reliability) is constructed. The algorithm scans all nodes of T using a stack structure for this purpose. The nodes of T are alternately put on and removed from the stack, their data being modified in the process. Once the algorithm has terminated, the stack contains only the final modification of the root node of T, and its value is equal to the system's failure probability (reliability).     

An evaluation of the multi-state node networks reliability using the traditional binary-state networks reliability algorithm

A system where the components and system itself are allowed to have a number of performance levels is called the Multi-state system (MSS). A multi-state node network (MNN) is a generalization of the MSS without satisfying the flow conservation law. Evaluating the MNN reliability arises at the design and exploitation stage of many types of technical systems. Up to now, the known existing methods can only evaluate a special MNN reliability called the multi-state node acyclic network (MNAN) in which no cyclic is allowed. However, no method exists for evaluating the general MNN reliability. The main purpose of this article is to show first that each MNN reliability can be solved using any the traditional binary-state networks (TBSN) reliability algorithm with a special code for the state probability. A simple heuristic SDP algorithm based on minimal cuts (MC) for estimating the MNN reliability is presented as an example to show how the TBSN reliability algorithm is revised to solve the MNN reliability problem. To the author's knowledge, this study is the first to discuss the relationships between MNN and TBSN and also the first to present methods to solve the exact and approximated MNN reliability. One example is illustrated to show how the exact MNN reliability is obtained using the proposed algorithm.     

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.     

Tracing the unreliability and recognizing the major unreliability contribution of network components

Weak part analysis of a system is a key element in a system reliability quantification process. It enables the weakest areas of a system to be recognized and assists in directing remedial measures for improving the system reliability. This paper presents a novel approach to identifying the weak parts using the unreliability tracing (UT) technique and introduces the proportional sharing principle (PSP). The model for tracing the unreliability of a complex network is presented based on reliability evaluation methods using minimal cut sets (MCSs) and the PSP. The system UT sharing factors (UTSFs) are derived to easily identify the major unreliability contributions (MUCs) in a system. The method is illustrated using three cases and the UT, UTSF and the reliability impact analysis of different components are discussed. The results show that the developed technique can be applied to complex networks for UT tracing and recognizing the MUC.     

Stochastic network interdiction optimization via capacitated network reliability modeling and probabilistic solution discovery

This paper introduces an evolutionary optimization approach that can be readily applied to solve stochastic network interdiction problems (SNIP). The network interdiction problem solved considers the minimization of the cost associated with an interdiction strategy such that the maximum flow that can be transmitted between a source node and a sink node for a fixed network design is greater than or equal to a given reliability requirement. Furthermore, the model assumes that the nominal capacity of each network link and the cost associated with their interdiction can change from link to link and that such interdiction has a probability of being successful. This version of the SNIP is for the first time modeled as a capacitated network reliability problem allowing for the implementation of computation and solution techniques previously unavailable. The solution process is based on an evolutionary algorithm that implements: (1) Monte-Carlo simulation, to generate potential network interdiction strategies, (2) capacitated network reliability techniques to analyze strategies’ source-sink flow reliability and, (3) an evolutionary optimization technique to define, in probabilistic terms, how likely a link is to appear in the final interdiction strategy. Examples for different sizes of networks are used throughout the paper to illustrate the approach.     

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.     

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.     

Solving advanced network reliability problems by means of cellular automata and Monte Carlo sampling

This paper extends the cellular automata-based, Monte Carlo sampling methodology for computing network reliability, previously proposed by the first author. The extension regards the development of cellular automata for the solution of the all-terminal and k-terminal connection problems and the maximum unsplittable flow problem, which can be considered as a particular, simplified case of the maximum flow distribution problem. The algorithms developed are presented in detail and verified on literature cases.     

Node-pair reliability of network systems with small distances between adjacent nodes

A new method for computing the node-pair reliability of network systems modeled by random graphs with nodes arranged in sequence is presented. It is based on a recursive algorithm using the “sliding window” technique, the window being composed of several consecutive nodes. In a single step, the connectivity probabilities for all nodes included in the window are found. Subsequently, the window is moved one node forward. This process is repeated until, in the last step, the window reaches the terminal node. The connectivity probabilities found at that point are used to compute the node-pair reliability of the network system considered. The algorithm is designed especially for graphs with small distances between adjacent nodes, where the distance between two nodes is defined as the absolute value of the difference between the nodes’ numbers. The maximal distance between any two adjacent nodes is denoted by Γ(G), where G symbolizes a random graph. If Γ(G)=2 then the method can be applied for directed as well as undirected graphs whose nodes and edges are subject to failure. This is important in view of the fact that many algorithms computing network reliability are designed for graphs with failure-prone edges and reliable nodes. If Γ(G)=3 then the method's applicability is limited to undirected graphs with reliable nodes. The main asset of the presented algorithms is their low numerical complexity—O(n), where n denotes the number of nodes.     

Maximal network reliability for a stochastic power transmission network

Many studies regarded a power transmission network as a binary-state network and constructed it with several arcs and vertices to evaluate network reliability. In practice, the power transmission network should be stochastic because each arc (transmission line) combined with several physical lines is multistate. Network reliability is the probability that the network can transmit d units of electric power from a power plant (source) to a high voltage substation at a specific area (sink). This study focuses on searching for the optimal transmission line assignment to the power transmission network such that network reliability is maximized. A genetic algorithm based method integrating the minimal paths and the Recursive Sum of Disjoint Products is developed to solve this assignment problem. A real power transmission network is adopted to demonstrate the computational efficiency of the proposed method while comparing with the random solution generation approach.     

Approximate multi-state reliability expressions using a new machine learning technique

The machine-learning-based methodology, previously proposed by the authors for approximating binary reliability expressions, is now extended to develop a new algorithm, based on the procedure of Hamming Clustering, which is capable to deal with multi-state systems and any success criterion. The proposed technique is presented in details and verified on literature cases: experiment results show that the new algorithm yields excellent predictions.     

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.     

Progress towards the development of a model for predicting human reliability

A methodology for predicting the probability of human task reliability during a task sequence is described. The method is based on a probabilistic performance requirement–resource consumption model. This enables error-promoting conditions in accident scenarios to be modelled explicitly and a time-dependent probability of error to be estimated. Particular attention is paid to modelling success arising from underlying human learning processes and the impact of limited resources. The paper describes the principles of the method together with an example related to safety and risk of a diver in the wreck scenario. © 1998 John Wiley & Sons, Ltd.     

Fuzzy-based system reliability of a labour-intensive manufacturing network with repair

This paper presents a fuzzy-based assessment model to evaluate system reliability of a labour-intensive manufacturing system with repair actions. Due to the uncertainty in human performance, labour-intensive manufacturing systems must determine the capacity of each labourer in order to accurately characterise the performance of the systems. Therefore, we model such a manufacturing system as a fuzzy multi-state network in order to characterise the labourers’ influence on workstation performance. First, the workstation reliability is defined according to the loading state by three fuzzy membership functions, namely ‘under loading’, ‘normal loading’ and ‘over loading’, respectively. The system reliability is subsequently evaluated with fuzzy intersection operations in terms of these workstation reliabilities. Thus, the system reliability is defined as a fuzzy membership function to assess whether the manufacturing system performance is sufficient to satisfy the demand reliably. A case study of a footwear manufacturing system is illustrated to explain the proposed model. Furthermore, we apply the proposed model to a non-labour-intensive manufacturing network in order to validate the applicability to this class of systems.     

Split-type free-displacer Stirling refrigerator design using linear network analysis

A linear network analysis is developed for the system design of split-type free-displacer Stirling refrigerators. The dynamics models are derived to describe the input/output relation of each component by use of the governing equations in conjunction with linearization and approximation. By connecting the equivalent circuits of the components together, a linear network consisting of a fluid network and a displacer network is obtained. The fluid network accounts for the propagation of gas flow induced by the pressure wave; while the displacer network accounts for the displacer motion induced by the pressure force exerted on the displacer. Two transfer functions are further derived for the displacer motion and the gas pressure of the expansion space with respect to the piston motion. The system performance is then evaluated from the frequency response of the transfer functions by using the sinusoidal signal analysis. The performance prediction of a split-type free-displacer Stirling refrigerator using the linear network analysis is shown to be satisfactory.     

Component reliability assessment using quantitative and qualitative data

The estimation of a component failure rate depends on the availability of plant specific numerical data. The purpose of this study was development of a new method that explicitly includes numerical and linguistic information into the assessment of a specific failure rate. The basis of the method is the Bayesian updating approach. A prior distribution is selected from a generic database, whereas likelihood is assessed using the principles of fuzzy set theory. The influence of component operating conditions on component failure rate is modeled using a fuzzy inference system. Results of fuzzy reasoning are then used for building an appropriate likelihood function for the Bayesian inference.The method was applied on a high voltage transformer. Results show that with the proposed method, one can estimate the specific failure rate and analyze possible measures to improve component reliability. The method can be used for specific applications including components for which there is not enough numerical data for specific evaluation.     

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.