فرضیات مسئله ماشینهای موازی این مطالعه 3
اهداف تحقیق 4
1-5. جنبههای نوآوری تحقیق 4
1-6. محتویات تحقیق 4
1-7. جمعبندی 4
فصل دوم: ادبیات نظری و پیشینه تحقیق
2-1. مقدمه 7
2-2. تعربف اثر یادگیری در فن زمانبندی 7
2-3. تعریف نگهداری و تعمیرات در زمانبندی 9
2-4. ادبیات و پیشینه تحقیق 10
2-4-1. مسائل ماشینهای موازی 10
2-4-2. مروری بر مطالعات زمانبندی با اثر یادگیری 11
2-4-3. مروری بر مطالعات اثر همزمان یادگیری و زوال در زمانبندی 11
2-4-4. مروری بر مطالعات زمانبندی با اثر استهلاک 12
2-5. جمعبندی 13
فصل سوم: ارائه مدل ریاضی
3-1. مقدمه 14
3-2. تعریف مسئله 14
3-3. فرضیات مسئله 14
3-4. مدل ریاضی پیشنهادی 15
3-4-1. اندیسها 15
3-4-2. پارامترهای مسئله 15
3-4-3. متغیرهای تصمیم 15
3-4-4. مدل ریاضی 16
3-4-5. توضیحات مدل 17
3-5. تحلیل حساسیت 17
3-6. پیچیدگی مسئله 22
3-7. مقدمهای بر الگوریتم ژنتیک 24
3-7-1. شمای کلی الگوریتم ژنتیک 25
3-7-2. واژگان الگوریتم ژنتیک 26
3-7-3. جامعه اولیه 26
3-7-4. عملیات ژنتیک 27
3-7-4-1.عملگر انتخاب 27
3-7-4-2.عملگر تقاطع 28
3-7-4-3. عملگر جهش 29
3-7-4-4.تابع برازش 30
3-7-4-5. شرط توقف 30
3-8 .معرفی الگوریتم رقابت استعماری
3-8-1. مقدمه 30
3-8-2. شکلدهی امپراطوری اولیه 30
3-8-3. سیاست جذب، حرکت کشور مستعمره به سمت استعمارگر 33
3-8-4. انقلاب 35
3-8-5. جابهجایی قدرت بین استعمارگر و مستعمره 35
3-8-6. رقابت استعماری 36
3-8-7. همگرایی 37
فصل چهارم: یافتههای تحقیق
4-1. مقدمه 41
4-2. ساختار الگوریتم ژنتیک پیشنهادی 41
4-2-1. ساختار کروموزوم 41
4-2-2. جمعیت اولیه 42
4-2-3. تابع برازش 42
4-2-4. عملگر تقاطع 43
4-2-5. عملگر
جهش 44
4-2-6. ارزیابی فرزندان 45
4-2-7. جست و جوی محلی 45
4-2-8. معیار توقف 45
4-3. ساختار الگوریتم رقابت استعماری پیشنهادی 46
4-4. نتایج محاسباتی 47
4-4-1. تنظیم پارامترها 47
4-4-2. روش تاگوچی 47
4-4-3. روش تاگوچی برای تنظیم الگوریتم ژنتیک 49
4-4-4. روش تاگوچی برای تنظیم الگوریتم رقابت استعماری 50
4-5. معیارهای عملکرد
4-5-1. شاخص زمان محاسباتی 52
4-5-2. روشهای اندازهگیری عملکرد الگوریتمها 52
4-5-3. تحلیل نمودار زمان محاسباتی الگوریتم ژنتیک و رقابت استعماری 55
4-6. جمعبندی 56
فصل پنجم: نتیجهگیری و پیشنهادات آتی
5-1. جمعبندی 59
5-2. پیشنهادات آتی 59
ضمیمه یک 60
ضمیمه دو 65
منابع و مراجع 71
لیست جدولها
جدول 3-1. دادههای مسئله اول برای کار و زمان 18
جدول 3-2. دادههای مسئله اول برای نرخ یادگیری 18
جدول 3-3. دادههای مسئله اول برای نرخ استهلاک 18
جدول 3-4. دادههای مربوط به زمان نگهداری برای مسئله اول 18
جدول 3-5. دادههای مسئله دوم برای کار و زمان 19
جدول 3-6. دادههای مسئله دوم برای نرخ یادگیری 19
جدول 3-7. دادههای مسئله دوم برای نرخ استهلاک 20
جدول 3-8. دادههای مربوط به زمان نگهداری برای مسئله دوم 20
جدول 3-9. دادههای مسئله سوم برای کار و زمان 21
جدول 3-10. دادههای مسئله سوم برای نرخ یادگیری 21
جدول 3-11. دادههای مربوط به زمان نگهداری برای مسئله سوم 21
جدول 3-12. دادههای مسئله سوم برای نرخ استهلاک 22
جدول 4-1. پارامترهای الگوریتم ژنتیک در سه سطح 49
جدول 4-2. مقادیر بهینه برای پارامترهای GA 50
جدول 4-3. پارامترهای الگوریتم ICA در سه سطح 50
جدول 4-4. مقادیر بهینه برای پارامترهای ICA 51
جدول 4-5. نتایج بدستآمده از روش دقیق، الگوریتم ژنتیک و رقابت استعماری 53
لیست شکلها
شکل 2-1. رویکردهای مدلسازی اثر یادگیری 9
شکل 3-1. سلسله مراتب پیچیدگی توابع هدف در مسائل زمانبندی 24
شکل 3-2. تقاطع تکنقطهای 29
شکل 3-3. تقاطع دو نقطهای 29
شکل 3-4. نحوه تخصیص کشورهای مستعمره به کشور استعمارگر 32
شکل 3-5. حرکت خطی مستعمره در راستای استعمارگر 34
شکل 3-6. زاویه انحراف رسیدن کشور مستعمره به امپریالیسم 34
شکل 3-7. مسیر انقلاب در یک کشور مستعمره 35
شکل 3-8 .جابهجایی قدرت مابین کشورهای استعمارگر و مستعمره 36
شکل 3-9. سقوط امپراطوریهای ضعیفتر 37
شکل 4-1. ساختار دو بخش و نحوه کدگشایی کروموزوم 42
شکل 4-2. نحوه عملکرد عملگرهای تقاطع 44
شکل 4-3. نمایش و نحوه عملگر جهش 45
شکل 4-4. مقادیر سطوح مختلف پارامترهای الگوریتم GA در نسبت S/N 49
شکل 4-5. مقادیر سطوح مختلف پارامترهای الگوریتم ICA در نسبت S/N 51
شکل 4-6. نمودار RPD مربوط به الگوریتم ژنتیک و رقابت استعماری 55
شکل 4-7. نمودار زمان محاسباتی الگوریتم ژنتیک و رقابت استعماری 56
چکیده:
نگهداری ماشین در تولید اغلب برای ممانعت از شکست ماشین به منظور حفظ راندمان تولید انجام میشود. در این پایاننامه مسئله کمینه سازی بیشترین زمان تکمیل بر روی ماشینهای موازی غیرمرتبط باتوجه به تاثیرات استهلاک بر زمان کارها و فعالیتهای نگهداری و اثر یادگیری در افق زمانبندی مورد بررسی قرار گرفت. یک ماشین بعد از عملیات نگهداری به شرایط اولیه خود بازمیگردد و اثر استهلاک از نو، آغاز میگردد. هدف در این مسئله پیدا کردن دفعات بهینه، بهترین زمان انجام عملیات نگهداری و توالی بهینه کارها روی ماشینها به طوری که بیشترین زمان تکمیل کارها کمینه گردد. برای مسئله مطرح شده یک مدل ریاضی خطی ارائه شد و بعد از اشاره به NP-hard بودن مسئله به ارائه روش فرا ابتکاری ژنتیک و رقابت استعماری جهت حل مسئله در ابعاد موجود در واقعیت پرداخته شد و در نهایت نتایج بدست آمده مورد بررسی و تحلیل قرار گرفت.
مقدمه:
زمانبندی[1] فرآیند تخصیص منابع به فعالیتها با درنظرگرفتن دورههای زمانی مربوط به آنها به منظور بهینهسازی یک یا چند هدف میباشد. این فرآیند به عنوان یک فرآیند تصمیمگیری مبنای کار بسیاری از صنایع تولیدی و خدماتی محسوب میشود. زمانبندی کارای فعالیتها زمینه ساز بهبود عملکرد سیستمهای تولیدی میباشد و ضرورتی برای بقا در فضای رقابتی بازار به شمار میآید. تئوری زمانبندی در ارتباط با مدلهای ریاضی است که فرآیند زمانبندی را تشریح میکنند. چشم انداز تئوریک یک نگرش کمی برای بدستآوردن ساختار مسائل در چهارچوب مدلهای ریاضی بدست میدهد که این امر با تشریح منابع و فعالیتها و تبدیل اهداف تصمیمگیری به یک تابع هدف، صورت میپذیرد. درنتیجه، منابع، فعالیتها و توابع هدف عناصر کلیدی مدلهای زمانبندی محسوب میشوند. منابع برحسب قابلیتهای کمی و کیفی خود مشخص میشوند. به طوری که هر مدل نشاندهنده نوع و میزان منابع به کاررفته در آن میباشد. از سوی دیگر، فعالیتها برحسب اطلاعاتی از قبیل منابع موردنیاز، مدت زمان انجام، زمان آغاز و زمان پایان آنها توصیف میشوند. توابع هدف نیز دربرگیرنده هزینههای سیستم برای اجرای تصمیمات مربوط به تخصیص منابع به فعالیتها میباشند. تصمیمات عمده در فرآیند زمانبندی شامل بهره برداری کار از منابع، پاسخگویی سریع به تقاضا و انطباق دقیق زمان های تحویل با موعدهای تحویلی تعیین شده می شوند.
انگیزه بسیاری از توسعهها و پیشرفتهای علمی در حوزه زمانبندی برخاسته از محیطهای صنعتی است و به طورطبیعی در بیان مفاهیم زمانبندی از واژههای به کار رفته درصنعت استفاده میشود. به