این پایان نامه را ضمن تشکر و سپاس بیکران و در کمال افتخار و امتنان تقدیم می نمایم به:
محضر ارزشمند پدر و مادر عزیزم به خاطر همه تلاشهای محبت آمیزی که در دوران مختلف زندگیام انجام داده اند و بامهربانی چگونه زیستن را به من آموخته اند.
به همسر مهربانم که در تمام طول تحصیل همراه و همگام من بوده است .
به استادان فرزانه و فرهیخته ای که در راه کسب علم و معرفت مرا یاری نمودند .
به آنان که در راه کسب دانش راهنمایم بودند .
به آنان که نفس خیرشان و دعای روح پرورشان بدرقه ی راهم بود.
الها به من کمک کن تا بتوانم ادای دین کنم و به خواسته ی آنان جامه ی عمل بپوشانم. پروردگارا حسن عاقبت ، سلامت و سعادت را برای آنان مقدر نما. خدایا توفیق خدمتی سرشار از شور و نشاط و همراه و همسو با علم و دانش و پژوهش جهت رشد و شکوفایی ایران کهنسال عنایت بفرما.
چکیده
مسئله زمانبندی سیستم باز1 یک مسئله زمانبندی مهم و جهانی است و این مسئله به طور وسیع در صنعت کاربرد دارد. مسئله زمانبندی سیستم باز جزء مسائل سخت2 است. مسئله زمانبندی سیستم باز فضای راه حل آن به طور قابل ملاحظه ای بزرگتر از مسئله زمان‌بندی مغازه کارها3 است و به نظر می رسد که در کتاب ها و مقالات به آن کمتر توجه شده است. استفاده از روش های کلاسیک برای بدست آوردن جواب بهینه در این مسائل‌دارای پیچیدگی زمانی بالایی است و دربرخی از موارد غیرممکن است درنتیجه برای حل این مسائل بیشتر از روش های ابتکاری استفاده می شود. هدف مسئله زمانبندی سیستم باز بدست آوردن یک ترکیب امکان پذیر از سفارشات ماشین و کار تعیین شده است که زمان کلی اتمام کارها4 در کمترین زمان ممکن باشد. در بین مقالات مختلفی که در زمینه حل مسئله زمانبندی سیستم های باز ارائه شده است، هیچکدام پارامتر نگهداری ماشین ها5 را درنظر نگرفته اند و این درحالیست که در عمل، ماشین آلات موجود در کارخانجات بنا به دلایل مختلف دچار آسیب و خرابی در حین انجام کار می‌شوند که این امر خسارات فراوانی از جمله اتلاف زمان، و هزینه های اضافی در جهت اجرای مجدد فرایند نیمه کاره را به همراه دارد. در این پایان نامه یک روش جدید برای حل مسئله زمانبندی سیستم های باز با استفاده از الگوریتم ژنتیک ارائه شده است که مسئله نگهداری ماشین ها را نیز در نظر می گیرد. در الگوریتم پیشنهادی با استفاده از عملگرهای متنوع در کنار هدفمند کردن انتخاب کروموزوم برای کارایی هر چه بیشتر الگوریتم تلاش شده است و نتایج تجربی نشان دهنده کارایی بیشتر الگوریتم پیشنهادی در مقایسه با دیگر الگوریتمها می باشد.
کلمات کلیدی: مسئله زمانبندی سیستمهای باز، الگوریتم ژنتیک ، نگهداری ماشین ، زمان کلی اتمام کار
فهرست مطالب
1 فصل اول مقدمه و کلیات تحقیق 1
1-1 مقدمه 2
1-2 بیان مسئله 2
1-3 ضرورت تحقیق 5
1-4 اهداف تحقیق 5
1-5 نوآوری تحقیق 6
1-6 پرسشهای اصلی تحقیق 6
1-7 فرضیه های تحقیق 7
1-8 زمینه های کاربردی 7
1-8-1 تخصیص گیت در یک فرودگاه 8
1-8-2 زمانبندی در یک واحد پردازش مرکزی 9
1-8-3 زمانبندی در پالایشگاه نفت 10
1-8-4 کارخانه تولید پاکت کاغذی 10
1-8-5 کارخانه تولید تجهیزات لامپ های صنعتی 11
1-9 تعریف کلمات کلیدی 12
1-10 ساختار پایان نامه 14
2 فصل دوم ادبیات و پیشینه تحقیق 15
1-2 مقدمه 16
2-2 تعریف مربوط به زمانبندی 16
2-3 زمانبندی از دیدگاهی دیگر 18
2-4 نظریه زمانبندی 19
2-5 مروری بر مدل های زمان بندی 20
1-5-2 چارچوب و نمادها 20
2-5-2 ترکیب ماشین ها (محیط های کار) 21
2-5-3 مدل های تک ماشینه 22
2-5-4 مدل های ماشین موازی 23
2-5-5 مدل های جریان کارگاهی 24
2-5-6 مدل های کار کارگاهی 28
2-5-7 مدل های کارگاه باز 31
2-5-8 مدل های کارگاه وابسته 33
2-5-9 مدل های پردازش دسته ای 33
2-5-10 مدل های خط مونتاژ 33
2-5-11 مدل های خط مونتاژ ترکیبی 34
2-6 محدودیت های زمانبندی 34
2-6-1 معیارهای ارز یابی عملکرد 36
2-7 الگوریتم ژنتیک 38
2-7-1 تکنیک‌های حل مسائل بهینه سازی 38
2-7-2 صورت کلی الگوریتم ژنتیک 40
2-7-3 تعاریف 41
2-7-4 نمایش کروموزوم 41
2-7-4-1 نمایش باینری 41
2-7-4-2 نمایش جایگشتی 42
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 55
2-8-2 الگوریتم AFS Petri Net 55
2-8-3 الگوریتم GA-ACO 56
2-8-4 الگوریتم GA-Fuzzy 58
2-8-5 الگوریتم HGA 59
2-8-6 الگوریتم GADG 60
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
فهرست جداول
جدول ‏11: مساله معیاری برای 5 کار و 5 ماشین 4
جدول ‏21: نمایش برخی از محیط های مختلف کار در مسائل زمان بندی با پارامتر α 22
جدول ‏22: نمایش بعضی از محدودیت های مسائل زمان بندی با پارامتر β 34
جدول ‏23: نمایش بعضی از معیارهای به کار رفته در مسائل زمانبندی با پارامتر  36
جدول ‏24: احتمال انتخاب در روش چرخ گردان برای داده‌های فرضی 45
جدول ‏41: پارامترهای ورودی الگوریتم پیشنهادی 80
جدول ‏42: نتایج اجرای داده های تست جدول 4-1 81
فهرست تصاویر
شکل ‏21: مساله معیاری برای 5 کار و 5 ماشین 5
شکل ‏21: رابطه تقذم برای N کار 25
شکل ‏22: مساله 3 کار 26
شکل ‏23: نمونه اول زمانبندی 26
شکل ‏24: نمونه ای دیگر از زمانبندی 26
شکل ‏25: قاعده جانسون 27
شکل ‏26: مساله 3 کار و 3 ماشین 30
شکل ‏27: نمودار گانت بر طبق ماشین 30
شکل ‏28: نمودار گانت بر اساس کار 31
شکل ‏29: تکنیک بکار برده شده برای مسائل JOB SHOP 31
شکل ‏210: دسته بندی استراتژی‌های جستجو 39
شکل ‏211: مراحل کلی الگوریتمهای تکاملی 40
شکل ‏212: نمایش کروموزوم به صورت درختی 43
شکل ‏213: احتمال انتخاب در روش چرخ گردان 46
شکل ‏214: احتمال انتخاب در روش رتبه بندی 47
شکل ‏215: انتخاب مسابقه‌ای 48
شکل ‏216: عملگر تبادل تک نقطه ای 49
شکل ‏217: عملگر تبادل دو نقطه ای 50
شکل ‏218: عملگر معکوس سازی 51
شکل ‏219: عملگر حذف و کپی 51
شکل ‏220: عملگر حذف و تولید مجدد 52
شکل ‏221: مراحل الگوریتم GA-ACO 57
شکل ‏222: عملگر مبتنی بر کار 58
شکل ‏223: عملگر جهش شیفتی 58
شکل ‏224: یک کروموزوم نمونه در الگوریتم GA-FUZZY 59
شکل ‏225: یک کروموزوم نمونه در الگوریتم HGA 59
شکل ‏226: فلوچارت الگوریتم HGA 60
شکل ‏227: یک کروموزوم نمونه در الگوریتم GADG 61
شکل ‏31: فلوچارت الگوریتم پیشنهادی 65
شکل ‏32: یک کروموزوم نمونه 66
شکل ‏33: نگهداری ماشین وابسته به سن ماشین 67
شکل ‏34: یک کروموزوم نمونه با در نظر گرفتن نگهداری ماشین 68
شکل ‏35: نمودار گانت شکل 3-4 68
شکل ‏36: ایجاد جمعیت اولیه با استفاده از ویژگی چند جمعیتی 69
شکل ‏37: عملگر تبادل دو نقطه ای 72
شکل ‏38: عملگر تبادل تک نقطه ای 73
شکل ‏39: عملگر تبادل چند نقطه ای 74
شکل ‏310: عملگر جهش دو نقطه ای 77
شکل ‏41: نمودار مقایسه بهترین شایستگی الگوریتم ها برای داده تست 1 82
شکل ‏42: نمودار مقایسه بهترین شایستگی الگوریتم ها برای داده تست 3 82
شکل ‏43: نمودار بهترین شایستگی الگوریتم ها برای داده تست 4 83
شکل ‏44: پراکندگی جمعیت اولیه برای داده تست 2 83
شکل ‏45: پراکندگی جمعیت اولیه برای داده تست 4 84
فصل اول مقدمه و کلیات تحقیق
در این فصل ابتدا مسئله مورد نظر بیان گردیده و ضرورت و اهداف را دنبال مینمایم در ادامه پرسشهای موجود در مسئله را بررسی مینمایم و فرضیههای تحقیق را شرح میدهم سپس نوآوریهای تحقیق را ارائه مینمایم در پایان واژههای کلیدی تعریف شده و ساختار پایان نامه ذکر خواهد شد.
مقدمه
مسئله زمانبندی سیستم های باز یکی از مهمترین مسائل زمانبندی در دنیای مهندسی و صنعت است. در این مسئله m ماشین و n کار وجود دارد. هرکار شامل تعداد معینی از عملیات است. هر عملیات دارای زمان از پیش تعیین شده ای برای پردازش6 بر روی ماشین متناظر خود می باشد. ترتیب پردازش این عملیات در زمان به انجام رسیدن همه کارها بسیار تاثیر گذار است. بنابراین هدف از حل این مسئله پیدا کردن ترتیب عملیاتی است که با کمترین مدت زمانبندی قابل پردازش باشد. در این راستا مقالات زیادی با استفاده از الگوریتم های ابتکاری7 مختلف ارائه شده است که از بین آنها الگوریتم ژنتیک8 یکی از بهترین ها، شناخته شده است. در این پایان نامه یک روش جدید برای حل مسئله زمانبندی با در نظر گرفتن پارامتر نگهداری ماشین9 ها بر پایه الگوریتم ژنتیک با ویژگی چند جمعیتی10 ارائه شده است. نتایج تجربی نشان می دهد الگوریتم ارائه شده به جواب بهینه تری دست پیدا میکند [77].
بیان مسئله
مسئله زمانبندی سیستم باز یک مسئله زمانبندی مهم و جهانی است و این مسئله به طور وسیع در صنعت کاربرد دارد. این مسئله جزء مسائل سخت است. این مسئله شبیه به مسئله زمانبندی مغازه کارها است با این تفاوت که در هر کار11 هیچ اولویتی بین فرایند یا عملیات هر کار وجود ندارد. در مسئله زمانبندی سیستم باز فضای راه حل به طور قابل ملاحظهای بزرگتر از مسئله زمان بندی مغازه کارها است و به نظر میرسد که در کتاب ها و مقالات به آن کمتر توجه شده است. شرح مسئله سیستم باز توسط گراهام و همکارانش بدین صورت باشد: یک تعداد کار به تعداد n (J1,J2, … , Jn) وجود دارد که روی یک سلسله ماشین به تعداد m (M1,M2, … , Mm) قابل پردازش است، هر کار متشکل از m عملیات می باشد (Oij). که j=1 to m و i=1 to n و هر کدام از عملیات باید روی یک ماشین

این مطلب رو هم توصیه می کنم بخونین:   منابع پایان نامه درموردتلفن همراه، evaluation، Technology
دسته‌ها: No category

دیدگاهتان را بنویسید