Fast optimal diagnosis procedures for k-out-of-n:G systems

A k-out-of-n:G system consists of a set of components, where each component is either faulty or fault-free. The system is working if at least k components are fault-free. The problem of finding an optimal diagnosis procedure for a given k-out-of-n:G system has been considered in several research fields including medical diagnosis, redundant-system testing, and searching data-files. A polynomial-time algorithm for this problem was presented first by Salloum, and later by Salloum and Breuer, and independently by Ben-Dov. This paper implements the Salloum-Breuer-Ben-Dov algorithm, leading to an optimal diagnosis procedure that can determine the state of any given system in O(n·log(n)) time complexity and O(n) space complexity. The efficiency is achieved by using a generalized radix sorting procedure that uses a heap data structure. For some k-out-of-n:G systems, including those with equal testing costs for all components, the components along the leftmost and rightmost paths in the optimal diagnostic tree uniquely determine the other components in the tree. This property is used to devise a faster optimal diagnosis procedure than the one for the general k-out-of-n:G system. With regard to complexity, these procedures are the best solutions for the problem under consideration. This conjecture is supported by the fact that all these procedures require a sorting operation which has O(n·log(n)) as a lower bound on its time complexity     

An algorithm for computing the reliability of weighted-k-out-of-nsystems

This paper constructs a new k-out-of-n model, viz, a weighted-k-out-of-n system, which has n components, each with its own positive integer weight (total system weight=w), such that the system is good (failed) if the total weight of good (failed) components is at least k. The reliability of the weighted-k-out-of-n:G system is the complement of the unreliability of a weighted-(w-k+1)-out-of-n:F system. Without loss of generality, the authors discuss the weighted-k-out-of-n:G system only. The k-out-of-n:G system is a special case of the weighted-k-out-of-n:G system wherein the weight of each component is 1. An efficient algorithm is given to evaluate the reliability of the weighted-k-out-of-n:G system. The time complexity of this algorithm is O(n.k)     

一类多状态连续n中取k(G)系统的可靠性计算

为了计算多状态连续厅中取后（G）系统的可靠性,引入4个定理,将满足引理的多状态系统转换为二元状态系统。分别推导了多状态线形连续k／n（G）系统和环形连续k／n（G）系统的可靠性计算公式。证明了固定k值增加一个新部件,若部件可靠性独立同分布,线形和环形系统可靠性均增加;若部件可靠性独立但不同分布,环形系统存在一个极值,新增加部件可靠性大于这个极值时得到的新系统可靠性增加,反之系统可靠性下降。     

Generalized multi-state k-out-of-n:G systems

In a binary k-out-of-n:G system, k is the minimum number of components that must work for the system to work. Let 1 represent the working state and 0 the failure state, k then indicates the minimum number of components that must be in state 1 for the system to be in state 1. This paper defines the multi-state k-out-of-n:G system: each component and the system can be in 1 of M+1 possible states: 0, 1, ..., M. In Case I, the system is in state ⩾j iff at least k_j components are in state ⩾j. The value of k_j I 1 can be different for different required minimum system-state level j. Examples illustrate applications of this definition. Algorithms for reliability evaluation of such systems are presented     

The Availability of a k-out-of-n:G Network

A method is described for calculating the analytic availability of a k-out-of-n:G network where the availability of each component may be different. An algorithm and a FORTRAN subroutine are provided to calculate this type of availability.     

Optimal design of k-out-of-n:G subsystems subjected to imperfect fault-coverage

Systems subjected to imperfect fault-coverage may fail even prior to the exhaustion of spares due to uncovered component failures. This paper presents optimal cost-effective design policies for k-out-of-n:G subsystems subjected to imperfect fault-coverage. It is assumed that there exists a k-out-of-n:G subsystem in a nonseries-parallel system and, except for this subsystem, the redundancy configurations of all other subsystems are fixed. This paper also presents optimal design polices which maximize overall system reliability. As a special case, results are presented for k-out-of-n:G systems subjected to imperfect fault-coverage. Examples then demonstrate how to apply the main results of this paper to find the optimal configurations of all subsystems simultaneously. In this paper, we show that the optimal n which maximizes system reliability is always less than or equal to the n which maximizes the reliability of the subsystem itself. Similarly, if the failure cost is the same, then the optimal n which minimizes the average system cost is always less than or equal to the n which minimizes the average cost of the subsystem. It is also shown that if the subsystem being analyzed is in series with the rest of the system, then the optimal n which maximizes subsystem reliability can also maximize the system reliability. The computational procedure of the proposed algorithms is illustrated through the examples.     

