8.1 Introductory Remarks

Very often a reliability goal function cannot be expressed in a convenient analytical form and makes even calculation of reliability decrements practically impossible. For instance, such situations arise when system units are mutually dependent or their reliability simultaneously depends on some common environmental factors (temperature, mechanical impacts, etc.). In these cases, the Monte Carlo simulation is usually used for reliability indices calculation. However, the problem arises: how can one use the Monte Carlo simulation for optimization?

Roughly speaking, the idea is in observing the process of the spare unit expenditure (replacement of failed units) until specified restrictions allow one to do so. This may be a simulation process or an observation of the real deployment of the system. After the stopping moment, we start another realization of simulation process or observation of the real data. When the appropriate statistical data are collected, the process of finding the optimal solution starts.

Avoiding a formal description of the algorithm, let us demonstrate it on numerical examples which will make the idea of the method and its specific technique clearer.

8.2 Formulation of Optimal Redundancy Problems in Statistical Terms

Standard methods do not give a solution if the goal function is the mean time to failure:

(8.1)

or if units are dependent, for instance, via a vector of some external factors g (temperature, humidity, vibration, etc.):

(8.2)

where F(g) is the distribution function of some external parameter g and G is its domain.

8.3 Algorithm for Trajectory Generation

For solution of the formulated problems, we need to have data obtained from real experiment (or system deployment) or from Monte Carlo simulation of the system model. Though this procedure is routine, we will briefly describe it for the presentation closeness. The procedure is as follows.

Consider a series system of n units. (For simplicity of explanation of the algorithm, we will assume that the units are independent. However, everything described below can be easily extended to the general case: it will effect only a mechanism of random sequence generation.)

Let us consider the process of spare unit expenditure as the process of changing the system states and the total cost of spare units at sequential replacement moments. After failure each unit is immediately replaced with a spare one. Let be the moment of the kth replacement during the jth Monte Carlo experiment. The number of spare units of type i spent at moment is denoted .

An initial state at is:

The total cost of spare units at the initial moment is C₀ = 0. (Sometimes it might be reasonable to consider the initial cost of the system with no spare units as C₀, that is, where k_i is the number of units of type i within equipment before reliability improvement.)

Consider the step-by-step procedure of generating trajectories ψ^(s), s = 1, 2, …. We begin with ψ⁽¹⁾ but the corresponding superscript, (1), will be omitted for the sake of convenience.

Step 1. Generate random time to failure (TTF) for each unit, and define b_i1 = ξ_i, that is b_i1 is the moment of the earliest failure (and instantaneous replacement) of the ith unit. The current moment (for every unit i) at the beginning of any trajectory ψ^(s) is b_i0 = 0.

Step 2. Determine the moment of the occurrence of the first event (first replacement) within the first realization ψ⁽¹⁾ as t₁ = min_1≤i≤nb_i1.

Step 3. Assign to the corresponding unit (for which the moment of failure is the earliest one) a specific number i = i₁.

Step 4. Put into the spare units counter a new value .

Step 5. Rename remaining x_i0 as follows: x_i0 = x_i1 for all i ≠ i₁.

Step 6. Calculate a new value of the system cost .

Step 7. Generate the next random TTF for unit i₁, .

Step 8. Calculate the next event occurring due to unit i₁: .

Step 9. Rename the remaining values b_i1 = b_i2 for all i ≠ i₁.

Thus completes the first cycle. GOTO step 2, that is, find t₂ = min_1≤i≤nb_i2, and so on, until stopping the first realization.

The type of problem to be solved determines the stopping rule of each realization.

Stopping rule for the inverse problem of optimal redundancy: The process is stopped at the moment t_N when the total cost of spare units exceeds the permitted C⁰.

Stopping rule for the direct problem of optimal redundancy: The simulation process for each realization stops at the moment t_M−1 < t*≤t_M where t* equals the required operational time t₀ (if the reliability index is the probability of failure free operation) or t* is the required system's mean time to failure (MTTF).

After the termination of generating the first trajectory, ⁽¹⁾, we start to generate ⁽²⁾ by the same rules. The number of needed realizations, N, is determined by the required accuracy of statistical estimates.

Thus, each trajectory j represents a set of the following data:

where is the set of spare units at moment , that is, .

After the description of the Monte Carlo simulating process, let us consider the optimization problems themselves. We can make an important remark: previously all problems were formulated in probabilistic terms, but dealing with statistical (empirical) functions has to be specific. The following problems are reformulated in an appropriate way.

8.4 Description of the Idea of the Solution

Assume that we need to supply some system with spare units for a specified period of time. We have no prior knowledge of units' reliability but we have an opportunity to observe a real process (or simulation) of failure occurrence.

