Homogeneous redundancy optimization in multi-state series-parallel systems: A heuristic approach

This paper presents a heuristic for a series-parallel system, exhibiting a multi-state behavior, minimizing the cost in order to provide a desired level of reliability. System reliability is defined as the ability to satisfy consumer demands which is presented as a piecewise cumulative load curve. The components are binary and chosen from a list of products available on the market, and are characterized in terms of their feeding capacity, reliability and cost. The solution approach makes use of a homogeneous collection of components to provide redundancy in a subsystem. The algorithm is applied to power systems found in the literature for various levels of reliability requirement. The heuristic offers a straightforward analysis and is efficient both in terms of solution quality and computational time, as compared to existing genetic algorithms and heuristics. Thus, the developed heuristic is attractive, and it can be easily and efficiently applied to numerous real-life systems.     

Tabu search for the redundancy allocation problem of homogenous series–parallel multi-state systems

This paper develops an efficient tabu search (TS) heuristic to solve the redundancy allocation problem for multi-state series–parallel systems. The system has a range of performance levels from perfect functioning to complete failure. Identical redundant elements are included in order to achieve a desirable level of availability. The elements of the system are characterized by their cost, performance and availability. These elements are chosen from a list of products available in the market. System availability is defined as the ability to satisfy consumer demand, which is represented as a piecewise cumulative load curve. A universal generating function technique is applied to evaluate system availability. The proposed TS heuristic determines the minimal cost system configuration under availability constraints. An originality of our approach is that it proceeds by dividing the search space into a set of disjoint subsets, and then by applying TS to each subset. The design problem, solved in this study, has been previously analyzed using genetic algorithms (GAs). Numerical results for the test problems from previous research are reported, and larger test problems are randomly generated. Comparisons show that the proposed TS out-performs GA solutions, in terms of both the solution quality and the execution time.     

A joint reliability-redundancy optimization approach for multi-state series-parallel systems

In this paper, we present a practical approach for the joint reliability-redundancy optimization of multi-state series-parallel systems. In addition to determining the optimal redundancy level for each parallel subsystem, this approach also aims at finding the optimal values for the variables that affect the component state distributions in each subsystem. The key point is that technical and organizational actions can affect the state transition rates of a multi-state component, and thus affect the state distribution of the component and the availability of the system. Taking this into consideration, we present an approach for determining the optimal versions and numbers of components and the optimal set of technical and organizational actions for each subsystem of a multi-state series-parallel system, so as to minimize the system cost while satisfying the system availability constraint. The approach might be considered to be the multi-state version of the joint system reliability-redundancy optimization methods.     

Initial allocation compensation algorithm for redundancy allocation: The scanning heuristic

The tiny feature size in current semiconductor integrated circuits naturally requires redundancy strategies to improve manufacturing yield and operating reliability. To find an optimal redundancy architecture that provides maximum yield and reliability is a trade-off problem. In the reliability optimization field, this type of problem is generally called a redundancy allocation problem. In this paper, we propose a new iterative algorithm, the scanning heuristic, to solve the redundancy allocation problem. The solution quality of conventional iterative heuristics is highly dependent on the initial starting point of the algorithm employed. To overcome this weakness, the scanning heuristic systematically divides the original solution space into several small bounded solution spaces. The local optimum in each divided solution space then becomes a candidate for the final solution. The experimental results demonstrate that the proposed heuristic, and subsequently some combinations of heuristics, are superior to existing heuristics in terms of solution quality.     

Redundancy allocation of series-parallel systems using a variable neighborhood search algorithm