Two formulas for computing the reliability of incompletek-out-of-n:G systems

Reliability computation of highly redundant systems most commonly uses approximate methods. Except for k-out-of-n:G systems or consecutive k-out-of-n:G systems, exact reliability formulas offering a broader range of applicability are rare. This paper gives two new formulas for this purpose: the first handles k-out-of-n:G systems of which some paths are not present; the second allows for the reliability calculation of a coherent binary system in general. Both formulas express system reliability in terms of the reliabilities of k-out-of-n:G systems. In practice, these new formulas cope with highly redundant systems with certain similarities to k-out-of-n:G systems. For example, a reliability of the control-rod system of a nuclear reactor is computed. Although the paper is directed to system reliability, the results can be used for computing the failure probability of a system which in practical applications is sometimes more convenient. In which case, the formulas are to be changed such that a system is given by its minimal cut-sets instead of minimal path-sets, and p should be a component unreliability instead of its reliability. The first proof of formula uses domination theory and, in thus contributes to the state of the art in this field     

Application of boundary-tracking gradient-method for optimizingspares cost for k-out-of-n:G systems

This paper presents an application of a classical method of steepest-descent optimization coupled with a boundary-tracking technique to solve the integer spare allocation problem for k-out-of-n:G systems. The objective function for the optimization is linear and subject to a nonlinear availability constraint. The constrained problem is solved in an unconstrained manner using a multiple-gradient technique. The search along the function gradient (unit cost) aims to locate the desired optimum on the constraint boundary. A recovery move to the feasible region is carried out if the search strays into the unfeasible region. Upon re-entry into the feasible region, a new base point for the new search direction is found along the vector sum of the gradient of the objective function and the violated constraint at the recovery point. Results for this boundary tracking multi-dimensional gradient optimization method are compared with enhanced simplical optimization and other methods developed specifically for solving integer problems. The authors' tests are carried out on systems of various numbers of subsystems. The results show appreciable improvement in execution time when compared to their earlier integer simplical optimization methods and to the Sasaki method. The improvement in CPU times is presented for comparison     

Optimal design of reliable network systems in presence of uncertainty

In practice, network designs can be based on multiple choices of redundant configurations, and different available components which can be used to form links. More specifically, the reliability of a network system can be improved through redundancy allocation, or for a fixed network topology, by selection of highly reliable links between node pairs, yet with limited overall budgets, and other constraints as well. The choice of a preferred network system design requires the estimation of its reliability. However, the uncertainty associated with such estimates must also be considered in the decision process. Indeed, network system reliability is generally estimated from estimates of the reliability of lower-level components (nodes & links) affected by uncertainties. The propagation of the estimation uncertainty from the components degrades the accuracy of the system reliability estimation. This paper formulates a multiple-objective optimization approach aimed at maximizing the network reliability estimate, and minimizing its associated variance when component types, with uncertain reliability, and redundancy levels are the decision variables. In the proposed approach, Genetic Algorithms (GA) and Monte Carlo (MC) simulation are effectively combined to identify optimal network designs with respect to the stated objectives. A set of Pareto optimal solutions are obtained so that the decision-makers have the flexibility to choose the compromised solution which best satisfies their risk profiles. Sample networks are solved in the paper using the proposed approach. The results indicate that significantly different designs are obtained when the formulation incorporates estimation uncertainty into the optimal design problem objectives.     

Lifetime of Combined $k$-out-of-$n$ , and Consecutive $k_{c}$ -out-of-$n$ Systems