Consider the direct problem of optimal redundancy. What shall we do in this case? We observe the process of spare unit expenditure during time t*. This process can be described as a random path—call it trajectory—in a discrete n-dimensional space, X. An illustration of such a process in a two-dimensional case is presented in Figure 8.1.

FIGURE 8.1 Example of a two-dimensional trajectory.

Let us observe N such trajectories, j = 1, 2, … , N, in an n-dimensional space where n is the number of unit types. Each realization is stopped when the total cost of spare units exceeds the permitted amount, that is, each trajectory reaches or even penetrates a hyperplane:

(8.3)

determined by the restriction on the total system cost (an example for the two-dimensional case is given in Fig. 8.2).

FIGURE 8.2 Example of two-dimensional trajectory inside hyperplane C(x₁, x₂) = C⁰.

After this, in the same n-dimensional space, we construct the hypercube x_r, r = 1, 2, … , such that each of its vertices is lying under the hyperplane. In Figure 8.2 there are two such hypercubes, though there could be many of them: actually, in this case all pairs (x₁, x₂) that belong to hyper plane C(x₁, x₂) = C⁰ could be vertices of such a hypercube.

Denote the maximum time that trajectory ^(j) is spending within the hypercube χ_r by . Introduce an indicator:

(8.4)

Among all hypercubes above we choose the hypercube χ_r that maximizes the frequency of failure-free operation during required interval t₀ under the cost restrictions:

(8.5)

where C⁰ is the admissible redundant group cost.

Maximization of the system average time to failure is reached by the hypercube that corresponds to the solution of the following problem of the conditional optimization:

(8.6)

Now consider the direct problem of optimal redundancy. In this case, the required time of the system failure-free operation equals t₀. We observe the process of spare units expenditure N times until the system failure-free time exceeds t₀ and record trajectories ^(j), j = 1, 2, … , N, in an n-dimensional space. Afterwards we construct such hypercubes χ_r, r = 1, 2, … , in the same n-dimensional space that includes (covers) R⁰ × 100% of all trajectories where R⁰ is the specified level of the reliability index. Among all hypercubes described above, we choose the one that is characterized by the minimum total cost. In other words, the hypercube must satisfy the solution of the following problem:

(8.7)

Now let the specified requirement be given for the system average time to failure, T*. The hypercube presenting the solution must be chosen corresponding to the solution of the problem:

(8.8)

Of course, one should take into account that the operation with the frequency differs from the operation with the probability. The proposed solution is asymptotically accurate. Thus, all these arguments are satisfactory only for a large enough sample size.

8.5 Inverse Optimization Problem

8.5.1 System Successful Operation versus System Cost

We need to find x^opt that satisfies Equation (8.5). The algorithm for solution is as follows.

Step 1. Choose a hypercube χ₁ whose diagonal vertex is lying on or under the hyperplane in Equation (8.3).

Step 2. Take the first realization, ψ⁽¹⁾, obtained with the help of the Stopping Rule 1. Find moment when this trajectory “punctures” the hypercube χ₁. This corresponds to the moment where

and where χ_i1 is a component of χ₁.

Step 3. Assign to a value 1 or 0 by using the indicator function in Equation (8.4).

Step 4. Add to the value in the counter (initial value equals 0) of successful trajectories.

Repeat the procedure from step 2 for the next realization, ψ⁽²⁾.

After the analyzing of all trajectories, we calculate the frequency of successful trajectories, for the chosen hypercube χ₁. Then we find such a hypercube χ_K that is characterized by the maximum value of For this purpose, we can use a random search, steepest descent, or other numerical optimization procedure in the discrete space of the trajectories of spare unit expenditure.

---

Example 8.1

Consider a series system of n = 3 units. For the sake of simplicity of illustrative calculations and possibility to compare an obtained solution with analytical solution, assume that the system units are independent and c_i = c for all i, 1 ≤ i ≤ 3. Let the unit time to failure (TTF) be distributed exponentially with parameters λ₁ = 1, λ₂ = 0.5, and λ₃ = 0.25, respectively. The specified time of failure-free operation is t₀ = 1. Admissible total cost of a spare unit is equal to 4.

In the left three columns of Table 8.1, there are random exponentially distributed times to failure, ξ_i, for all three units. In the next three columns there are corresponding sequences of replacement times θ_i(k): θ_i(k) = ξ_i1 + ξ_i2 + … +ξ_ik. In other words, θ_i(k) is a random survival time of the ith redundant group consisting of one main and k-1 spare units.

TABLE 8.1 Random TTF and Replacement Time for 10 Monte Carlo Realizations

We will use the same random numbers for all of the examples below. This leads to a dependence of the results obtained for different problems, but our main goal is to illustrate the algorithm of the solution with the use of a numerical example, rather than to execute an accurate statistical experiment.