This paper presents a meta-heuristic algorithm, variable neighborhood search (VNS), to the redundancy allocation problem (RAP). The RAP, an NP-hard problem, has attracted the attention of much prior research, generally in a restricted form where each subsystem must consist of identical components. The newer meta-heuristic methods overcome this limitation and offer a practical way to solve large instances of the relaxed RAP where different components can be used in parallel. Authors’ previously published work has shown promise for the variable neighborhood descent (VND) method, the simplest version among VNS variations, on RAP. The variable neighborhood search method itself has not been used in reliability design, yet it is a method that fits those combinatorial problems with potential neighborhood structures, as in the case of the RAP. Therefore, authors further extended their work to develop a VNS algorithm for the RAP and tested a set of well-known benchmark problems from the literature. Results on 33 test instances ranging from less to severely constrained conditions show that the variable neighborhood search method improves the performance of VND and provides a competitive solution quality at economically computational expense in comparison with the best-known heuristics including ant colony optimization, genetic algorithm, and tabu search.     

Reliability optimization of series-parallel systems with a choice of redundancy strategies using a genetic algorithm

This paper proposes a genetic algorithm (GA) for a redundancy allocation problem for the series-parallel system when the redundancy strategy can be chosen for individual subsystems. Majority of the solution methods for the general redundancy allocation problems assume that the redundancy strategy for each subsystem is predetermined and fixed. In general, active redundancy has received more attention in the past. However, in practice both active and cold-standby redundancies may be used within a particular system design and the choice of the redundancy strategy becomes an additional decision variable. Thus, the problem is to select the best redundancy strategy, component, and redundancy level for each subsystem in order to maximize the system reliability under system-level constraints. This belongs to the NP-hard class of problems. Due to its complexity, it is so difficult to optimally solve such a problem by using traditional optimization tools. It is demonstrated in this paper that GA is an efficient method for solving this type of problems. Finally, computational results for a typical scenario are presented and the robustness of the proposed algorithm is discussed.     

A combined approach to solve the redundancy optimization problem for multi-state systems under repair policies

This paper combines universal moment generating function technique with stochastic Petri nets to solve the redundancy optimization problem for multi-state systems under repair policies. Redundant elements are included in order to achieve a desirable level of production availability. The elements of the system are characterized by their cost, performance and availability. These elements are chosen from a list of products available on the market. The number of repair teams is less than the number of reparable elements, and a repair policy specifies the maintenance priorities between the system elements. A heuristic is proposed to determine the minimal cost system configuration under availability constraints. This heuristic, first applies universal moment generating function technique to evaluate the system availability, assuming unlimited maintenance resources. Once a preliminary solution is found by the optimization algorithm, stochastic Petri nets are used to model different repair policies, and to find the best system configuration (architecture and number of repairmen) in terms of global performance (availability and cost). This combined procedure is applied to a reference example.     

A bat algorithm for the redundancy allocation problem

This article uses a recently developed bat algorithm (BA) meta-heuristic optimization method to solve the reliability redundancy allocation problem (RAP). The RAP is a well-known NP-hard problem which has been the subject of much prior work, generally of a restricted form where each component must consist of identical components in parallel to make computations tractable. Meta-heuristic methods overcome this limitation and allow for larger instances to be solved for a more general case where different components can be placed in parallel. The BA has not yet been used in reliability design, as it was a method initially designed for continuous problems. A BA is devised and tested on a well-known suite of problems from the literature. It is shown that the BA is competitive with the best known heuristics for redundancy allocation.     

An efficient heuristic versus a robust hybrid meta-heuristic for general framework of serial–parallel redundancy problem

We present a heuristic approach to solve a general framework of serial–parallel redundancy problem where the reliability of the system is maximized subject to some general linear constraints. The complexity of the redundancy problem is generally considered to be NP-Hard and the optimal solution is not normally available. Therefore, to evaluate the performance of the proposed method, a hybrid genetic algorithm is also implemented whose parameters are calibrated via Taguchi's robust design method. Then, various test problems are solved and the computational results indicate that the proposed heuristic approach could provide us some promising reliabilities, which are fairly close to optimal solutions in a reasonable amount of time.     

Redundancy allocation for multi-state systems using physical programming and genetic algorithms