A combined k-out-of-n:F(G) & consecutive k_c -out-of-n :F(G) system fails (functions) iff at least k components fail (function), or at least fcc consecutive components fail (function). Explicit formulas are given for the lifetime distribution of these combined systems whenever the lifetimes of components are exchangeable, and have an absolutely continuous joint distribution. The lifetime distributions of the aforementioned systems are represented as a linear combination of distributions of order statistics by using the concept of Samaniego's signature. Formulas for the mean lifetimes are given. Some numerical results are also presented.     

An O(n·(log2(n))2) algorithm forcomputing the reliability of k-out-of-n:G and k-to-l-out-of-n:G systems

This paper presents the RAFFT-GFP (Recursively Applied Fast Fourier Transform for Generator Function Products) algorithm as a computationally superior algorithm for expressing and computing the reliability of k-out-of-n:G and k-to-l-out-of-n:G systems using the fast Fourier transform. Originally suggested by Barlow and Heidtmann (1984), generating functions provide a clear, concise method for computing the reliabilities of such systems. By recursively applying the FFT to computing generator function products, the RAFFT-GFP achieves an overall asymptotic computational complexity of O(n·(log₂(n)) ²) for computing system reliability. Algebraic manipulations suggested by Upadhyaya and Pham (1993) are reformulated in the context of generator functions to reduce the number of computations. The number of computations and the CPU time are used to compare the performance of the RAFFT-GFP algorithm to the best found in the literature. Due to larger overheads required, the RAFFT-GFP algorithm is superior for problem sizes larger than about 4000 components, in terms of both computation and CPU time for the examples studied in this paper. Lastly, studies of very large systems with unequal reliabilities indicate that the binomial distribution gives a good approximation for generating function coefficients, allowing algebraic solutions for system reliability     

Performance evaluation of generalized multi-state k-out-of-n systems

The generalized multi-state k-out-of-n:G system model defined by Huang provides more flexibilities for modeling of multi-state systems. However, the performance evaluation algorithm they proposed for such systems is not efficient, and it is applicable only when the k/sub i/ values follow a monotonic pattern. In this paper, we defined the concept of generalized multi-state k-out-of-n:F systems. There is an equivalent generalized multi-state k-out-of-n:G system with respect to each generalized multi-state k-out-of-n:F system, and vice versa. The form of minimal cut vector for generalized multi-state k-out-of-n:F systems is presented. An efficient recursive algorithm based on minimal cut vectors is developed to evaluate the state distributions of a generalized multi-state k-out-of-n:F system. Thus, a generalized multi-state k-out-of-n:G system can first be transformed to the equivalent generalized multi-state k-out-of-n:F system, and then be evaluated using the proposed recursive algorithm. Numerical examples are given to illustrate the effectiveness and efficiencies of the proposed recursive algorithms.     

Genetic algorithms as applied to the numerical computation ofelectromagnetic scattering by weakly nonlinear dielectric cylinders

This paper deals with the application of an optimization procedure based on a genetic algorithm (GA) to the prediction of the electromagnetic fields scattered by weakly nonlinear dielectric objects. Starting by an integral approach and describing the nonlinearities of the constitutive parameters by the Volterra-type integrals, the nonlinear scattering problem is numerically solved by an iterative procedure developed for the minimization of a suitable defined cost function. A GA is applied in order to deal with a large number of unknowns related to the harmonic components of the nonlinear internal electromagnetic field. In a preliminary stage, the behavior of typical parameters of the GA is analyzed; then numerical solutions are carried out and compared with those provided by other methods. Finally, some considerations are made concerning the rate of convergence of the iterative procedure     

Design of CVT-Based Hybrid Passenger Cars

In this paper, the hybridization of a small passenger car equipped with a continuously variable transmission (CVT) is investigated. Designing a hybrid drive train is a multiobjective design problem. The main design objectives are fuel consumption, emissions, and performance. However, it is difficult to find a global optimal integral design solution due to the interdependence of design choices (parameters) regarding the drive-train topology, component sizes, component technologies, and control strategy, as well as the unknown sensitivity of the design objectives to the design parameters. In this paper, a parametric optimization procedure is presented to solve the design problem, where the main design objective is fuel consumption. The effects of parameter variation on fuel consumption have been investigated. Furthermore, a reduced hybrid drive-train model is introduced, with which the effects of design parameter variation is very quickly studied with an average error of less than 1.6%.      

