ارائه یک الگوریتم جدید با ترکیب و بهبود روش‌های حریصانه و وزن‌‌دهی هزینه‌ها برای حل مسائل متنوع تخصیص افزونه

نوع مقاله: مقاله پژوهشی

نویسندگان

1 هیئت‌علمی، پژوهشگاه فضایی ایران، پژوهشکده مواد و انرژی اصفهان، ایران.

2 کارشناسی ارشد مهندسی صنایع، پژوهشگاه فضایی ایران، پژوهشکده مواد و انرژی اصفهان، ایران.

چکیده

به دلیل اهمیت موضوع قابلیت اطمینان و نقش کلیدی آن در عملکرد سیستم‌ها و میزان و ابعاد هزینه‌های آن، بهینه‌سازی قابلیت اطمینان بخصوص مسائل تخصیص افزونه (RAP) در کانون توجه طراحان قرار گرفته است. ازآنجاکه مسائل RAP بسیار متنوع و از نوع NP-hard هستند، بنابراین برای حل هر دسته از آن‌ها روش‌های مختلفی به کار گرفته شده است که اغلب طیف محدودی از این مسائل را پوشش می‌دهند. در این مقاله یک الگوریتم جدید ارائه می‌شود که با انجام برخی بهبودهای ابتکاری بر روی روش‌های حریصانه و وزن­دهی هزینه‌ها، آن‌ها را به‌گونه‌ای تلفیق می‌کند که برای حل انواع مسائل RAP با پیکربندی‌های مختلف، تنوع در قطعات و انواع استراتژی افزونگی قابل به‌کارگیری باشد. به‌کارگیری یک روش نو در وزن­دهی به هزینه‌ها، استفاده از یک شاخص حریصانه ابتکاری و مکانیزم خاص جستجو در این الگوریتم باعث افزایش سرعت، دقت و انعطاف آن در حل انواع مسائل RAP می‌شود. قابلیت‌های الگوریتم از طریق حل چند مسئله، با پیکربندی متنوع و شرایط مختلف که بعضاً فضاهای جواب بسیار بزرگی دارند نشان داده می‌شود. نتایج مبین این است که الگوریتم، قادر به حل مسائل متنوع می‌باشد و جواب‌های برابر یا بسیار نزدیک به جواب بهینه یا بهترین جواب‌های موجود را در زمان کوتاه تولید می‌کند. اجرای الگوریتم به دلیل منطق عملی و ملموسی که دارد می‌تواند بینش عملیاتی طراحان را توسعه دهد.

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

Providing a New Algorithm by Combining and Improving Greedy Method and Weighed Costs for Solving Different Redundancy Allocation Problems (RAP)

نویسندگان [English]

  • Mazaher Ziaei 1
  • fazlolah hojati 2
1 Institute of Materials and Energy, Iranian Space Research Center, Isfahan, Iran.
2 Institute of Materials and Energy, Iranian Space Research Center, Isfahan, Iran.
چکیده [English]

Due to the importance of reliability in systems performance and amount and variety of its costs, system designers have more attention to the reliability optimization, especially redundancy allocation problems (RAP). Reliability optimization problems are various and NP-hard. Thus, for any kind of them, different methods have developed which are usually suitable for limited kind of these problems. This paper provides a new algorithm (GW) that by doing some heuristic improvements on greedy method and weighed costs and combining them, it can be used for RAP with different configurations, variety of components and diversity in redundancy strategy. Using a new method of weighting costs, using an innovative greedy index and a specific search mechanism in this algorithm increas its speed, accuracy, and flexibility in solving the RAP types. The algorithm abilities are shown by solving several test problems with different conditions and variety of configurations while some of them are large. Results reveal that this algorithm is able to solve various problems and produces solutions in short time that are equal or very near to optimal solutions or the best existent solutions. GW has tangible and operational logic, therefore, it can develop the practical insight of system designers.

کلیدواژه‌ها [English]

  • Reliability optimization
  • redundancy allocation
  • Bridge system
  • Series-parallel systems

[1]      Kuo, W., Prasad, V.R., (2000). “An annotated overview of system-reliability optimization”, IEEE Transactions on Reliability, 49(2): 176-187.