This paper proposes a multi-objective optimization model for redundancy allocation for multi-state series–parallel systems. This model seeks to maximize system performance utility while minimizing system cost and system weight simultaneously. We use physical programming as an effective approach to optimize the system structure within this multi-objective optimization framework. The physical programming approach offers a flexible and effective way to address the conflicting nature of these different objectives. Genetic algorithm (GA) is used to solve the proposed physical programming-based optimization model due to the following three reasons: (1) the design variables, the number of components of each subsystems, are integer variables; (2) the objective functions in the physical programming-based optimization model do not have nice mathematical properties, and thus traditional optimization approaches are not suitable in this case; (3) GA has good global optimization performance. An example is used to illustrate the flexibility and effectiveness of the proposed physical programming approach over the single-objective method and the fuzzy optimization method.     

Coupling ant colony and the degraded ceiling algorithm for the redundancy allocation problem of series–parallel systems

The redundancy allocation problem (RAP) is a well known NP-hard problem which involves the selection of elements and redundancy levels to maximize system reliability given various system-level constraints. As telecommunications and internet protocol networks, manufacturing and power systems are becoming more and more complex, while requiring short developments schedules and very high reliability, it is becoming increasingly important to develop efficient solutions to the RAP. This paper presents an efficient algorithm to solve this reliability optimization problem. The idea of a heuristic approach design is inspired from the ant colony meta-heuristic optimization method and the degraded ceiling local search technique. Our hybridization of the ant colony meta-heuristic with the degraded ceiling performs well and is competitive with the best-known heuristics for redundancy allocation. Numerical results for the 33 test problems from previous research are reported and compared. The solutions found by our approach are all better than or are in par with the well-known best solutions.     

Structure optimization of multi-state system with time redundancy

In this article, a multi-state system with time redundancy where each system element has its own operation time is considered. In addition, the system total task must be performed during the restricted time. The reliability optimization problem is treated as finding the minimal cost system structure subject to the reliability constraint. A method for reliability optimization for systems with time redundancy is proposed. This method is based on the universal generating function technique for the reliability index computation and on genetic algorithm for the optimization. It provides a solution for the optimization problem for the complex series–parallel system and for the system with bridge topology. Two types of systems will illustrate the approach: systems with ordinary hot reserve and systems with work sharing between elements connected in parallel. Numerical examples are also given.     

A universal generating function approach for the analysis of multi-state systems with dependent elements

The paper extends the universal generating function technique used for the analysis of multi-state systems to the case when the performance distributions of some elements depend on states of another element or group of elements.     

Layer modelling for the inspection allocation problem in re-entrant production systems

In the past two decades, re-entrant production systems have received a great deal of attention. One of the most important characteristics of re-entrant production systems is that the work units are manufactured layer-by-layer, so that some defects are more difficult to inspect after they are covered by the next layer. In this research, a mathematical model considering layered fabrication is developed to find the optimal solution for allocating inspections in re-entrant production systems. Workstations of variables data and inspections of quality characteristics measurement are modelled. In addition, this study considers three possibilities for the treatment of detected non-conforming units, namely repair, rework and scrap. Moreover, a heuristic algorithm is proposed in order to improve the optimization method based on complete enumeration, which suffers from a large amount of computation time, especially as the number of workstations increases. The model is highly extensible and applicable, so it can serve as a production-planning tool to solve the inspection allocation problem in re-entrant production systems.     

Block diagram method for analyzing multi-state systems with uncovered failures

The paper suggests a modification of the generalized reliability block diagram (RBD) method for evaluating reliability and performance indices of multi-state systems with uncovered failures. Such systems (or their subsystems) can fail to perform their task in the case of undetected failure of any one of their elements. Examples of this effect can be found in computing systems, electrical power distribution networks, pipe lines carrying dangerous materials etc. The suggested method based on a universal generating function technique allows performance distribution of complex multi-state series-parallel system with uncovered failures to be obtained using a straightforward recursive procedure. Illustrative examples are presented.     

