In this thesis, we propose a modified genetic algorithm (referred to as GA) for large-scaled reliability redundancy allocation problems (referred to as RRA) with series-parallel systems which were proven NP-hard. Traditional GAs do not perform well in large-scaled RRA without applying any frontier search technique. To obtain high quality solutions, it is critical to search the region near the boundary of the feasible region, but when considering large-scaled problems, it is difficult to achieve with such traditional GAs.
In the proposed algorithm, a large-scaled RRA problem is first narrowed down to an approximate core problem by applying some particular variable reduction strategies, and then the corresponding approximate core problem is solved by a modified hybrid genetic algorithm (referred to as HGA) first proposed by Huang. The proposed algorithm can obtain high quality solutions for large-scaled problems in a reasonable time and can be adopted into various problems by altering some mechanisms.

Abstract i
List of tables, problems,andfigures iv

1 Introduction 1
1.1 Background and motivation 1
1.2 Problem description 2
1.3 Framework 4

2 Literature review 5
2.1 Exact methods for reliability redundancy allocation 5
2.1.1 Branch and bound algorithms 6
2.1.2 Dynamic programming techniques 7
2.1.3 Summary and discussion 10
2.2 Reliability redundancy allocation by heuristics 10
2.2.1 Sharma-Venkateswaran method 11
2.2.2 Nakagawa-Nakashima method 12
2.2.3 Aggarwal-Gupta-Misra method and Jianping’s
bound heuristic 13
2.2.4 The surrogate constraints method 14
2.2.5 Reliability redundancy allocation with
components level selection by heuristic 16
2.2.6 Summary and discussion 18
2.3 Metaheuristics for reliability redundancy allocation 18
2.3.1 Genetic Algorithm 19
2.3.2 Yokota-Gen-Ida method for RRA 20
2.3.3 Yokota-Gen-Ida-Taguchi method for RRA with
alternative design 21
2.3.4 Yokota-Gen-Li method for RRA 22
2.3.5 Summary and discussion 24
3 A hybrid genetic algorithm with variable reduction
strategy 25
3.1 Boundary solutions for optimization 25
3.2 The core problem and the variable reduction strategy 27
3.3 A hybrid genetic algorithm for 0-1 knapsack problems 28
3.4 A hybrid genetic algorithm for solving reliability
redundancy allocation 30
4 Experimental results and discussion 34
4.1 Reduction methods for base problems 34
4.2 A numerical example for variable reduction strategies35
4.3 Computational results and discussion 38
5 Conclusions and further research 44
Appendix 46
A.I The sensitivity of ci/ai ratio on the boundary 46
A.II The step size of variables 47
References 49






List of Tables, Problems, and Figures
Tables
Table 4.1. Coefficients used in Example 4.1 for Problem P1 36 Table 4.2. Experimental results of different reduction methods for n = 100 40
Table 4.3. Experimental results of different reduction methods for n = 200 40
Table 4.4. Experimental results of different reduction methods for n = 500 41
Table 4.5. The average sorted index of different reduction methods 41
Table 4.6. The average base value of different reduction methods 42
Table A.1. The scattering information of the critical variables 46
Table A.2. The computational results for step size information 48
Problems
P1. Modified series-parallel RA problems originally formulated by Tillman and Littschwager 3
P2. General form of series-parallel RRA with linear constraints 6
P3. 0-1 translation form of P2by Ghare and Taylor 6
P4. RRA with components selection under separable cost and weight constraints 8
P5. P4 with the weight constraint being translated into the objective by Lagrange multiplier 8
P6. General form of series-parallel RRA under any failure mode with linear constraints 11
P7. General form of series-parallel RRA under any failure mode with linear constraints 12
P8. General form of series-parallel RRA under any failure mode with linear constraints 15
P9. Surrogate dual problem of Problem P8 15
P10. General form of series-parallel RRA with separable constraints 16
P11. General form of series-parallel RRA under any failure mode 20
P12. General form of series-parallel RRA with alternative design 21
P13. General form of series-parallel RRA under any failure mode 22
P14. 0-1 multidimensional linear knapsack problem 27
P15. Core problem of Problem P14 defined by Balas and Zemel 28
P16. General form of series-parallel RRA 31
P17. Piecewise Linear form of Problem P16 32
Figures
Figure 1.1. A series-parallel reliability system 4