[2]      Chern, M.S., (1992). “On the computational complexity of reliability redundancy allocation in a series system”, Operations Research Letters, 11(5): 309-315.

[3]      Coit, D.W., Konak, A., (2006). “Multiple Weighted Objectives Heuristic for the Redundancy Allocation Problem”, IEEE Transactions on Reliability, 55(3): 551-558.

[4]      Hsieh, Y.C., (2003). “A linear approximation for redundant reliability problems with multiple component choices”, Computers & Industrial Engineering, 44(1): 91-103.

[5]      Bulfin, R.L. and C.Y. Liu. (1985). “Optimal Allocation of Redundant Components for Large Systems”, IEEE Transactions on Reliability, 34(3): 241-247.

[6]      Misra, K.B., Sharma, U., (1991). “An efficient algorithm to solve integer-programming problems arising in system-reliability design”, IEEE Transactions on Reliability, 40(1): 81-91.

[7]      Onishi, J., Kimura, S., James, R.J.W., Nakagawa, T., (2007). “Solving the Redundancy Allocation Problem with a Mix of Components Using the Improved Surrogate Constraint Method”, IEEE Transactions on Reliability, 56(1): 94-101.

[8]      Bellman, R., Dreyfus, S., (1958). “Dynamic Programming and the Reliability of Multicomponent Devices”, Operations Research, 6(2): 200-206.

[9]      Fyffe, D.E., Hines, W.W., Lee, N.K., (1968). “System Reliability Allocation and a Computational Algorithm”, IEEE Transactions on Reliability, R-17(2): 64-69.

[10]   Nakagawa, Y., Miyazaki, S., (1981). “Surrogate Constraints Algorithm for Reliability Optimization   Problems with Two Constraints”, IEEE Transactions on Reliability, R-30(2): 175-180.

[11]   Nakagawa, Y., Nakashima, K., (1977). “A Heuristic Method for Determining Optimal Reliability Allocation”, IEEE Transactions on Reliability, R-26(3): 156-161.

[12]   Dinghua, S., (1987). “A New Heuristic Algorithm for Constrained Redundancy-Optimization in Complex Systems”, IEEE Transactions on Reliability, R-36(5): 621-623.

[13]   Agarwal, M., Gupta, R., (2005). Penalty function approach in heuristic algorithms for constrained redundancy reliability optimization, IEEE Transactions on Reliability, 54(3): 549-558.

[14]   Kumar, P., Chaturvedi, D.K., Pahuja, G.L., (2010). “Heuristic methods for solving redundancy allocation in complex systems”, International Journal of Reliability and Safety, 4(2-3): 285-298.

[15]   Coit, D.W., Smith, A.E., (1996). “Reliability optimization of series-parallel systems using a genetic algorithm”, IEEE Transactions on Reliability, 45(2): 254-266.

[16]   Levitin, G., Lisnianski, A., Ben-Haim, H., Elmakis, D., (1998). “Redundancy optimization for series-parallel multi-state systems”, IEEE Transactions on Reliability, 47(2): 165-172.

[17]   Shelokar, P.S., Jayaraman, V.K., Kulkarni, B.D., (2002). “Ant algorithm for single and multiobjective reliability optimization problems”, Quality and Reliability Engineering International, 18(6): 497-514.

[18]   Zhao, J.H., Liu, Z., Dao, M.T., (2007). “Reliability optimization using multiobjective ant colony system approaches”, Reliability Engineering & System Safety, 92(1): 109-120.

[19]   Kulturel-Konak, S., Smith, A.E., Coit, D.W., (2003). “Efficiently Solving the Redundancy Allocation Problem Using Tabu Search”, IIE Transactions, 35(6): 515-526.

[20]  جولای، فریبرز.، زارعی‌شوریجه، محمدعلی.، جویبار، سبحان. (1394). «توسعه یک روش برای حل مساله قابلیت اطمینان مبتنی بر ترکیب تکنیک شبیه‌سازی و الگوریتم بهینه‌سازی ازدحام ذرات در شرایط عدم قطعیت»، نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید، 3(5): 73-89.

[21]   Ramirez-Marquez, J.E., Coit, D.W., (2004). “A heuristic for solving the redundancy allocation problem for multi-state series-parallel systems”, Reliability Engineering & System Safety, 83(3): 341-349.

