بخشی از مقاله
کلمات کلیدي: قابلیت اطمینان، تخصیص افزونگی، سیستم هاي سري موازي، شبیه سازي مونت کارلو، الگوریتم NSGA-II، الگوریتم MOPSO
چکیده
در این مقاله به مدل سازي و حل مسئلهي تخصیص افزونگی براي سیستمهاي سري- موازي پرداختهایم. در این مسئله فرض شده است که هر در زیرسیستم میتوان از بین انتخاب هاي موجود یک جزء را براي قرارگیري انتخاب کرد و به تعدادي از آن جزء در آن زیرسیستم قرار داد، که این اجزاء در وزن و هزینه با یکدیگر متفاوتند. پس از تصمیمگیري در مورد نوع و تعداد اجزاي انتخابی، به هر زیرسیستم اجازه داده میشود تا جهت محاسبهي متوسط زمان تا خرابی - MTTF - ، یک نوع تابع توزیع احتمال را انتخاب کند. بدلیل پیچیدگی محاسبه متوسط زمان تا خرابی براي هر یک از زیرسیستمها، در این مقاله از شبیه سازي مونت کارلو استفاده شده است. از آنجا که این مدل از مسائل NP-Hard میباشد، براي بدست آوردن جوابهاي قابل قبول نیاز به الگوریتمهاي فراابتکاري است که الگوریتم هاي بهینه سازي چندهدفهي NSGA-II و MOPSO براي حل این مسئله توسعه داده شده است. در پایان مثالهاي عددي براي ارزیابی الگوریتمها ارائه شده و دو الگوریتم به لحاظ کارایی با هم مقایسه شدهاند.
مقدمه و مرور ادبیات
در سالهاي اخیر روند شتابندهي توسعهي دانش و فنĤوريهاي در دست بشر و از طرفی دستیابی به زمینههاي نوین علوم و تکنولوژي، منجر به طراحی، ساخت و تولید سیستمها و تجهیزات پیچیده و حساس مهندسی شده است. این سامانههاي پیشرفته عموما در صنایع بسیار حساسی نظیر صنایع وابسته به خودرو، صنایع هوایی، دفاعی و نظیر آنها کاربرد دارند. از آنجایی که نقص در عملکرد چنین سیستمهایی ممکن است منجر به بروز خسارات شدید و جبران ناپذیر جانی و مالی شود، حصول اطمینان از عملکرد درست آنها در بازههاي زمانی موردنظر، از ملزومات اصلی در طراحی و ساخت آنها میباشد. نظر به اهمیت موضوع یاد شده، در سالیان اخیر طراحان پارامترهاي طراحی جدیدي را تدوین و در محصولات خود لحاظ کردهاند، که یکی از مهمترین آنها قابلیت اطمینان - پایایی - است.
در حالت کلی، پایایی، توانایی یک جزء یا سیستم در انجام و حفظ عملکرد صحیح خود در زمان معین و در شرایط تعیین شده می- باشد. یکی از روشهاي بهبود پایایی سیستم، اضافه نمودن اجزاي مازاد - افزونگی - به سیستم میباشد. البته به دلیل محدودیتهاي موجود در سیستم، اضافه نمودن اجزاي افزونه به آن محدود میباشد. در نتیجه محققین همواره به دنبال روشها و رویکردهایی بودهاند که بهترین ترکیب ممکن از اجزاي افزونه را به سیستم تخصیص دهند تا پایایی آن بیشینه شود. با توجه به اینکه چنین مسائلی در دستهي مسائل NP-Hard قرار دارند، جهت حل آنها نیاز به استفاده از الگوریتمهاي ابتکاري و فراابتکاري میباشد.
شایان ذکر است به دلیل ساختار خاص مسئلهي تخصیص افزونگی به سیستمهاي سري- موازي، نیاز به الگوریتمهاي ترکیبی و کارآمد که با توجه به ساختار این مسئله شکل گرفته باشد، احساس میشود. فیفه و همکاران1یک مدل ریاضی براي مسئلهي تخصیص افزونگی معرفی کردند که باعث شد این مسئله مورد توجه بیشتري قرار گیرد و برخی از محققان مدلهاي حل و الگوریتمهاي خود را براي حل این مسئله ارائه کنند. آنها مسئلهي RAP با محدودیتهاي وزن و هزینهي سیستم را با استفاده از برنامه ریزي پویا حل کردند.[1]
چرن2 نشان داد که حتی سادهترین شکل مساله تخصیص افزونگی با محدودیتهاي خطی، یک مساله NP-HARD بوده و اغلب یافتن جواب موجه براي آن با توجه به چندین محدودیت، کار بسیار دشواري است. بنابراین تعیین جواب دقیق براي مسائل با اندازه نسبتا متوسط، دشوار و براي مسائل با اندازه بزرگ قطعا غیرممکن است. فیفه و همکاران3 یک مدل ریاضی براي مسئلهي تخصیص افزونگی معرفی کردند که باعث شد این مسئله مورد توجه بیشتري قرار گیرد.
تکنیکهاي بهینهسازي که بر پایههاي رویکردهاي فراابتکاري استوار میباشد، اخیرا براي حل مسائل تخصیص افزونگی با ترکیبی از اجزاء ارائه شدهاند. هرچند روش حل دقیقی توسعه داده نشده است. با توجه به مسائل مربوط به اجزاي چندانتخابه، مطالعات وسیعی انجام شدهاند. ناکاگاوا و میازاکی4 یک الگوریتم پیشرفته برنامهریزي پویا ارائه نمودهاند تا با استفاده از آن، مسائل اصلی مطرح شده توسط فیفه و همکاران را حل کنند.[2] از آن پس الگوریتمهاي فرابتکاري مختلف برپایه جریمهاي براي بهبود جوابهاي این مسائل ارائه شدند. براي مثال میتوان به الگوریتم ژنتیک - کویت و اسمیت[3] - 5، جست و جوي ممنوعه - کالتورل- کوناك، اسمیت و کویت[4] - 6، تبرید شبیه سازي شده - کیم، باي و پارك[5] - 1، بهینه سازي کلونی مورچگان - لیانگ و اسمیت[6] - 2، ترکیب روش حریصانه و الگوریتم ژنتیک - یو و چن[7] - 3، الگوریتم ایمن - 4چن و یو[8] - 5، الگوریتم نزولی همسایگی متغیر6 - لیانگ و وو[9] - 7، جست و جوي همسایگی متغیر8 متغیر8 - لیانگ و چن[10] - 9، ترکیب الگوریتم کلونی مورچگان و الگوریتم سقف تخریب شده - 10 نهاس، نورالفتح و آیت کادي - 11 [11] اشاره کرد.
علاوه بر رویکردهاي برنامهریزي خطی ساده12، - هیسه[12 ] - 13، الگوریتم ابتکاري - هیوریستیک - بیشینه- کمینه14 - رامیرز – مارکوئز، کویت و کوناك[13] - 15، الگوریتم ابتکاري - هیوریستک - تابع هدف چندگانه وزن دار16 - کویت و کوناك[14] - 17، سیستم کلونی مورچگان تابع هدف چندگانه18 - ژو، لیو و دائو[15] - 19، و روش محدودیت جانشین بهبود یافته20 - اونیشی، کیمورا، راس جیمز و ناکاگاوا[16] - 21، رویکردهایی هستند که براي حل دقیق مسائلی که قبلا به آنها اشاره شد، ارائه شدهاند. در مقاله اخیر دو روش حل دقیق بر پایهي روش ISC توسعه داده شده و از آن براي حل بهینهي مسائل استفاده شده است.
پینتون و کمپبل [17] و کمپبل و پنیتون[18] 22 یک مسئلهي بهینه سازي را حل نمودند که در آن توزیع زمان کار اجزاء تا خرابی از توزیع نمایی پیروي میکند، اما خود پارامتر توزیع نیز متغیر تصادفی میباشد. آنها با استفاده از الگوریتم ژنتیک سعی در بیشینه نمودن زمان متوسط بین خرابیها داشتهاند. رابینشتین و همکاران[19] 23 نیز از الگوریتم ژنتیک براي حل مسئلهي تخصیص افزونگی با در نظر گرفتن عدم قطعیت در مشخصهي اجزاء سود بردند. اوکشاف و هریسون[20] 24 و ندنکو و اوکشاف25 [21] الگوریتمهایی را براي بیشینه نمودن زمان متوسط تا خرابی ارائه نمودند.
