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.     

Quantized hopfield networks for reliability optimization

The use of neural networks in the reliability optimization field is rare. This paper presents an application of a recent kind of neural networks in a reliability optimization problem for a series system with multiple-choice constraints incorporated at each subsystem, to maximize the system reliability subject to the system budget. The problem is formulated as a nonlinear binary integer programming problem and characterized as an NP-hard problem. Our design of neural network to solve efficiently this problem is based on a quantized Hopfield network. This network allows us to obtain optimal design solutions very frequently and much more quickly than others Hopfield networks.     

Matrix-based system reliability method and applications to bridge networks

Using a matrix-based system reliability (MSR) method, one can estimate the probabilities of complex system events by simple matrix calculations. Unlike existing system reliability methods whose complexity depends highly on that of the system event, the MSR method describes any general system event in a simple matrix form and therefore provides a more convenient way of handling the system event and estimating its probability. Even in the case where one has incomplete information on the component probabilities and/or the statistical dependence thereof, the matrix-based framework enables us to estimate the narrowest bounds on the system failure probability by linear programming. This paper presents the MSR method and applies it to a transportation network consisting of bridge structures. The seismic failure probabilities of bridges are estimated by use of the predictive fragility curves developed by a Bayesian methodology based on experimental data and existing deterministic models of the seismic capacity and demand. Using the MSR method, the probability of disconnection between each city/county and a critical facility is estimated. The probability mass function of the number of failed bridges is computed as well. In order to quantify the relative importance of bridges, the MSR method is used to compute the conditional probabilities of bridge failures given that there is at least one city disconnected from the critical facility. The bounds on the probability of disconnection are also obtained for cases with incomplete information.     

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 generic method for estimating system reliability using Bayesian networks

This study presents a holistic method for constructing a Bayesian network (BN) model for estimating system reliability. BN is a probabilistic approach that is used to model and predict the behavior of a system based on observed stochastic events. The BN model is a directed acyclic graph (DAG) where the nodes represent system components and arcs represent relationships among them. Although recent studies on using BN for estimating system reliability have been proposed, they are based on the assumption that a pre-built BN has been designed to represent the system. In these studies, the task of building the BN is typically left to a group of specialists who are BN and domain experts. The BN experts should learn about the domain before building the BN, which is generally very time consuming and may lead to incorrect deductions. As there are no existing studies to eliminate the need for a human expert in the process of system reliability estimation, this paper introduces a method that uses historical data about the system to be modeled as a BN and provides efficient techniques for automated construction of the BN model, and hence estimation of the system reliability. In this respect K2, a data mining algorithm, is used for finding associations between system components, and thus building the BN model. This algorithm uses a heuristic to provide efficient and accurate results while searching for associations. Moreover, no human intervention is necessary during the process of BN construction and reliability estimation. The paper provides a step-by-step illustration of the method and evaluation of the approach with literature case examples.     

Validation of reliability computational models using Bayes networks

This paper proposes a methodology based on Bayesian statistics to assess the validity of reliability computational models when full-scale testing is not possible. Sub-module validation results are used to derive a validation measure for the overall reliability estimate. Bayes networks are used for the propagation and updating of validation information from the sub-modules to the overall model prediction. The methodology includes uncertainty in the experimental measurement, and the posterior and prior distributions of the model output are used to compute a validation metric based on Bayesian hypothesis testing. Validation of a reliability prediction model for an engine blade under high-cycle fatigue is illustrated using the proposed methodology.     

Algorithm for estimating reliability confidence bounds of multi-state systems

The paper suggests an effective approach for the estimation of reliability confidence bounds based on component reliability and uncertainty data for multi-state systems with binary-capacitated components. The approach presented is based on the implementation of the universal generating function technique. When compared with a pure Monte Carlo simulation approach, the universal generating function (UGF)-based approach is proven to be more effective due to a more precise reliability estimation and a considerably lower computational effort. Examples are given throughout the paper to illustrate the suggested approach.     

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.     