[22]   Kuo, W., Wan, R., (2007). “Recent Advances in Optimal Reliability Allocation”, IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 37(2): 143-156.

[23]   Cao, D., Murat, A., Chinnam, R.B., (2013). “Efficient xact optimization of multi-objective redundancy allocation problems in series-parallel systems”, Reliability Engineering & System Safety, 111: 154-163.

[24]   Garg, H., Sharma, S., (2013). “Multi-objective eliability-redundancy allocation problem using particle swarm optimization”, Computers & Industrial Engineering, 64(1): 247-255.

[25]   Garg, H., (2015). “An approach for solving constrained reliability-redundancy allocation problems using cuckoo search algorithm”, Beni-Suef University Journal of Basic and Applied Sciences, 4(1): 14-25.

[26]   Abouei Ardakan, M., Zeinal Hamadani, A., (2014).  “Reliability optimization of series–parallel systems with mixed redundancy strategy in subsystems”, Reliability Engineering & System Safety, 130: 132-139.

[27]   Liu, Y., Qin, G., (2014). “A Modified Particle Swarm Optimization Algorithm for Reliability Redundancy Optimization Problem,  journal of computers(9): 2124-2131.

[28]   Huang, C.L., (2015). “A particle-based simplified swarm optimization algorithm for reliability redundancy allocation problems”, Reliability Engineering & System Safety, 142:  221-230.

[29]   Kong, X., Gao, L., Ouyang, H., Li, S.,  (2015). “Solving the redundancy allocation problem with multiple strategy choices using a new simplified particle swarm optimization”, Reliability Engineering & System Safety, 144: 147-158.

[30]   Zhang, E., Chen, Q., (2016). “Multi-objective reliability redundancy allocation in an interval environment using particle swarm optimization”, Reliability Engineering & System Safety, 145: 83-92.

[31]   Feizabadi, M., Jahromi, A.E., (2017). “A new model for reliability optimization of series-parallel systems with non-homogeneous components”, Reliability Engineering & System Safety, 157: 101-112.

[32]   Ziaei, M., Hojati, F., (2014). “Using a huristic algorithm based on greedy method for reliability optimization of a series system with multiple choice and limited budget”, in 3th international reliability engineering conference.

[33]   Ahmadizar, F., Soltanpanah, H., (2011). “Reliability optimization of a series system with multiple-choice and budget constraints using an efficient ant colony approach”, Expert Systems with Applications, 38(4): 3640-3646.

[34]   Amari, S.V., Dill, G., (2010). “Redundancy optimization problem with warm-standby redundancy”, in 2010 Proceedings - Annual Reliability and Maintainability Symposium (RAMS).

[35]   Cormen, T.H., Charles, E. Leiserson. Ronald L. Rivest.  (2009). Introduction to Algorithms, Third Edition. The MIT Press.

[36]   Ushakov, I., (2013). “Optimal Resource Allocation. 1nd ed.  San Diego”, USA: John Wiley & Sons Inc.

[37]   Pardeep, K., Chaturvedi, D., Pahuja, G., (2010). “An efficient heuristic algorithm for determining optimal redundancy allocation of complex networks”, Theory & applications, 3(18): 15-28.

[38]   Jae-Hwan, K., Bong-Jin, Y., (1993). “A heuristic method for solving redundancy optimization problems in complex systems”, IEEE Transactions on Reliability, 42(4): 572-578.

[39]   Gao, J., Shan, J., Cui, H., Li, L., (2011). “A hybrid genetic algorithm with effective local search technique”, Applied Mathematics, 39: 4814-4817.

[40]   Billionnet, A., (2008). Redundancy Allocation for Series-Parallel Systems Using Integer Linear Programming,  IEEE Transactions on Reliability, 57(3): 507-516.

[41]   Lee, H., Kuo, W., Ha, C., (2003). “Comparison of max-min approach and NN method for reliability optimization of series-parallel system”, Journal of Systems Science and Systems Engineering, 12(1): 39-48.

[42]   Coit, D.W., Liu, J.C., (2000). “System Reliability Optimization With k-out-of-n Subsystems, International Journal of Reliability”, Quality and Safety Engineering, 7(2): 129-142.