---

---

Solution to Example 8.1

(1) Consider Realization 1 from Table 8.1. First, take values ξ_i of the first row of the left block of columns: ξ₁₁ = 0.07, ξ₂₁ = 0.75, and ξ₃₁ = 0.24. Denote them θ₁₍₁₎, θ₂₍₁₎, and θ₃₍₁₎, respectively, and set them into the first row of the right block of columns (“Replacement time”). Find the minimum value: min {θ₁₍₁₎, θ₂₍₁₎, θ₃₍₁₎} = θ₁₍₁₎ = 0.07.

(2) Next take the value ξ₁₂ = 0.53 in the column “TTF; Unit 1.” Form a new value: θ₁₍₂₎ = θ₁₍₁₎ + ξ₁₂ = 0.07 + 0.53 = 0.6. Rename θ₂₍₁₎ = θ₂₍₂₎ and θ₃₍₁₎ = θ₃₍₂₎. Set this value into the second place in the column “Replacement time; Unit 1.”

(3) Find the minimum value: min {θ₁₍₂₎, θ₂₍₂₎ , θ₃₍₂₎} = θ₃₍₂₎ = 0.24. Repeat step 2 until the total cost of each system equals 7. (For the case c_i = c, it means that all 7 units are spent.) As the result, we spent three units of type 1, no units of type 2, and two units of type 3. In this particular case, the system TTF does not reach the specified time t₀ = 1.

(4) Repeat steps 1 to 3 with the remaining realizations from Table 8.1 and complete Table 8.2.

(5) Notice that units marked with “*” in Table 8.2 are auxiliary, that is, in each particular case they are not necessary because t₀ has been reached before all permitted resources were spent.

(6) In Table 8.3, list all vectors: , k = 1, 2, … , 10, that are obtained from Table 8.2 after exclusion of the marked units (see Table 8.3).
Realization #1 is not taken into account because its TTF < 1.

(7) Order each component of these vectors separately (see Table 8.4). In other words, Table 8.4 shows the frequency with which a corresponding number of spare units of each type has been met during 10 realizations of the Monte Carlo simulation. We see that the use of the vector (3, 3, 2) of spare units for this realization will lead to 1 failure in 10 experiments. However, the total system cost equals 8 units. So, the next step is to find the best way of reducing the total system cost.

(8) Put the number of realizations for which TTF has not reached t₀ = 1 into the failure counter. In our case there is only one such realization with TTF ≤ 1.

(9) Exclude from Table 8.2 all vectors which correspond to the realizations mentioned in step 7.

(10) Find which unit in Table 8.4 has the smallest number of the use of largest values of . In our example, three units of type 1 were used in three realizations, three units of type 1 were used once, and two units of type 3 were used four times. (We exclude from consideration Realization 1 since it did not deliver TTF ≥ 1.) In this case we exclude one unit of type 2 because in this case we gain one unit of cost and “loss” only one realization.

(11) Add number of units excluded at step 9 into the counter of system failures.

(12) Check if the system cost equal to or less than C⁰ = 7. If “No,” correct Table 8.3 by exclusion of the vector 1 and continue the procedure from step 6. If “Yes,” stop the procedure.

(13) Calculate the ratio of realization without failure (the total number of realization minus the number of failures from the counter) to the total number of performed realizations.
In the example considered the final solution is (3, 2, 2).

TABLE 8.2 Initial Experiment with Exclusion of “Extra Units” (Marked with “*”)

Unit 1	Unit 2	Unit 3
Realization 1
0.07	0.75	0.24
0.6		3.43
0.66
1.19
Realization 2
0.42	0.13	4.92
0.58	1.28
1.03
1.31*
Realization 3
0.62	3.47	3.22
4.28	6.2*	7.14*
9.39*
Realization 4
1.45	5.85	0.51
2.58*	9.15
3.85*
4.29*
Realization 5
0.32	0.22	0.54
1.08	0.37	2.06
	1.87
Realization 6
0.11	2.03	5.54
1.13	2.52*
2.01*
2.41*
Realization 7
1.22	0.11	2.69
3.09*	1.02	2.79*
	3.13*
Realization 8
0.27	1.49	22.49
0.71	2.02*
1.45
2.2*
Realization 9
0.46	1.55	7.9
1.52	6.35*
3.42*
3.59*
Realization 10
0.83	1.08	0.58
1.23	2.84*	4.33
2.23*

TABLE 8.3 Realization of Units Spent (Corrected for t₀ ≥ 1)

TABLE 8.4 Ordered Numbers of the Use of Units of Different Types