Integration of computation and testing for reliability estimation

This paper develops a methodology to integrate reliability testing and computational reliability analysis for product development. The presence of information uncertainty such as statistical uncertainty and modeling error is incorporated. The integration of testing and computation leads to a more cost-efficient estimation of failure probability and life distribution than the tests-only approach currently followed by the industry. A Bayesian procedure is proposed to quantify the modeling uncertainty using random parameters, including the uncertainty in mechanical and statistical model selection and the uncertainty in distribution parameters. An adaptive method is developed to determine the number of tests needed to achieve a desired confidence level in the reliability estimates, by combining prior computational prediction and test data. Two kinds of tests — failure probability estimation and life estimation — are considered. The prior distribution and confidence interval of failure probability in both cases are estimated using computational reliability methods, and are updated using the results of tests performed during the product development phase.     

Multi-scale reliability analysis and updating of complex systems by use of linear programming

Complex systems are characterized by large numbers of components, cut sets or link sets, or by statistical dependence between the component states. These measures of complexity render the computation of system reliability a challenging task. In this paper, a decomposition approach is described, which, together with a linear programming formulation, allows determination of bounds on the reliability of complex systems with manageable computational effort. The approach also facilitates multi-scale modeling and analysis of a system, whereby varying degrees of detail can be considered in the decomposed system. The paper also describes a method for computing bounds on conditional probabilities by use of linear programming, which can be used to update the system reliability for any given event. Applications to a power network demonstrate the methodology.     

Equivalence of the LP relaxations of two strong formulations for the capacitated lot-sizing problem with setup times

The multi-item Capacitated Lot-Sizing Problem (CLSP) has been widely studied in the literature due to its relevance to practice, such as its application in constructing a master production schedule. The problem becomes more realistic with the incorporation of setup times since they may use up significant amounts of the available resource capacity. In this paper, we present a proof to show the linear equivalence of the Shortest Path (SP) formulation and the Transportation Problem (TP) formulation for CLSP with setup costs and times. Our proof is based on a linear transformation from TP to SP and vice versa. In our proof, we explicitly consider the case when there is no demand for an item in a period, a case that is frequently observed in the real world and in test problems in the literature. The equivalence result in this paper has an impact on the choice of model formulation and the development of solution procedures.     

Reliability graph with general gates: an intuitive and practical method for system reliability analysis

In this paper, we propose an intuitive and practical method for system reliability analysis. Among the existing methods for system reliability analysis, reliability graph is particularly attractive due to its intuitiveness, even though it is not widely used for system reliability analysis. We provide an explanation for why it is not widely used, and propose a new method, named reliability graph with general gates, which is an extension of the conventional reliability graph. An evaluation method utilizing existing commercial or free software tools are also provided. We conclude that the proposed method is intuitive, easy-to-use, and practical while as powerful as fault tree analysis, which is currently the most widely used method for system reliability analysis.     

Bayesian networks for multilevel system reliability

Bayesian networks have recently found many applications in systems reliability; however, the focus has been on binary outcomes. In this paper we extend their use to multilevel discrete data and discuss how to make joint inference about all of the nodes in the network. These methods are applicable when system structures are too complex to be represented by fault trees. The methods are illustrated through four examples that are structured to clarify the scope of the problem.     

Comparing two reliability upper bounds for multistate systems

The path-cut reliability bound due to Esary and Proschan [J. Am. Stat. Assoc. 65 (1970) 329] and the minimax reliability bound due to Barlow and Proschan [Statistical Theory of Reliability and Life Testing: Probability Models, 1981] for binary systems have been generalized to multistate systems by Block and Savits [J. Appl. Probab. 19 (1982) 391]. Some comparison results concerning the two multistate lower bounds for various types of multistate systems are given by Meng [Probab. Eng. Inform. Sci. 16 (2002) 485]. In this note we compare the two multistate upper bounds and present results which generalize some previous ones obtained by Maymin [J. Stat. Plan. Inference 16 (1987) 337] for binary systems. Examples are given to illustrate our results.     