A Monte Carlo simulation approach to the availability assessment of multi-state systems with operational dependencies

This paper deals with multi-state systems (MSS), whose performance can settle on different levels, e.g. 100%, 80%, 50% of the nominal capacity, depending on the operative conditions of the constitutive multi-state elements. Examples are manufacturing, production, power generation and gas and oil transportation systems. Often in practice, MSS are such that operational dependencies exist between the system state and the state of its components. For example, in a production line of nodal series structure, with no buffers between the nodes, if one of the nodes throughput changes (e.g. switches from 100% to 50% due to a deterministic or stochastic transition of one of its components), the other nodes must be reconfigured (i.e. their components must deterministically change their states) so as to provide the same throughput.In this paper, we present a Monte Carlo simulation technique which allows modelling the complex dynamics of multi-state components subject to operational dependencies with the system overall state. A correlation method is tailored to model the automatic change of state of the relevant components following a change in one of the system nodes. The proposed technique is verified on a simple case study of literature.     

Optimal load distribution in series-parallel systems

This paper presents an algorithm for determining an optimal loading of elements in series-parallel systems. The optimal loading is aimed at achieving the greatest possible expected system performance subject to repair resource constraint. The model takes into account the dependence of elements’ failure rates on their load. The optimization algorithm uses a universal generating function technique for evaluating the expected system performance, and a genetic algorithm for determining the optimal load distribution. An illustrative example of load distribution optimization is presented.     

Redundancy analysis for repairable multi-state system by using combined stochastic processes methods and universal generating function technique

This paper discusses a type of redundancy that is typical in a multi-state system. It considers two interconnected multi-state systems where one multi-state system can satisfy its own stochastic demand and also can provide abundant resource (performance) to another system in order to improve the assisted system reliability. Traditional methods are usually not effective enough for reliability analysis for such multi-state systems because of the “dimensional curse” problem. This paper presents a new method for reliability evaluation for the repairable multi-state system considering such kind of redundancy. The proposed method is based on the combination of the universal generating function technique and random processes methods. The numerical example is presented to illustrate the proposed method.     

A fast algorithm for buffer allocation problem

In this paper, we address the problem of seeking optimal buffer configurations in unreliable production lines with the objective of maximising their production rates. A fast algorithm is proposed for solving the problem. The key idea is to decompose a long production line into a set of overlapping three-machine two-buffer systems. The performance of the algorithm is demonstrated by a comparison with the degraded ceiling (DC) algorithm. Numerical results show that the proposed algorithm is almost as accurate as the DC algorithm, but it is much faster, especially for long production lines.     

A Monte-Carlo simulation approach for approximating multi-state two-terminal reliability

This paper describes a Monte-Carlo (MC) simulation methodology for estimating the reliability of a multi-state network. The problem under consideration involves multi-state two-terminal reliability (M2TR) computation. Previous approaches have relied on enumeration or on the computation of multi-state minimal cut vectors (MMCV) and the application of inclusion/exclusion formulae. This paper discusses issues related to the reliability calculation process based on MMCV. For large systems with even a relatively small number of component states, reliability computation can become prohibitive or inaccurate using current methods. The major focus of this paper is to present and compare a new MC simulation approach that obtains accurate approximations to the actual M2TR. The methodology uses MC to generate system state vectors. Once a vector is obtained, it is compared to the set of MMCV to determine whether the capacity of the vector satisfies the required demand. Examples are used to illustrate and validate the methodology. The estimates of the simulation approach are compared to exact and approximation procedures from solution quality and computational effort perspectives. Results obtained from the simulation approach show that for relatively large networks, the maximum absolute relative error between the simulation and the actual M2TR is less than 0.9%, yet when considering approximation formulae, this error can be as large as 18.97%. Finally, the paper discusses that the MC approach consistently yields accurate results while the accuracy of the bounding methodologies can be dependant on components that have considerable impact on the system design.