An aggregation method of Markov graphs for the reliability analysis of hybrid systems

To meet always increasing safety requirements in car industry, design and safety assessment methods are developed in order to fit the complexity of new embedded mecatronic systems. Hybrid (discrete/continuous) and dynamic features, specific to these systems, require choosing a suitable formalism. These features should also be considered in safety studies made all through the system design. The aim of this paper is to propose a quantitative analysis method based on the construction of an aggregated Markov graph, which allows a limitation of the combinatorial expansion. This graph is directly deducted from the Petri net modelling of the system. It is composed by a set of functional modes and a set of transitions to which statistical information regarding the system dynamics has been added.     

Reliability models for computer systems: An overview including dataflow graphs

The reliability of a system is the probability that the system will perform its intended mission under given conditions. This paper provides an overview of the approaches to reliability modelling and identifies their strengths and weaknesses. The models discussed include structure models, simple stochastic models and decomposable stochastic models. Ignoring time-dependence, structure models give reliability as a function of the topological structure of the system. Simple stochastic models make direct use of the properties of underlying stochastic processes, while decomposable models consider more complex systems and analyse them through subsystems. Petri nets and dataflow graphs facilitate the analysis of complex systems by providing a convenient framework for reliability analysis.     

Analysis of sequential failures for assessment of reliability and safety of manufacturing systems

Assessment of reliability and safety of a manufacturing system with sequential failures is an important issue in industry, since the reliability and safety of the system depend not only on all failed states of system components, but also on the sequence of occurrences of those failures. Methods that are currently available in sequential failure analysis always start with given sequences of the failures in the system, which is not the case in real life situations; therefore, the sequences of the failures should be identified and the probability of their occurrence should be determined. In this paper, we represent a methodology that can be used for identifying the failure sequences and assessing the probability of their occurrence in a manufacturing system. The method employs Petri net modeling and reachability trees constructed based on the Petri nets. The methodology is demonstrated on an example of an automated machining and assembly system.     

Automatic creation of Markov models for reliability assessment of safety instrumented systems

After the release of new international functional safety standards like IEC 61508, people care more for the safety and availability of safety instrumented systems. Markov analysis is a powerful and flexible technique to assess the reliability measurements of safety instrumented systems, but it is fallible and time-consuming to create Markov models manually. This paper presents a new technique to automatically create Markov models for reliability assessment of safety instrumented systems. Many safety related factors, such as failure modes, self-diagnostic, restorations, common cause and voting, are included in Markov models. A framework is generated first based on voting, failure modes and self-diagnostic. Then, repairs and common-cause failures are incorporated into the framework to build a complete Markov model. Eventual simplification of Markov models can be done by state merging. Examples given in this paper show how explosively the size of Markov model increases as the system becomes a little more complicated as well as the advancement of automatic creation of Markov models.     

Hybrid Subset Simulation method for reliability estimation of dynamical systems subject to stochastic excitation

A hybrid Subset Simulation approach is proposed for reliability estimation for general dynamical systems subject to stochastic excitation. This new stochastic simulation approach combines the advantages of the two previously proposed Subset Simulation methods, Subset Simulation with Markov Chain Monte Carlo (MCMC) algorithm and Subset Simulation with splitting. The new method employs the MCMC algorithm before reaching an intermediate failure level and splitting after reaching the level to exploit the causality of dynamical systems. The statistical properties of the failure probability estimators are derived. Two examples are presented to demonstrate the effectiveness of the new approach and to compare with the previous two Subset Simulation methods. The results show that the new method is robust to the choice of proposal distribution for the MCMC algorithm and to the intermediate failure events selected for Subset Simulation.     

An efficient hybrid reliability analysis method with random and interval variables

Random and interval variables often coexist. Interval variables make reliability analysis much more computationally intensive. This work develops a new hybrid reliability analysis method so that the probability analysis (PA) loop and interval analysis (IA) loop are decomposed into two separate loops. An efficient PA algorithm is employed, and a new efficient IA method is developed. The new IA method consists of two stages. The first stage is for monotonic limit-state functions. If the limit-state function is not monotonic, the second stage is triggered. In the second stage, the limit-state function is sequentially approximated with a second order form, and the gradient projection method is applied to solve the extreme responses of the limit-state function with respect to the interval variables. The efficiency and accuracy of the proposed method are demonstrated by three examples.     

Computer-aided reliability analysis of fault-tolerant systems

We present an overview of the major problems inherent in reliability modelling of fault-tolerant systems. The problems faced while modelling such systems include the need to consider a very large state space, non-exponential distributions, error analysis, the need to perform a combined evaluation of performance and reliability, and the need to include the details of fault/error handling behaviour. Some of the proposed solutions are discussed and current tools (harp, save, deep andsharpe) to facilitate evaluation of such systems are described. References are provided to many of the important techniques utilized in reliability, availability, and performance modelling of such systems. This research was supported in part by the Air Force Office of Scientific Research under grant AFOSR-84-0132, by the Army Research Office under contract DAAG29-84-0045 and by the National Aeronautics and Space Administration under grant NAG1-70.     

