2-7-4-3 نمایش مقداری…………………. 42
2-7-4-4 نمایش درختی…………………. 43
2-7-5 تابع شایستگی…………………. 43
2-7-6 عملگر انتخاب…………………. 44
2-7-6-1 انتخاب تصادفی………………… 44
2-7-6-2 انتخاب چرخ گردان……………….. 44
2-7-6-3 انتخاب رتبه بندی…………………. 46
2-7-6-4 انتخاب نخبه‌گرا ………………..47
2-7-6-5 انتخاب مسابقه‌ای…………………. 47
2-7-7 عملگر تبادل………………… 48
2-7-7-1 عملگر تبادل تک نقطه ای…………………. 48
2-7-7-2 عملگر تبادل دو نقطه ای…………………. 49
2-7-8 عملگر جهش………………….. 50
2-7-8-1 عملگر معکوس سازی…………………. 51
2-7-9 عملگر حذف و کپی…………………. 51
2-7-10 عملگر حذف وتولید مجدد………………… 52
2-7-11 پارامترهای الگوریتم ژنتیک………………….. 52
2-7-12 همگرایی…………………. 53
2-7-13 شرط خاتمه الگوریتم ژنتیک………………….. 53
2-7-14 مزایای الگوریتم ژنتیک………………….. 53
2-7-15 معایب الگوریتم ژنتیک………………….. 54
2-8 کارهای انجام شده ………………..55
2-8-1 الگوریتم ETPN-GA………………….
2-8-2 الگوریتم AFS Petri Net…………………
2-8-3 الگوریتم GA-ACO………………….
2-8-4 الگوریتم GA-Fuzzy…………………
2-8-5 الگوریتم HGA………………….
2-8-6 الگوریتم GADG………………….
2-8-7 الگوریتم های دیگر………………… 61
3 روش تحقیق…………………. 63
3-1 مراحل الگوریتم پیشنهادی…………………. 64
3-2 نمایش کروموزوم………………… 65
3-3 شرح پارامتر نگهداری ماشین…………………. 67
3-4 ایجاد جمعیت اولیه………………… 68
3-5 شایستگی…………………. 70
3-6 انتخاب…………………. 71
3-7 عملگر تبادل………………… 71
3-7-1 عملگر تبادل دو نقطه ای…………………. 72
3-7-2 عملگر تبادل تک نقطه ای………………73
3-7-3 عملگر تبادل چند نقطه ای…………………. 74
3-8 عملگر جهش………………….. 77
3-9 تعویض جمعیت…………………. 78
3-10 شرط خاتمه………………… 79
4 محاصبات و یافته های تحقیق…………………. 79
4-1 پیاده سازی الگوریتمها……………….. 80
این مطلب را هم بخوانید :
4-2 طراحی داده های تست و پارامترهای الگوریتم…….. 80
4-3 نتایج حاصل از شبیه سازی…………………. 81
5 نتیجه گیری و پیشنهادات………………… 86
فهرست منابع و مأخذ………………… 88
چکیده:
مسئله زمانبندی سیستم باز یک مسئله زمانبندی مهم و جهانی است و این مسئله به طور وسیع در صنعت کاربرد دارد. مسئله زمانبندی سیستم باز جزء مسائل سخت است. مسئله زمانبندی سیستم باز فضای راه حل آن به طور قابل ملاحظه ای بزرگتر از مسئله زمانبندی مغازه کارها است و به نظر می رسد که در کتاب ها و مقالات به آن کمتر توجه شده است. استفاده از روش های كلاسیک برای بدست آوردن جواب بهینه در این مسائل‌دارای پیچیدگی زمانی بالایی است و دربرخی از موارد غیرممكن است درنتیجه برای حل این مسائل بیشتر از روش های ابتكاری استفاده می شود. هدف مسئله زمانبندی سیستم باز بدست آوردن یک ترکیب امکان پذیر از سفارشات ماشین و کار تعیین شده است که زمان کلی اتمام کارها در کمترین زمان ممکن باشد. در بین مقالات مختلفی که در زمینه حل مسئله زمانبندی سیستم های باز ارائه شده است، هیچکدام پارامتر نگهداری ماشین ها را درنظر نگرفته اند و این درحالیست که در عمل، ماشین آلات موجود در کارخانجات بنا به دلایل مختلف دچار آسیب و خرابی در حین انجام کار می‌شوند که این امر خسارات فراوانی از جمله اتلاف زمان، و هزینه های اضافی در جهت اجرای مجدد فرایند نیمه کاره را به همراه دارد. در این پایان نامه یک روش جدید برای حل مسئله زمانبندی سیستم های باز با بهره گرفتن از الگوریتم ژنتیک ارائه شده است که مسئله نگهداری ماشین ها را نیز در نظر می گیرد. در الگوریتم پیشنهادی با بهره گرفتن از عملگرهای متنوع در کنار هدفمند کردن انتخاب کروموزوم برای کارایی هر چه بیشتر الگوریتم تلاش شده است و نتایج تجربی نشان دهنده کارایی بیشتر الگوریتم پیشنهادی در مقایسه با دیگر الگوریتمها می باشد.
فصل اول: مقدمه و کلیات تحقیق
در این فصل ابتدا مسئله مورد نظر بیان گردیده و ضرورت و اهداف را دنبال مینمایم در ادامه پرسشهای موجود در مسئله را بررسی مینمایم و فرضیه های تحقیق را شرح میدهم سپس نوآوریهای تحقیق را ارائه مینمایم در پایان واژههای کلیدی تعریف شده و ساختار پایان نامه ذکر خواهد شد.
