Initial allocation compensation algorithm for redundancy allocation: The scanning heuristic

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

[FIGURE 1 OMITTED]

The algorithm starts with the initial allocation of [[IOTA].sub.0]. A simple heuristic--any heuristic can be used to illustrate this point but here we use the steepest ascent rate heuristic in Section 3.1--is executed, and a local optimum of [0.sub.1] is obtained. Note that no point in the n-dimensional integer hy-percube [[IOTA].sub.0], 0.sub.1], i.e., the solution space I, can have a reliability greater than [Florin].([[MICRON].sub.1]) if the objective function is coherent (Ha and Kuo, 2006a). In addition, according to Proposition 1, the solution path from [[IOTA].sub.0] to [[MICRON].sub.1] is always in the solution space I.

Now, let us divide the main solution space into four parts, the solution spaces I, II, III, and IV, based on the obtained local optimum of [[OMICRON].sub.1]. Solution space I is a hyper-cube [[[IOTA].sub.0], [OMICRON].sub.1]], where the [[IOTA].sub.0] is the initial allocation and the [[OMICRON].sub.1] is the local optimum of the current phase. Solution space IV is a hypercube [[OMICRON].sub.1{j ,[for all]j}, [infinity]), where [[OMICRON].sub.1{j ,[for all]}] is a vector ([[OMICRON].sub.11] 1, ..., [[OMICRON].sub.1n] 1) and it has no upper bound. Solution space I is excluded from further consideration because the global optimum of the space I is already obtained. Solution space IV can also be eliminated because any solution in the space is infeasible (Ha and Kuo, 2006a). To show its infeasibility, consider any solution in the space IV and assume it is feasible. Then, the reliability of the solution is larger than the reliability of [[OMICRON].sub.1] because it has more redundancies than [[OMICRON].sub.1]. That [[OMICRON].sub 1] is a local optimum is a contradiction.

Solution spaces II and III are hypercubes [[[IOTA].sub.[omicron]1{1 }], [infinity]) and [[IOTA].sub.[omicron]1{2 }], [infinity]), respectively. As for the n-dimensional problem, n new initial points (lower bounds), [[IOTA].sub.[omicron]1{i }] for j = 1, ..., n, are actually generated for the next phase. The new initial points firmly prohibit the solution paths of the further phases from going into the solution space of the previous phase. This makes the heuristic efficient. The newly generated solution spaces can be overlapped slightly because the upper bounds of the divided solution spaces are not bounded. However, all of the subproblems that are defined by the divided solution spaces are actually bounded by the constraints of the problem. Thus, the overlapping of the solution spaces is not significant in the scanning heuristic.

In the next phase, we run the simple heuristic again for the two remaining solution spaces, II and III. Now, assume that two new local optima, [[MICRON].sub.2] and [[MICRON].sub.3], are the local optima in solution spaces II and III, respectively. If the relationship [[Florin].sub.([0.sub.1])][greater than or equal to] [[Florin].sub.([0.sub.2])] and [[Florin].sub.([0.sub.1])][greater than or equal to] [[Florin].sub.([0.sub.3])] is valid, the algorithm stops because no improvement has been made in this phase; otherwise, the next phase runs with the largest local optimum and its solution space. For example, if [[Florin].sub.([0.sub.1])] has the largest value among [[Florin].([0.sub.1])], [[Florin].([0.sub.2])], and [[Florin].sub.([0.sub.3])], then the next phase is executed on solution space III. The algorithm stops if there is no improvement between two consecutive phases.