A corridor method based hybrid algorithm for redundancy allocation
Tóm tắt
In this paper a hybrid algorithm for the redundancy allocation problem is presented. The problem is the allocation of redundant components within series-parallel systems. We present an algorithm that deals with the classical formulation, where at least one component per subsystem must be included in the final configuration, as well as the
$$k$$
-out-of-
$$n$$
formulation, in which at least
$$k$$
components per subsystem must be included in the final network configuration. We propose a three-phase scheme in which the cross entropy method, the corridor method and a dynamic programming-based scheme are effectively intertwined. Computational results on well-known benchmark instances as well as on randomly generated large scale instances are presented, proving the effectiveness and robustness of the proposed algorithm.
Tài liệu tham khảo
Altiparmak, F., Dengiz, B., Smith, A.E.: Optimal design of reliable computer networks: a comparison of metaheuristics. J. Heuristics 9, 471–487 (2003)
Belli, F., Jedrzejowicz, P.: An approach to the reliability optimization of software with redundancy. IEEE Trans. Softw. Eng. 17(3), 310–312 (1991)
Berman, O., Ashrafi, N.: Optimal design of large software-systems using N-version programming. IEEE Trans. Reliab. 43(2), 344–350 (1994)
Billionnet, A.: Redundancy allocation for series-parallel systems using integer linear programming. IEEE Trans. Reliab. 57(3), 507–516 (2008)
Bulfin, R.L., Liu, C.Y.: Optimal allocation of redundancy components for large systems. IEEE Trans. Reliab. R–34(3), 241–247 (1985)
Caserta, M., Márquez, A.: Tabu search-based metaheuristic algorithm for software system reliability problems. Comput. Operat. Res. 36(3), 811–822 (2009)
Caserta, M., Quiñonez, E.: A Cross entropy-lagrangean hybrid algorithm for the multi-item capacitated lot-sizing problem with setup times. Comput. Operat. Res. 36, 530–548 (2009)
Caserta, M., Voß, S.: Corridor selection and fine tuning for the corridor method. Lect. Notes Comput. Sci. 5851, 163–175 (2009)
Caserta, M., Voß, S.: A discrete-binary transformation of the reliability redundancy allocation problem. Technical report, University of Hamburg, Institute of Information Systems, (2011)
Caserta, M., Voß, S.: A math-heuristic Dantzig-Wolfe algorithm for capacitated lot sizing. Ann. Math. Artif. Intell. 69, 207–224 (2013a)
Caserta, M., Voß, S.: An exact algorithm for the reliability redundancy allocation problem. Technical report, University of Hamburg, Institute of Information Systems, (2013b)
Caserta, M., Voß, S., Sniedovich, M.: Applying the corridor method to a blocks relocation problem. OR Spectr 33, 915–929 (2011)
Chern, M.-S.: On the computational complexity of reliability redundancy allocation in a series system. Oper. Res. Lett. 11, 309–315 (1992)
Coit, D.W., Konak, A.: Multiple weighted objectives heuristic for the redundancy allocation problem. IEEE Trans. Reliab. 55(3), 551–558 (2006)
Coit, D.W., Smith, A.E.: Reliability optimization of series-parallel systems using a genetic algorithm. IEEE Trans. Reliab. 45(2), 254–266 (1996)
Coit, D.W., Liu, J.: System reliability optimization with k-out-of-n subsystems. Int. J. Reliab. Qual. Saf. Eng. 7(02), 129–142 (2000)
De Boer, P., Kroese, D.P., Mannor, S., Rubinstein, R.Y.: A tutorial on the cross-entropy method. Ann. Oper. Res. 134, 19–67 (2005)
Deeter, D.E., Smith, A.E.: Economic design of reliable networks. IIE Trans. 30, 1161–1174 (1998)
Fréville, A.: The multidimensional 0–1 knapsack problem: an overview. Eur. J. Oper. Res. 155(1), 1–21 (2004)
Ha, C., Kuo, W.: Reliability redundancy allocation: an improved realization for nonconvex nonlinear programming problems. Eur. J. Oper. Res. 127, 24–38 (2006)
Hsieh, Y.C.: A linear approximation for redundant reliability problems with multiple component choices. Comput. Ind. Eng. 44, 91–103 (2002)
Kim, H.G., Bae, C.O., Park, D.J.: Reliability redundancy optimization using simulated annealing algorithms. J. Qual. Maint. Eng. 12(4), 354–363 (2006)
Kulturel-Konak, S., Smith, A.E., Coit, D.W.: Efficiently solving the redundancy allocation problem using tabu search. IIE Trans. 35(6), 515–526 (2003)
Kuo, W., Prasad, V.R.: An annotated overview of system-reliability optimization. IEEE Trans.Reliab. 49(2), 176–187 (2000)
Kuo, W., Prasad, V.R., Tillman, F.A., Hwang, C.: Optimal Reliability Design. Cambridge University Press, New York (2001)
Kuo, W., Wan, R.: Recent advances in optimal reliability allocation. IEEE Trans. Syst. Man Cybern. A 37(2), 143–156 (2007)
Liang, Y.-C., Chen, Y.-C.: Redundancy allocation of series-parallel systems using a variable neighborhood search algorithm. Reliab. Eng. Syst. Saf 92(3), 323–331 (2007)
Liang, Y.C., Smith, A.E.: An ant colony optimization algorithm for the redundancy allocation problem (RAP). IEEE Trans. Reliab. 53(3), 417–423 (2004)
Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, New York (1990)
Nahas, N., Nourelfath, M., Ait-Kadi, D.: Coupling ant colony and the degraded ceiling algorithm for the redundancy allocation problem of series-parallel systems. Reliab. Eng. Syst. Saf. 92(2), 211–222 (2007)
Nakawara, Y., Miyazaki, S.: Surrogate constraints algorithm for reliability optimization problems with two constraints. IEEE Trans. Reliab. 30(2), 175–180 (1981)
Ng, K.Y., Sancho, N.G.: A hybrid dynamic programming/depth first search algorithm, with an application to redundancy allocation. IIE Trans. 33, 1047–1058 (2001)
Onishi, J., Kimura, S., James, R.J., Nakagawa, Y.: Solving the redundancy allocation problem with a mix of components using the improved surrogate constraint method. IEEE Trans. Reliab. 56(1), 94–101 (2007)
Ouzineb, M., Nourelfath, M., Gendreau, M.: An efficient heuristic for reliability design optimization problems. Comput. Oper. Res. 37, 223–235 (2010)
Painton, L., Campbell, J.: Genetic algorithms in optimization of system reliability. IEEE Trans. Reliab. 44, 172–178 (1995)
Ramirez-Marquez, J.E., Coit, D.W., Konak, A.: Redundancy allocation for series-parallel systems using a max-min approach. IIE Trans. 36, 891–898 (2004)
Rubinstein, R.Y., Kroese, D.P.: The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte Carlo Simulation, and Machine Learning. Springer, New York (2004)
Sadjani, S.J., Soltani, R.: An efficient heuristic versus a robust hybrid metaheuristic for general framework of serial-parallel redundancy problem. Reliab. Eng. Syst. Saf. 94(11), 1703–1710 (2009)
Sniedovich, M., Voß, S.: The corridor method: a dynamic programming inspired metaheuristic. Control Cybern. 35(3), 551–578 (2006)
Taillard, E., Voß, S.: POPMUSIC—Partial Optimization Metaheuristic Under Special Intensification Conditions. In: Ribeiro, C.C., Hansen, P. (eds.) Essays and Surveys in Metaheuristics, pp. 613–629. Kluwer, Boston (2002)
Tavakkoli-Moghaddam, R., Safari, J., Sassani, F.: Reliability optimization of series-parallel systems with a choice of redundancy strategies using a genetic algorithm. Reliab. Eng. Syst. Saf. 93(4), 550–556 (2008)
Twum, S.B., Aspinwall, E.: Models in design for reliability optimisation. Am. J. Sci. Ind. Res. 4(1), 95–110 (2013)
Yalaoui, A., Châtelet, E., Chu, C.: A new dynamic programming method for reliability & redundancy allocation in a parallel-series system. IEEE Trans. Reliab. 54(2), 254–261 (2005)
You, P.S., Chen, T.C.: An efficient heuristic for series-parallel redundant reliability problems. Comput. Oper. Res. 32, 2117–2127 (2005)