A memetic algorithm with iterated local search for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is a difficult vehicle routing problem, where given an undirected graph, the objective is to minimize the total cost of all vehicle tours that serve all required edges under vehicle capacity constraints. In this paper, a memetic algorithm with iterated local search (MAILS) is proposed to solve this problem. The proposed MAILS incorporates a new crossover operator, i.e., the longest common substring crossover (LCSX), an iterated local search (ILS) and a perturbation mechanism into the framework of the memetic algorithm (MA). The proposed MAILS is evaluated on the CARP benchmark instances and computational results show that the MAILS is very competitive.     

Application of the fault tree analysis for assessment of power system reliability

A new method for power system reliability analysis using the fault tree analysis approach is developed. The method is based on fault trees generated for each load point of the power system. The fault trees are related to disruption of energy delivery from generators to the specific load points. Quantitative evaluation of the fault trees, which represents a standpoint for assessment of reliability of power delivery, enables identification of the most important elements in the power system. The algorithm of the computer code, which facilitates the application of the method, has been applied to the IEEE test system. The power system reliability was assessed and the main contributors to power system reliability have been identified, both qualitatively and quantitatively.     

自组织网络的可靠性评估算法研究

网络的可靠性是网络性能评估指标的一个方面,他对于网络系统级的性能评估有重要意义。本文从网络可靠性的概念、可靠性分析角度介绍了三种自组织网络的可靠性评估算法:基于跳面节点的可靠性算法、可靠性的上下界估计算法和经验值估计算法的原理和特点,然后介绍了网络性能评估可靠性算法中的一种新的研究方向———效能系数评估法。     

The k-out-of-n acyclic multistate-node networks reliability evaluation using the universal generating function method

In this article, a special node called the k⁻-out-of-n node, which cannot receive more than a certain amount of flows, is newly introduced. The acyclic multistate-node network (AMNN) that unsatisfied the flow conservation law is then extended to the k-out-of-n AMNN by including the k⁻-out-of-n and k⁺-out-of-n nodes. A very simple universal generating function method (UGFM) based on some intuitive properties that characterize the structure of the k-out-of-n AMNN is developed to solve the k-out-of-n AMNN reliability. The correctness of the proposed UGFM will be analyzed and proven. An example with three special cases illustrates how the k-out-of-n AMNN reliability is evaluated using the proposed UGFM. To show that the proposed UGFM can also solve the AMNN reliability, the first case of the example demonstrates that the proposed UGFM without needing to remove redundant terms and collecting like terms is more efficient and reasonable than the best-known UGFM.     

Error bounds for the reliability index in finite element reliability analysis

This work presents an extension of the goal‐oriented error estimation techniques to the reliability analysis of a linear elastic structure. We use a first‐order reliability method in conjunction with a finite element analysis (FEA) to compute the failure probability of the structure. In such a situation the output of interest that is computed from the FEA is the reliability index β. The accuracy of this output, and thus of the reliability analysis, depends, in particular, on the accuracy of the FEA. In this paper, upper and lower bounds of the reliability index are proposed, as well as simple bounds of the failure probability. An application to linear fracture mechanics is presented. Copyright © 2011 John Wiley & Sons, Ltd.     

An integer concave minimization approach for the minimum concave cost capacitated flow problem on networks

Formulating the minimum concave cost capacitated network flow problem as an integer concave minimization problem, we establish finite branch and bound algorithms, in which the branching operation is the so–called integral rectangular partition and the bounding procedure is performed by the classical minimum linear cost flow problem on subnetworks. For the special case that the flow cost function is concave on a fixed number of arcs and linear on the others, an upper bound of the running time is given. Received: 19 July 1996 / Accepted: 8 July 1997