On the Evaluation of the Reliability of k-out-of-n Systems

The paper provides some correcting remarks on several methods to determine the k-out-of-n:G system reliability - a problem that has taken more than its share in the literature. A Jain-Gopal paper presents two algorithms JG-1 and JG-2 to evaluate the reliability of a k-out-of-n System. The comparison of the computational costs of JG-1 with those of JG-2 and with other existing algorithms, especially Barlow-Heidtmann, need to be restated.     

Efficient computation of the sensitivity of k-out-of-n system reliability

The first-order sensitivity of system reliability is useful in evaluating several criticality measures, uncertainty measures, and the instantaneous failure rate of the system. Three new algorithms are described herein for the computation of the sensitivity of k-out-of-n system reliability. Generally, the numerical results of these algorithms check very well versus one another as well as versus those of known special cases. The computational complexities of these algorithms vary from almost double to slightly less than that of the best known algorithm for computing the k-out-of-n system reliability. Some observations are made on the important rankings of system components for different values of k, n and component reliabilities.     

Component redundancy vs system redundancy in the hazard rateordering

Design engineers are well aware of the stochastic result which says that (under the appropriate assumptions) redundancy at the component level is superior to redundancy at the system level. Given the importance of the hazard rate in reliability and life testing, we investigate to what extent this principle holds for the stronger stochastic ordering, viz, hazard rate ordering. Surprisingly, this does not hold for even series systems if the spares do not match the original components in distribution. It is true for series systems however for matching spares, and we conjecture that this is the case in general for k-out-of-n:G systems. We also investigate this principle for cold-standby redundancy (as opposed to active or parallel redundancy)     

The modeling, characterization, and design of monolithic inductorsfor silicon RF IC's

The results of a comprehensive investigation into the characteristics and optimization of inductors fabricated with the top-level metal of a submicron silicon VLSI process are presented. A computer program which extracts a physics-based model of microstrip components that is suitable for circuit (SPICE) simulation has been used to evaluate the effect of variations in metallization, layout geometry, and substrate parameters upon monolithic inductor performance. Three-dimensional (3-D) numerical simulations and experimental measurements of inductors were also used to benchmark the model accuracy. It is shown in this work that low inductor Q is primarily due to the restrictions imposed by the thin interconnect metallization available in most very large scale integration (VLSI) technologies, and that computer optimization of the inductor layout can be used to achieve a 50% improvement in component Q-factor over unoptimized designs     

Multiobjective optimization design of Yagi-Uda antenna

An optimization method, such as the steepest gradient methods, could not easily obtain globally optimum solutions for devising antenna design parameters that allow the antenna to simultaneously improve multiple performances such as gain, sidelobe level, and input impedance. The genetic algorithm (GA) is suitable for empirically solving optimization problems and is effective in designing an antenna. In particular, this method can solve the multiobjective optimization problem using various Pareto-optimal solutions in an extremely efficient manner. In this paper, the Pareto GA, by which various Pareto-optimal solutions for each objective function (performance) can be obtained in a single trial of a numerical simulation and which enables the selection of parameters in accordance with the design requirement, is applied to the multiobjective optimization design of the Yagi-Uda antenna. The effectiveness of the Pareto GA was demonstrated by comparing the performances obtained by the Pareto GA with those of the previously reported values, which were obtained by the conventional GA, and with the values of the design benchmark reference.     

Steady-State Availability of k-out-of-n:G System with Single Repair

This paper presents a solution and computer program for steady-state availability of a k-out-of-n:G system with single repair. Techniques and methodologies are commonly treated in text books to solve one and two element availabilities. This paper provides both the solution for k-out-of-n system availability and a FORTRAN source program for calculating the availability. The managers of mass transit and computer systems can put n elements on line with the assurance that, on the average, at least k elements will actually be available to complete the mission.