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.     

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.     

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.     

General network reliability problem and its efficient solution by Subset Simulation

Complex technological networks designed for distribution of some resource or commodity are a pervasive feature of modern society. Moreover, the dependence of our society on modern technological networks constantly grows. As a result, there is an increasing demand for these networks to be highly reliable in delivering their service. As a consequence, there is a pressing need for efficient computational methods that can quantitatively assess the reliability of technological networks to enhance their design and operation in the presence of uncertainty in their future demand, supply and capacity. In this paper, we propose a stochastic framework for quantitative assessment of the reliability of network service, formulate a general network reliability problem within this framework, and then show how to calculate the service reliability using Subset Simulation, an efficient Markov chain Monte Carlo method that was originally developed for estimating small failure probabilities of complex dynamic systems. The efficiency of the method is demonstrated with an illustrative example where two small-world network generation models are compared in terms of the maximum-flow reliability of the networks that they produce.     

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.     

Miner线性累计损伤理论在汽车试验场可靠性试验强化系数研究中的应用

 可靠性试验强化系数是汽车试验场制定规范的基础,运用科学的计算理论和方法可以得到准确的强化系数．根据Miner线性累积损伤理论,按照零件产生疲劳的因素对其进行修正,推导了计算汽车可靠性试验强化系数的数学模型,并在模型中引入损伤因子统计量和频率因子统计量的概念,使影响强化系数的多因素的物理意义更为准确．结合长安大学汽车试验场可靠性强化道路的实际,对某载货车在试验场上的载荷谱测试数据进行处理,计算得到试验场多种路面的综合强化系数．提供的理论和计算方法对其他试验场具有普遍的参考价值．     

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.     

压杆稳定的非概率可靠性凸集合模型分析方法

 针对概率可靠性模型对原始数据要求高的局限性,用凸集合模型来描述影响压杆稳定可靠性分析中的不确定参数,利用一阶Taylor展开式基于凸集合模型讨论了压杆稳定分析中不确定性参数对压杆稳定响应的影响,提出了压杆稳定的非概率可靠性度量的指标.此方法对数据的要求低,不用求概率密度函数而且计算简便.通过对工程实例的计算,其结果表明所提出的方法是一种简便而实用的分析方法.     

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.