[1] K. K. Aggarwal, J. S. Gupta, K. B. Misra, “A new heuristic criterion for solving a redundancy optimization problem”, IEEE Transactions on Reliability, vol. R-24, pp 86-87 (1975).
[2] K. K. Aggarwal, “Redundancy optimization in general systems”, IEEE Transactions on Reliability, vol. R-25, pp 330-332 (1976).
[3] E. Balas, “A note on the branch-and-bound principle”, Operations Research, vol. 16, pp 442-445 (1968).
[4] E. Balas, E. Zemel, “An algorithm for large zero-one knapsack problems”, Operations Research, vol. 28, pp 1130-1154 (1980).
[5] R. E. Bellman, S. E. Dreyfus, “Dynamic programming and the reliability of multicomponent devices”, Operations Research, vol. 6, pp 200-206 (1958).
[6] M. S. Chern, R. H. Jan, “Parametric programming applied to reliability optimization problems”, IEEE Transactions on Reliability, vol. R-34, pp165-170, (1985).
[7] M. S. Chern, R. H. Jan, “Reliability optimization problems with multiple constraints”, IEEE Transactions on Reliability, vol. R-35, (1986).
[8] M. S. Chern, R. H. Jan, R. J. Chern, “Parametric nonlinear integer programming: The right-hand side case”, European Journal of Operational Research, vol. 54, pp 237-255 (1991).
[9] M. S. Chern, “On the computational complexity of reliability redundancy allocation in a series system”, Operations Research Letters, vol. 11, pp 309-315 (1992).
[10] M. S. Chern, Metaheuristic Algorithms, Lecture Note, National Tsing Hua University (2010).
[11] D. W. Coit, A. E. Smith, “Reliability optimization of series-parallel systems using a genetic algorithm”, IEEE Transactions on Reliability, vol. 45, pp 254-266 (1996).
[12] D. W. Coit, A. E. Smith, “Penalty guided genetic search for reliability design optimization”, Computers and Industrial Engineering, vol. 30, pp 895-904 (1996).
[13] M. W. Cooper, “The use of dynamic programming methodology for the solution of a class of nonlinear programming problems”, Naval Research Logistics Quarterly, vol. 27, pp 89-95 (1980).
[14] B. Dengiz, F. Altiparmak, A. E. Smith, “Local search genetic algorithm for optimal design of reliable networks”, IEEE Transactions on Evolutionary Computation, vol. 1, pp 179-188 (1997).
[15] L. T. Fan, C. S. Wang, F. A. Tillman, C. L. Hwang, “Optimization of systems reliability”, IEEE Transactions on Reliability, vol. R-16, pp 81-86 (1967).
[16] D. E. Fyffe, W. W. Hines, N. K. Lee, “System reliability allocation and a computational algorithm”, IEEE Transactions on Reliability, vol. R-17, pp 64-69 (1968).
[17] M. Gen, K. Ida, M. Sasaki, J. U. Lee, “Algorithm for solving large-scale 0-1 goal programming and its application to reliability optimization problem”, Computers and Industrial Engineering, vol. 17, pp 525-530 (1989).
[18] M. Gen, R. Cheng, Genetic Algorithms and Engineering Design, New York: Wiley (1997).
[19] P. M. Ghare, R. E. Taylor, “Optimal redundancy for reliability in series system”, Operations Research, vol. 17, pp 838-847 (1969).
[20] K. Gopal, K. K. Aggarwal, J. S. Gupta, “An improved algorithm for reliability optimization”, IEEE Transactions on Reliability, vol. R-27, pp 325-328 (1978).
[21] M. Hikita, Y. Nakagawa, K. Nakashima, H. Narihisa, “Reliability optimization of systems by a surrogate-constraints algorithm”, IEEE Transactions on Reliability, vol. 41, pp 473-480, (1992).
[22] L. Hillier, Lieberman, Introduction to Operations Research, New York: McGraw-Hill, 8th edition, (2005).
[23] P. M. Himmelblau, Applied Nonlinear Programming, New York: McGraw-Hill (1972).
[24] D. S. Hochbaum, “Lower and upper bounds for the allocation problem and other nonlinear optimization problems”, Mathematics of Operations Research, vol. 19, pp 390-409 (1994).
[25] J. H. Holland, Adaption in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, MI (1975).
[26] H. C. Huang, “A hybrid genetic algorithm for the large-scale 0-1 multidimensional knapsack problem”, M. S. Thesis, National Tsing Hua University (2006).
[27] L. Jianping, “A bound heuristic algorithm for solving reliability redundancy optimization”, Microelectronics and Reliability, vol. 36, pp 335-339 (1996).
[28] P. J. Kolesar, “Linear programming and the reliability of multicomponent systems”, Naval Research Logistics Quarterly, vol. 15, pp 317-327 (1967).
[29] W. Kuo, C. L. Hwang, F. A. Tillman, “A note on heuristic methods in optimal system reliability”, IEEE Transactions on Reliability, vol. R-27, pp 320-324 (1978).
[30] W. Kuo, H. H. Lin, Z. Xu, W. Zhang, “Reliability optimization with the Lagrange-multiplier and branch-and-bound technique”, IEEE Transactions on Reliability, vol. R-36, pp 624-630 (1987).
[31] W. Kuo, V.R. Prasad, “An annotated overview of system-reliability optimization”, IEEE Transactions on Reliability, vol. 49, pp 176-187 (2000).
[32] W. Kuo, V. R. Prasad, F. A. Tillman, C. L. Hwang, Optimal Reliability Design: Fundamentals and Applications, Cambridge (2001).
[33] A. H. Land, A. G. Doig, “An automatic method for solving discrete programming problems”, Econometrica, vol. 1960, pp 497-520, (1960).
[34] E. L. Lawler, D. E. Wood, “Branch-and-bound-methods: A survey”, Operations Research, vol. 14, pp 699-719, (1966).
[35] D. G. Luenberger, “Quasi-convex programming”, SIAM Journal of Applied Mathematics, vol. 16, pp 1090-1095 (1968).
[36] D. W. McLeavey, “Numerical investigation of optimal parallel redundancy in series systems”, Operations Research, vol. 22, pp 1110-1117 (1973).
[37] D. W. McLeavey, J. A. McLeavey, “Optimization of system reliability by branch-and-bound”, IEEE Transactions on Reliability, vol. R-25, pp 327-329 (1976).
[38] K. B. Misra, “Reliability optimization of a series-parallel system”, IEEE Transactions on Reliability, vol. R-21, pp 230-238 (1972).
[39] K. B. Misra, “A simple approach for constrained redundancy optimization problem”, IEEE Transactions on Reliability, vol. 21, pp 30-34 (1972).
[40] Y. Nakagawa, K. Naskashima, “A heuristic method for determining optimal reliability allocation”, IEEE Transactions on Reliability, vol. R-26, pp 156-161 (1977).
[41] Y. Nakagawa, S. Miyazaki, “An experimental comparison of the heuristic methods for solving reliability optimization problems”, IEEE Transactions on Reliability, vol. R-30, pp 181-184 (1981).
[42] H. Pirkul, “A heuristic solution procedure for the multiconstraint zero-one knapsack problem”, Naval Research Logistics, vol. 34, pp 161-172 (1987).
[43] V. Ravi, B. Murty, P. Reddy, “Nonequilibrium simulated-annealing algorithm applied reliability optimization of complex systems”, IEEE Transactions on Reliability, vol. 46, pp 233-239 (1997).
[44] V. Selman, N. T. Grisamore, “Optimum system analysis by linear programming”, Proceedings: 1966 Annual Symposium on Reliability, pp 696-703 (1966).
[45] J. Sharma, K. V. Venkateswaran, “A direct method for maximizing the system reliability”, IEEE Transactions on Reliability, vol. R-20, pp 256-259 (1971).
[46] T. Taguchi, K. Ida, M. Gen, “Method for solving nonlinear goal programming with interval coefficients using genetic algorithm”, Computers and Industrial Engineering, vol. 33, pp 597-600 (1997).
[47] F. A. Tillman, J. M. Littschwager, “Integer programming formulation of constrained reliability problems”, Management Science, vol. 13, pp 887-899 (1967).
[48] F. A. Tillman, C. L. Hwang, L. T. Fan, S. A. Balbale, “Systems reliability subject to multiple nonlinear constraints”, IEEE Transactions on Reliability, vol. R-17, pp 153-157 (1968).
[49] F. A. Tillman, “Optimization by integer programming of constrained reliability problems with several modes of failure”, IEEE Transactions on Reliability, vol. R-18, pp 47-53 (1969).
[50] F. A. Tillman, C. L. Hwang, W. Kuo, “Optimization techniques for system reliability with redundancy – a review”, IEEE Transactions on Reliability, vol. R-26, pp 148-155 (1977).
[51] F. A. Tillman, C. L. Hwang, W. Kuo, “Determing component reliability and redundancy for optimum system reliability”, IEEE Transactions on Reliability, vol. R-26, pp 162-165 (1977).
[52] D. H. Wolpert, W. G. Macready, “No free lunch theorems for optimization”, IEEE Trans. Evolutionary Computation, vol. 1, pp 67-82 (1997).
[53] L. A. Wolsey, Integer Programming, N. Y.: Wiley (1998).
[54] Z. Xu, W. Kuo, H. H. Lin, “Optimization limits in improving system reliability”, IEEE Transactions on Reliability, vol. 39, pp 51-60 (1990).
[55] T. Yokota, M. Gen, K. Ida, “System reliability of optimization problems with several failure modes by genetic algorithm”, Japanese Journal of Fuzzy Theory and Systems, vol. 7, pp 117-185 (1995).
[56] T. Yokota, M. Gen, K. Ida, T. Taguchi, “Optimal design of system reliability by an approved genetic algorithm”, Transactions of Institute of Electronics, Information and Communication Engineers, vol. J78A, pp 702-709 (1995).
[57] T. Yokota, M. Gen, Y. X. Li, “Genetic algorithm for non-linear mixed integer programming problems and its applications”, Computers and Industrial Engineering, vol. 30, pp 905-917 (1996).