Construction of event-tree/fault-tree models from a Markov approach to dynamic system reliability

While the event-tree (ET)/fault-tree (FT) methodology is the most popular approach to probability risk assessment (PRA), concerns have been raised in the literature regarding its potential limitations in the reliability modeling of dynamic systems. Markov reliability models have the ability to capture the statistical dependencies between failure events that can arise in complex dynamic systems. A methodology is presented that combines Markov modeling with the cell-to-cell mapping technique (CCMT) to construct dynamic ETs/FTs and addresses the concerns with the traditional ET/FT methodology. The approach is demonstrated using a simple water level control system. It is also shown how the generated ETs/FTs can be incorporated into an existing PRA so that only the (sub)systems requiring dynamic methods need to be analyzed using this approach while still leveraging the static model of the rest of the system.     

An integrated methodology for the dynamic performance and reliability evaluation of fault-tolerant systems

We propose an integrated methodology for the reliability and dynamic performance analysis of fault-tolerant systems. This methodology uses a behavioral model of the system dynamics, similar to the ones used by control engineers to design the control system, but also incorporates artifacts to model the failure behavior of each component. These artifacts include component failure modes (and associated failure rates) and how those failure modes affect the dynamic behavior of the component. The methodology bases the system evaluation on the analysis of the dynamics of the different configurations the system can reach after component failures occur. For each of the possible system configurations, a performance evaluation of its dynamic behavior is carried out to check whether its properties, e.g., accuracy, overshoot, or settling time, which are called performance metrics, meet system requirements. Markov chains are used to model the stochastic process associated with the different configurations that a system can adopt when failures occur. This methodology not only enables an integrated framework for evaluating dynamic performance and reliability of fault-tolerant systems, but also enables a method for guiding the system design process, and further optimization. To illustrate the methodology, we present a case-study of a lateral-directional flight control system for a fighter aircraft.     

A comparison of reliability estimation methods for binary systems

This paper uses a simulation-based approach to compare the predictive accuracy of five different methods for estimating the risk of failure for binary failure/no failure systems such as US strategic missiles, space launch vehicles, and security systems based on the results of a number of tests. This paper tests two Bayesian approaches, two classical (frequentist) approaches, and the method currently used the US Air Force Strategic Command (STRATCOM) to estimate the reliability of strategic nuclear missiles. First, test results are simulated based on an assumed underlying reliability profile. Then the system's reliability is estimated by each of the approaches using the simulated test results, and these estimates are compared with the assumed underlying reliability. Statistical procedures are used to compare the errors from the different methods. The results of this study show that the STRATCOM approach and a classical approach using only the test data from the current period are significantly less accurate than the other three methods and that the accuracy of the Bayesian methods depend on the prior density functions used. The results in this paper provide a quantitative assessment of the accuracy of the tested methods.     

An algorithm for reliability analysis of phased-mission systems

The purpose of this paper is to describe an efficient Boolean algebraic algorithm that provides exact solution to the unreliability of a multi-phase mission system where the configurations are described through fault trees. The algorithm extends and improves the Boolean method originally proposed by Somani and Trivedi. By using the Boolean algebraic method, we provide an efficient modeling approach which avoids the state space explosion and the mapping problems that are encountered by the Markov chain approach. To calculate the exact solution of the phased-mission system with deterministic phase durations, we introduce the sum of disjoint phase products (SDPP) formula, which is a phased-extension of the sum of disjoint products (SDP) formula. Computationally, the algorithm is quite efficient because it calls an SDP generation algorithm in the early stage of the SDPP computation. In this way, the phase products generated in the early stage of the SDPP formula are guaranteed to be disjoint. Consequently, the number of the intermediate phase products is greatly reduced. In this paper, we also consider the transient analysis of the phased-mission system. Special care is needed to account for the possible latent failures at the mission phase change times. If there are more stringent success criteria just after a mission phase change time, an unreliability jump would occur at that time. Finally, the algorithm has been implemented in the software package . With , the complexities of the phased-mission system is made transparent to the potential users. The user can conveniently specify a phased-mission model at a high level (through fault trees) and analyze the system quantitatively.     

An efficient simulation method for reliability analysis of linear dynamical systems using simple additive rules of probability

This paper presents a simulation technique for reliability analysis of linear dynamical systems. It is based on simple additive rules of probability (in contrast to other probabilistic approaches such as importance sampling). It is shown that the proposed appoach is identical to a newly developed approach, Importance Sampling using Elementary Events (ISEE) [Au SK, Beck JL. First excursion probabilities for linear sytems by very efficient importance sampling. Probabl Eng Mech 2001;16(3):193–208]. A simple formula for the coefficient of variation of the estimator of the failure probability using the samples is also given. A 10-story building model with nonstationary excitation is utilized to demonstrate the accuracy and efficiency of the proposed method.     

A multi-state Markov model for a short-term reliability analysis of a power generating unit

