۰٫۱۹۳۱
۱۹
۱۰۰
۱۲
-
-
۸۸٫۲۰۹۱
۸۴٫۴۴۷
۰۰:۰۰:۱۰۲٫۶۷۳
۰٫۴۲۲۷
۸۶٫۹۰۱۲
۸۴٫۲۴۷۶
۰۰:۰۰:۲۰٫۰۵۶۱
۰٫۱۵۷۴
۲۰
۱۰۰
۱۵
-
-
۷۷٫۵۸۹۱
۷۰٫۸۴۵۴
۰۰:۰۰:۹۲٫۰۱۲
۰٫۴۷۵۹
۷۳٫۰۱
۷۰٫۲۱۱۶
۰۰:۰۰:۱۹٫۳۰۶
۰٫۱۹۹۲
جدول۵-۴٫ نتایج بدست آمده از روش دقیق، الگوریتم ژنتیک و رقابت استعماری
همانطوری که نتایج مشاهده می شود زمان محاسباتی مربوط به الگوریتم دقیق با بزرگ شدن اندازه نمونهها افزایش مییابد. به طوری که در جدول نیز وجود دارد در اندازه الگوریتم دقیق در مدت زمان ۰۰:۴۰:۲۳ به جواب بهینه دست یافته است در حالی که برای اندازه ۲ ۱۰الگوریتم دقیق بعد از مدت یک ساعت به هیچ جواب بهنه محلی یا بهینه جهانی نمیرسد. نتایج مربوط به الگوریتم ژنتیک فراابتکاری را در ادامه مورد بررسی قرار میدهیم.
۴-۵-۳٫ تحلیل نمودارRPD و زمان محاسباتی الگوریتم ژنتیک و رقابت استعماری
شکل ۴-۶٫ نمودار RPD مربوط به الگوریتم ژنتیک و رقابت استعماری
همانطوری که در بخش قبل اشاره شد برای بررسی عملکرد الگوریتمهای فراابتکاری پیشنهادی از معیار RPD استفاده شده است که RPD ارائه شده در این جدول برابر میانگین RPD های محاسبه شده برای ۵ بار اجرای هر مسئله میباشد. برای مشاهده روند تغییرات معیار RPD به ازای تغییرات ابعاد مسئله نمودار مربوط به آنها در شکل ۴-۶ نمایش داده شده است. همانطور که از این نمودار مشخص است برای مسئلههای با اندازه کوچک مقادیر RPD هر دو الگوریتم برابر صفر میباشد که نشان از عملکرد صحیح الگوریتم ژنتیک و رقابت استعماری پیشنهادی دارد. در مسائل با ابعاد بزرگتر که روش دقیق قادر به حل مساله در زمان معقول نمی باشد مقدار RPD با توجه به بهترین حل بدست آمده از روش الگوریتم ژنتیک و رقابت استعماری در ۵ تکرار محاسبه میگردد. در نموار ارائه شده در شکل۴-۶ مشاهده میگردد که در الگوریتم ژنتیک با افزایش اندازه مسئله از ۱۵ کار به ۳۰ کار مقدار RPD با یک رشد ناگهانی مواجه شده است اما از ۳۰ کار به بالا با افزایش تعداد کار و ماشین مقادیر RPD با یک روند صعودی ملایم افزایش مییابند. ولی در الگوریتم رقابت استعماری مقدار RPD از شیب کمتری نسبت به الگوریتم ژنتیک برخوردار است که نشاندهنده عملکرد بهتر این الگوریتم در مقایسه با الگوریتم ژنتیک میباشد.
معیار دیگری که برای بررسی عملکرد الگوریتمهای پیشنهادی ارائه شده است زمان حل مسائل توسط الگوریتمها میباشد که نمودار زمان محاسباتی الگوریتم ژنتیک و رقابت استعماری پیشنهادی به ازای اندازه های مختلف مسئله در شکل ۴-۷ ارائه شده است.
شکل ۴‑۷٫ نمودار زمان محاسباتی الگوریتم ژنتیک و رقابت استعماری
همانطور که در نمودار موجود در شکل ۴-۷ مشاهده میگردد، زمان محاسباتی مربوط به مسائل با ابعاد کوچک در مقایسه با حل دقیق بسیار ناچیز میباشد. زمان محاسباتی الگوریتم ژنتیک در مقایسه با الگوریتم رقابت استعماری به طور قابل توجهی بیشتر میباشد و دارای شیب بیشتری نسبت به الگوریتم رقابت استعماری میباشد.
۴-۶٫جمعبندی
در این فصل مدل زمانبندی روی ماشینهای موازی غیر مرتبط همراه با عملیات نگهداری با تاثیرات همزمان یادگیری و استهلاک ارائه شده است. مدل ارائه شده مورد اعتبارسنجی قرار گرفته و سپس بعد از اشاره به Np-hard بودن مسئله به شرح الگوریتمها ومزایا و معایب آن پرداخته و در انتها به ارائه الگوریتم ژنتیک و رقابت استعماری پیشنهادی برای مسئله مطرح شده پرداخته و جزئیات آن تشریح گردیده است.در ادامه برای همگرایی سریع الگوریتمهای ارائه شده به بهترین جواب ، یک تنظیم پارامتر با بهره گرفتن از روش تاگوچی ارائه شد. برای سنجش الگوریتم از شاخص درصد انحراف نسبی RPD استفاده شده است و در ادامه مسائل تولید شده توسط روشهای پیشنهادی اجرا گردید و نتایج در قالب جداول و نمودارها ارائه ، تحلیل و بررسی شده اند. با توجه به بررسیهای انجامشده ، نتایج حاصله از الگوریتم رقابت استعماری پیشنهادی دارای کیفیت بالاتری نسبت به الگوریتم ژنتیک برخوردار بوده اند که این کیفیت شامل RPD و زمان محاسباتی الگوریتم میباشد که به میزان قابل توجهی از الگوریتم ژنتیک کمتر بوده است . پس الگوریتم پیشنهادی این تحقیق طبق نتایج بدستآمده الگوریتم رقابت استعماری میباشد.
فصل پنجم
نتیجه گیری و پیشنهادات آتی
۵-۱٫ جمعبندی
در این تحقیق مسئله زمانبندی ماشینهای موازی غیر مرتبط با توجه به اثرات همزمان یادگیری و استهلاک و فعالیتهای نگهداری ارائه شده است که هدف حداقل کردن بیشترین زمان تکمیل و یافتن بهترین مکان و دفعات بهینه عملیات نگهداری و ترتیب بهینه کارها میباشد. یک مدل خطی برنامه ریزی عدد صحیح برای این مسئله ارائه شده است، در ادامه با توجه به اینکه این مسئله از دسته مسائل پیچیده میباشد از روش های فراابتکاری برای حل آن استفاده شده است. در این تحقیق دو الگوریتم ژنتیک و رقابت استعماری برای مسئله پیشنهاد شده است. برای بررسی عملکرد الگوریتمهای پیشنهادی، آنها را برای مسائل با ابعاد مختلف اجرا نموده و نتایج حاصله را با معیارهای مناسبی که معرفی شده است تحلیل نموده ایم. بررسیها نشان از عملکرد نسبتا مناسب الگوریتم رقابت استعماری برای مسئله مورد نظر دارد. در ادامه به پیشنهاداتی مناسب جهت مطالعات آتی در ادامه موضوع مطرح شده در این پایان نامه می پردازیم.
۵-۲ پیشنهادات آتی
مسائل زمانبندی و مدلهای آنها بسیار گسترده هستند و دارای پتانسیل زیادی برای بررسی در تحقیقات آینده میباشند. همچنین میتوان با در نظر گرفتن فرضیات جدید، مدلهای سابق را توسعه داد و آنها را به شرایط واقعیتر و کاربردیتر نزدیک کرد. پیشنهادات این تحقیق در ادامه ارائه میگردد.
فرم در حال بارگذاری ...