x1	x2	x3
1	1	1
2	1	1
2	1	1
2	1	1
2	1	1
2	(1)	2
3	2	2
3	2	2
3	2	2
(4)	3	(2)

Note: Numbers in parentheses correspond to the first realization, which was not taken into account.

---

As a direct calculation using tables of Poisson distribution shows, this vector delivers the probability 0.804. Of course, such a coincidence with the observed frequency equal to 0.8 in a particular statistical experiment is not a proof of the method. However, multiple results obtained by the proposed method for other examples show a proper closeness to the exact solution, even for a relatively small sample size.

The asymptotical convergence of the solution to the optimal one was proved by Gordienko and Ushakov (1978).

8.6 Direct Optimization Problem

8.6.1 System Cost versus Successful Operation

We need to find which satisfies the solution of Equation (8.5). The algorithm of solution in this case is as follows.

Step 1. Construct a realization of the first trajectory of the spare unit expenditure until exceeds the specified value of operational time t₀. Memorize the number of spare units spent, , i = 1, 2, …, n. Continue this procedure until all of N required trajectories are constructed.

Step 2. Construct a hypercube χ₁ whose edges χ_i1 are found as χ_i1 = max_1≤j≤Nx_ij that is, χ_i1 is the maximum number of spare units of type i observed during all N realizations. (It means that for this particular sample of realizations, all of them will lay within a hypercube that is stocked with enough spare units so that we would not observe any system failure.)

Step 3. Calculate the system cost for the hypercube χ⁽¹⁾ for which all trajectories have the survival time no less than t₀:

Step 4. Calculate for each i:

where shows how many numbers equal to χ_i1 exist for a unit of type i and is the value of the system cost decrease if we reject to use max_1≤j≤Nχ_ij and will use the next value in the descending order.

Step 5. Find the type of units that correspond to the maximum value of and name it as i₁, that is, this number corresponds to the following condition:

Step 6. Exclude units of type i₁ and form a new value:

Step 7. Rename remaining numbers:

Step 8. Calculate the system successful operation index after the exclusion of ν_i1 units of type i₁:

Step 9. Calculate the system spare units' cost after the exclusion of ν_i1 units of type i₁:

After these steps we have a new hypercube χ₂:

Repeat the procedure from step 5 until the system spare units' cost is equal to or smaller than the given restriction.

---

Example 8.3

Let us take . In the previous example we found that the vector of spare units (4, 3, 2) satisfies 100% of successful realizations. So, if we take a vector (3, 3, 2) it will satisfy the condition Now we need to find the lower 90% confidence limit for the frequency 0.9 obtained in 10 experiments. This limit can be found with the use of the Clopper-Pearson method.

In this particular case it is easier to make direct calculations. If we choose the estimate of the searched probability equal to 0.9 then the probability that we will observe no fewer than 8 successes is equal to:

So, in the process of decreasing the number of used spare units, we must stop after the first exclusion, that is, the solution in this case is (3, 3, 2).

Thus, the solutions of direct and inverse problems of optimal redundancy are different, though they should coincide. The variation lies in the difference of approaches: having the restriction on the system cost, we maximize the possible observed frequency; in the latter case we consider minimization of the system cost under the condition that the level of probability is guaranteed. This difference will be smaller if the number of realizations is larger.

We could solve the problem above with an iteration procedure using the solution of the direct problem of optimal redundancy. The use of the “fork method” is convenient in this case. We find the solution, for some cost restriction, say, , and calculate the value . If R₁ < R* we chose and continue the procedure; if R₁ > R* we chose and also continue the procedure. For the next steps, we can use a simple linear approximation:

where subscript k stands for the current step, subscript k − 1 for the previous step, and subscript k + 1 for the next step.

---

Chronological Bibliography

Ushakov, I. A., and Yasenovets, A. V. 1977. “Statistical methods of solving problems of optimal standby.” Soviet Journal of Computer and System Sciences, no. 6.

Ushakov, I. A., and Gordienko, E. I. 1978. “On statistical simulation approach to solution of some optimization problems.” Elektronische Informationsverarbeitung und Kybernetik, no. 3.

Ushakov, I. A., and Gordienko, E. I. 1978. “Solution of some optimization problems by means of statistical simulation.” Electronosche Infdormationsverarbeitung und Kybernetik, no. 11.

Mohan, C., and Shanker, K. 1988. “Reliability optimization of complex systems using random search technique.” Microelectronics and Reliability, no. 28.

Boland, P. J., El-Neweihi, E., and Proschan, F. 1992. “Stochastic order for redundancy allocations in series and parallel systems.” Advances in Applied Probability, no. 1.

Zhao, R., and Liu, B. 2003. “Stochastic programming models for general redundancy-optimization problems.” IEEE Transaction on Reliability, no. 52.