This paper presents a multi-state Markov model for a coal power generating unit. The paper proposes a technique for the estimation of transition intensities (rates) between the various generating capacity levels of the unit based on field observation. The technique can be applied to such units where output generating capacity is uniformly distributed. In order to estimate the transition intensities a special Markov chain embedded in the observed capacity process was defined. By using this technique, all transition intensities can be estimated from the observed realization of the unit generating capacity stochastic process. The proposed multi-state Markov model was used to calculate important reliability indices such as the Forced Outage Rate (FOR), the Expected Energy Not Supplied (EENS) to consumers, etc. These indices were found for short-time periods (about 100 h). It was shown that these indices are sensibly different from those calculated for a long-term range. Such Markov models could be very useful for power system security analysis and short-term operating decisions.     

Wedge simulation method for calculating the reliability of linear dynamical systems

In this paper the problem of calculating the probability of failure of linear dynamical systems subjected to random excitations is considered. The failure probability can be described as a union of failure events each of which is described by a linear limit state function. While the failure probability due to a union of non-interacting limit state functions can be evaluated without difficulty, the interaction among the limit state functions makes the calculation of the failure probability a difficult and challenging task. A novel robust reliability methodology, referred to as Wedge-Simulation-Method, is proposed to calculate the probability that the response of a linear system subjected to Gaussian random excitation exceeds specified target thresholds. A numerical example is given to demonstrate the efficiency of the proposed method which is found to be enormously more efficient than Monte Carlo Simulations.     

An improved decomposition scheme for assessing the reliability of embedded systems by using dynamic fault trees

The theories of fault trees have been used for many years because they can easily provide a concise representation of failure behavior of general non-repairable fault tolerant systems. But the defect of traditional fault trees is lack of accuracy when modeling dynamic failure behavior of certain systems with fault-recovery process. A solution to this problem is called behavioral decomposition. A system will be divided into several dynamic or static modules, and each module can be further analyzed using binary decision diagram (BDD) or Markov chains separately. In this paper, we will show a very useful decomposition scheme that independent subtrees of a dynamic module are detected and solved hierarchically. Experimental results show that the proposed method could result in significant saving of computation time without losing unacceptable accuracy. Besides, we also present an analyzing software toolkit: DyFA (dynamic fault-trees analyzer) which implements the proposed methodology.     

A new formalism that combines advantages of fault-trees and Markov models: Boolean logic driven Markov processes

This paper introduces a modeling formalism that enables the analyst to combine concepts inherited from fault trees and Markov models in a new way. We call this formalism Boolean logic Driven Markov Processes (BDMP). It has two advantages over conventional models used in dependability assessment: it allows the definition of complex dynamic models while remaining nearly as readable and easy to build as fault-trees, and it offers interesting mathematical properties, which enable an efficient processing for BDMP that are equivalent to Markov processes with huge state spaces. We give a mathematical definition of BDMP, the demonstration of their properties, and several examples to illustrate how powerful and easy to use they are. From a mathematical point of view, a BDMP is nothing more than a certain way to define a global Markov process, as the result of several elementary processes which can interact in a given manner. An extreme case is when the processes are independent. Then we simply have a fault-tree, the leaves of which are associated to independent Markov processes.     

Joint interval reliability for Markov systems with an application in transmission line reliability

We consider Markov reliability models whose finite state space is partitioned into the set of up states and the set of down states . Given a collection of k disjoint time intervals I_ℓ=[t_ℓ,t_ℓ+x_ℓ], ℓ=1,…,k, the joint interval reliability is defined as the probability of the system being in for all time instances in I₁I_k. A closed form expression is derived here for the joint interval reliability for this class of models. The result is applied to power transmission lines in a two-state fluctuating environment. We use the Linux versions of the free packages Maxima and Scilab in our implementation for symbolic and numerical work, respectively.     

Development of a hybrid negotiation scheme for multi-agent manufacturing systems

A hybrid inter-agent negotiation mechanism based on currency and a pre-emption control scheme is proposed to improve the performance of multi-agent manufacturing systems. The multi-agent system considered consists mainly of four types of agents: machine, clone, part and mediator. The machine agent controls the scheduling and the execution of a task. The clone agent aims to maximize the utilization rate by attracting relevant work to the machine. The part agent communicates with the machine agent or clone agent to acquire necessary production resources in order to get the required processing done, and the mediator agent contains the status of the part that will be processed by the subcontracting machine agent. The primary objective is to design decentralized control protocols for discrete part manufacturing systems to enhance the efficiency of the system and to allocate dynamically the resources to critical jobs based on the dynamic search tree. This research incorporates both the currency and the pre-emption schemes within a common framework. Currency functions are used to help the agents meet their individual objectives, whereas the pre-emption scheme is used to expedite the processing of parts based on their due dates. A dynamic search algorithm for the best route selection of different operations based on the job completion time is also proposed and it is implemented on a small manufacturing unit.     

Integrated analytical models for flexible manufacturing systems

Product form queueing networks (pfqn) and generalized stochastic Petri nets (gspn) have emerged as the principal performance modelling tools for flexible manufacturing systems (fms). In this paper, we present integratedpfqn-gspn models, which combine the computational efficiency ofpfqn and representational power ofgspn by employing the principle of flow-equivalence. We show thatfms that include nonproduct form characteristics such as dynamic routing and synchronization can be evaluated efficiently and accurately using the integrated models.