Initial allocation compensation algorithm for redundancy allocation: The scanning heuristic

IIE Transactions, July, 2008 by Chunghun Ha, Way Kuo

[l.sub.j][less than or equal to] [x.sub.j][less than or equal to][u.sub.j]for j = 1....,5,

[x.sub.j] is non-negative integer for j = 1...., 5.

Step 1. [x.sub.*] = (2, 1, 3, 2, 1); [[guilder].sub.*] = 0.992096; [DELTA] = 3;1 = (1, 1,1, 1, 1).

Step 2. [[guilder].sub.[DELTA]] = 0.992096; [x.sub.[DELTA]] = (2, 1, 3, 2, 1); [DELTA] = 2;

k = 1

Step 3 to 4. I = (3, 1, 1, 1, 1).

Step 5. x = (3, 2, 2, 1, 1); [guilder] = 0.993216;[[guilder].sup.*] = [guilder];[x.sup.*] = x; [I.sub.[DELTA]] = (3, 1, 1, 1, 1); k = 2.

Step 3 to 5. I = (3, 1, 1, 2, 1, 1, 1); x = (3, 1, 2, 2, 1, 1): [guilder] = 0.993216; k = 3.

Step 3 to 5. I = (1, 1, 4, 1, 1) x = (1, 1, 2, 4, 2); [gulder] = 0.99178; k = 4.

Step 3 to 5. I = (1, 1, 1, 3, 1) x = (1, 1, 2, 3, 2); [gulder] = 0.979988; k = 5.

Step 3 to 5. I = (1, 1, 1, 1, 2) x = (1, 2, 3, 1, 3); [gulder] = 0.990776; k = 6.

Step 6. Because [f sub delta] = 0.992096 < 0.992096 = [[gulder] sup *], 1 = (3, 1, 1, 1, 1).

Step 3. [[gulder] sub delta] = 0.993216; [x sub delta] =(3, 2, 2, 1, 1): [DELTA] = 1; k = 1.

Step 3 to 5. I = (4, 1, 1, 1, 1); x = (3, 2, 2, 1, 1); [gulder] = 0.992919; k = 2.

Step 3 to 4. I = (3, 3, 1, 1, 1); is infeasible; k = 3.

Step 3 to 5. I = (3, 1, 3, 1, 1, 2); x = (3, 2, 1, I, 3, 1, 2); [gilder] = 0.969527; k = 4.

Step 3 to 5. I = (3, 1, 1, 2, 1); x = (3, 1, 2, 2, 1); [gulder] = 0.991361; k = 5.

Step 3 to 5. I = (3, 1, 1, 1, 2); x = (3, 2, 1, 1, 3); [gulder] = 0.998772; k = 6.

Step 6. Stop alogrithm. [x sup *] = (3, 2, 2, 1, 1) and [gulder sup *] 0.993216.

Table 3. Computational results for the (RAP)
with optional components

                      CS                       LS
No  C    W      (Max, Mean, Min)          (Max, Mean, Min)         SC

1  130  190  (0.9857, 0.9855, 0.9852)  (0.9859, 0.9858, 0.9857)  0.9855
2  130  185  (0.9831, 0.9826, 0.9822)  (0.9835, 0.9830, 0.9828)  0.9795
3  130  180  (0.9797, 0.9793, 0.9782)  (0.9803, 0.9798, 0.9796)  0.9785
4  130  175  (0.9753, 0.9753, 0.9753)  (0.9757, 0.9754, 0.9753)  0.9748
5  130  170  (0.9708, 0.9705, 0.9795)  (0.9708, 0.9708, 0.9708)  0.9637
6  130  165  (0.9637, 0.9632. 0.9627)  (0.9637, 0.9637, 0.9637)  0.9557
7  130  160  (0.9557, 0.9556, 0.9554)  (0.9557, 0.9557, 0.9557)  0.9557

3.4. The scanning heuristic for the (RAP) with optional components

The original application of the scanning heuristic is the (RAP) with identical redundancies. However, this heuristic can also be applied to solving the (RAP) with optional components (Fyffe et al., 1968; Coit and Smith, 1996b; Liang and Smith, 2004). We have solved the test problem described in Liang and Smith (2004) using the scanning heuristic. The test problem is a series-parallel system with 14 subsystems in which there are three or four optional components that we can choose. Each optional component can have identical redundancies. The results are summarized in Table 3, where the CS denotes the genetic algorithm by Coit and Smith (1996b) and the LS denotes the ant colony optimization by Liang and Smith (2004). The maximum, mean, and minimum from ten trials are listed for the CS and the LS.