تحقیق رایگان درمورد الگوریتم ژنتیک، سلسله مراتب، مدل ریاضی

دانلود پایان نامه ارشد

16
2-4-4. مجموع وزنی زمان تکمیل کارها WjCj 16
2-4-5. مجموع زمان دیر کرد کارها Tj 16
2-4-6. مجموع وزنی زمان دیرکرد کارها WjTj 16
2-4-7. مجموع تعداد کارهای با تاخیر Uj 17
2-4-8. مجموع وزنی تعداد کارهای با تاخیر WjUj 17
2-4-9. مجموع زمانهای زودکرد و دیرکرد کارها Ej+Tj 17
2-4-10. مجموع وزنی زمانهای زودکرد و دیرکرد کارها WjEj+W’jTj 17
2-5. پیشینه تحقیق 17
2-6. ماشینهای موازی نامرتبط 18
2-7. دوبارهکاری 21
2-8. زمان نصب وابسته به توالی کارها 24
2-9. دسترسی محدود به ماشینها 27
2-10. جمع بندی 29
فصل سوم 30
مدل ریاضی پیشنهادی 30
3-1. مقدمه 31
3-2. تعریف مسئله 31
3-2. مفروضات مسئله 32
3-3. مدل ریاضی پیشنهادی 33
3-3-1. اندیسها و پارامترهای ورودی به مدل 34
3-3-2. متغیرهای تصمیمگیری 34
3-3-3. تابع هدف 35
3-3-4. محدودیتها 36
3-4. اعتبار سنجی مدل 40
3-5. پیچیدگی مسئله 43
3-6. الگوریتم ژنتیک 46
3-6-1. تاریخچه الگوریتم ژنتیک 47
3-6-2. واژگان ژنتیک 48
3-6-3. ساختار الگوریتم ژنتیک 49
3-6-4. کدگذاری 50
3-6-5. ایجاد جمعیت اولیه 51
3-6-6. اعمال ژنتیک 52
3-6-6-1. عملگرهای تقاطعی 52
3-6-6-1-1. يك نقطه برش 53
3-6-6-1-2. دو نقطه برش 54
3-6-6-2. عملگرهای جهشی 54
3-6-6-2-1. جابجايي 55
3-6-6-2-2. وارونگي 56
3-6-6-2-3. الحاق یا جاسازی 56
3-6-7. عمل تحول 57
3-6-7-1. فضای نمونه گیری 57
3-6-7-2. فضای نمونه گیری عادی 57
3-6-7-3. مکانیسم نمونه گیری 57
3-6-7-4. احتمال انتخاب 58
3-6-8. تابع برازش 59
3-6-9 . استراتژی برخورد با محدودیت 59
3-6-9-1. استراتژی اصلاح عملگرهای ژنتیک 60
3-6-9-2. استراتژی ردی 60
3-6-9-3. استراتژی اصلاحی 60
3-6-9-4. استراتژی جریمه ای 60
3-6-10. معیار توقف 61
3-7. الگوریتم زنبور عسل 62
3-7-1. مراحل اجرای الگوریتم 63
3-7-2. پارامتر های الگوریتم 64
3-7-3. فلوچارت الگوریتم زنبور عسل 64
3-7-4. شرح مراحل اجرای الگوریتم 65
3-8. جمعبندی 66
فصل چهارم 67
نتایج محاسباتی و تحلیل آن 67
4-1.مقدمه 68
4-2. پیادهسازی الگوریتم ژنتیک 68
4-2-1. ساختار کروموزوم 69
4-2-2. جمعیت اولیه 70
4-2-3. ارزیابی برازندگی تابع هدف 71
4-2-4. استراتژی انتخاب 71
4-2-5. اپراتورهای ژنتیک 73
4-2-6. همگرایی الگوریتم ژنتیک 75
4 -2-7. معیار توقف 75
4-3. پیادهسازی الگوریتم زنبور عسل( شماره یک) 76
4-3-1. مراحل اجرای الگوریتم زنبورعسل (شماره یک) 76
4-3-2. پارامترهای الگوریتم زنبورعسل (شماره یک) 77
4-3-3. روابط حاکم بر مقادیر پارامترها در الگوریتم زنبورعسل (شماره یک) 77
4-4. پیادهسازی الگوریتم زنبور عسل(شماره دو) 78
4-4-1. مراحل اجرای الگوریتم زنبورعسل (شماره دو) 78
4-4-2. پارامترهای الگوریتم زنبورعسل (شماره دو) 79
4-5. مجموعه دادهها 81
4-6. تنظیم پارامترهای کنترلی الگوریتمها 81
4-7. طراحی آزمایشات چندعاملی برای مسائل با ابعاد متوسط 84
4-7-1.تحلیل نتایج آماری 88
4-8. طراحی آزمایشات چندعاملی برای مسائل باابعاد بزرگ 92
4-8-1.تحلیل نتایج آماری 96
4-9. نتایج محاسباتی 99
4-10. جمعبندی 108
فصل پنجم 109
نتیجه گیری و پیشنهادات 109
5-1. مقدمه 110
5-2. نتیجه گیری 110
5-3. پیشنهادات آتی 111
5-3-1. پیشنهادات در زمینه ماهیت مسئله طرح شده در تحقیق 111
5-3-2. پیشنهادات در زمینه روش حل مسئله 112
فهرست منابع 113
پیوست 119

جدول 4-1. مقادیر دادههای ورودی به مسائل آزمایشی 81
جدول 4-2. پارامترهای کنترلی الگوریتم ژنتیک 83
جدول 4-3. پارامترهای کنترلی الگوریتم زنبور شماره یک 83
جدول 4-4. پارامترهای کنترلی الگوریتم زنبور شماره دو 83
جدول 4-5. فاکتورها و سطوح آنها در الگوریتم زنبور شماره یک در ابعاد متوسط 84
جدول 4-6. فاکتورها و سطوح آنها در الگوریتم زنبور شماره دو در ابعاد متوسط 84
جدول 4-7. فاکتورها و سطوح آنها در الگوریتم ژنتیک در ابعاد متوسط 84
جدول 4-8 . ترکیب فاکتورها و سطوح پاسخ مربوط به الگوریتم زنبور1 در مسائل با ابعاد متوسط 85
جدول4-9 . ضرایب همبستگی تخمینی مدل برای نسبتهای SN، الگوریتم زنبور1، ابعاد متوسط 86
جدول4-10. آنالیز واریانس برای نسبتهای SN، الگوریتم زنبور1، ابعاد متوسط 86
جدول 4-11. ضرایب همبستگی تخمینی مدل برای میانگین پاسخها، الگوریتم زنبور1، ابعاد متوسط 87
جدول 4-12. آنالیز واریانس برای میانگین پاسخها، الگوریتم زنبور1، ابعاد متوسط 87
جدول 4-13. جدول پاسخ نسبتهای SN، الگوریتم زنبور1، ابعاد متوسط 88
جدول4-14. جدول پاسخ میانگینها، الگوریتم زنبور1، ابعاد متوسط 88
جدول 4-15. مقادیر پارامترهای کنترلی الگوریتم زنبور 1، ابعاد متوسط 90
جدول 4-16.مقادیر پارامترهای کنترلی الگوریتم زنبور 2، ابعاد متوسط 91
جدول 4-17. مقادیر پارامترهای کنترلی الگوریتم ژنتیک، ابعاد متوسط 91
جدول 4-18. فاکتورها و سطوح آنها در الگوریتم زنبور شماره یک برای ابعاد بزرگ 92
جدول 4-19. فاکتورها و سطوح آنها در الگوریتم زنبور شماره دو برای ابعاد بزرگ 92
جدول 4-20. فاکتورها و سطوح آنها در الگوریتم ژنتیک برای ابعاد بزرگ 92
جدول 4-21. ترکیب فاکتورها و سطوح پاسخ مربوط به الگوریتم زنبور1 در مسائل با ابعاد بزرگ 93
جدول 4-22 . ضرایب همبستگی تخمینی مدل برای نسبتهای SN، الگوریتم زنبور1، ابعاد بزرگ 94
جدول 4-23 . آنالیز واریانس برای نسبتهای SN، الگوریتم زنبور1، ابعاد بزرگ 94
جدول 4-24. ضرایب همبستگی تخمینی مدل برای میانگین پاسخها، الگوریتم زنبور1، ابعاد بزرگ 95
جدول 4-25. آنالیز واریانس برای میانگین پاسخها، الگوریتم زنبور1، ابعاد بزرگ 95
جدول 4-26. جدول پاسخ نسبتهای SN، الگوریتم زنبور1، ابعاد بزرگ 96
جدول4-27. جدول پاسخ میانگینها، الگوریتم زنبور1، ابعاد بزرگ 96
جدول4-28. مقادیر پارامترهای کنترلی الگوریتم زنبور1، ابعاد بزرگ 98
جدول4-29. مقادیر پارامترهای کنترلی الگوریتم زنبور2، ابعاد بزرگ 98
جدول4-30. مقادیر پارامترهای کنترلی الگوریتم ژنتیک، ابعاد بزرگ 98
جدول4-31. نتایج محاسباتی حاصل از حل مسائل با ابعاد کوچک 100
جدول4-32. زمانهای محاسباتی و میانگین جوابهای حاصل از حل مسائل با ابعاد کوچک 101
جدول4-33. نتایج محاسباتی حاصل از حل مسائل با ابعاد متوسط 103
جدول4-34. زمانهای محاسباتی و میانگین جوابهای حاصل از حل مسائل با ابعاد متوسط 103
جدول4-35. نتایج محاسباتی حاصل از حل مسائل با ابعاد بزرگ 105
جدول4-36. زمانهای محاسباتی و میانگین جوابهای حاصل از حل مسائل با ابعاد بزرگ 105
جدول4-37. مقادیر RPD برای الگوریتمهای ژنتیک، رنبور1 و زنبور2 107

شکل3-1. حل گرافیکی مسئله (m=2,n=3,L=3) در شرایط فعال نبودن محدودیت دسترسی به ماشینها 40
شکل3-2. حل گرافیکی مسئله (m=2,n=3,L=3) در شرایط اعمال محدودیت دسترسی به ماشینها 41
شکل3-3. حل گرافیکی مسئله (m=2,n=3,L=3) در شرایط افزایش در زمان نصب کار شماره 3 42
شکل3-4. سلسله مراتب پیچیدگی محیطهای کارگاهی در مسائل زمانبندی ]4[ 44
شکل 3-5. سلسله مراتب پیچیدگی جزئیات نحوه پردازش و محدودیتها در مسائل زمانبندی ]4[ 44
شکل 3-6. سلسله مراتب پیچیدگی توابع هدف در مسائل زمانبندی ]4[ 44
شکل 3-7. سلسله مراتب پیچیدگی تعدادی از مسائل زمانبندی با تابع هدف Makespan ]4[ 45
شکل 3-8 .مقایسه فضاهای ژنوتیپ و فنوتیپ 48
شکل 3-9. فضای موجه، ناموجه و غیرقانونی 51
شکل3-10 . نحوه عملکرد اپراتور تقاطع یک نقطه برش 53
شکل3-11. اپراتور تقاطع تک نقطهای 54
شکل 4-1. رویه کلی الگوریتم ژنتیک 68
شکل4-2. روش نمایش جواب 70
شکل 4-3. عملیات تقاطع 74
شکل 4-4. پاسخ میانگینها، الگوریتم زنبور1، ابعاد متوسط 89
شکل 4-5. میانگین نسبت SN، الگوریتم زنبور1، ابعاد متوسط 90
شکل 4-6 . پاسخ میانگینها، الگوریتم زنبور1 ، ابعاد بزرگ 97
شکل 4-7 . میانگین نسبت SN، الگوریتم زنبور 1، ابعاد بزرگ 97
شکل 4-8. میانگین زمان محاسباتی الگوریتمها در ابعاد کوچک (2ماشین) 102
شکل 4-9. میانگین زمان محاسباتی الگوریتمها در ابعاد متوسط 104
شکل 4-10. میانگین زمان محاسباتی الگوریتمها در ابعاد بزرگ 106
شکل 4-11. نمودار LSD در سطح اطمینان 95% برای معیار RPD 107

فصل اول

کلیات تحقیق

1-1. مقدمه
مسائل زمانبندی1 یکی از مهمترین مسائل دنیای امروز میباشند که تاثیر شگرفی در افزایش بهرهوری سیستمهای تولیدی و خدماتی دارند. زمانبندی در عمل بهمعنای تخصیص منابع محدود به فعالیتهایی است که به آن منبع نیاز دارند و در واقع نوعی فعالیت تصمیمگیری است که با هدف بهینهسازی یک و یا چند معیار انجام میگیرد. باید به این نکته توجه داشت که در دنیای رقابتی کنونی، برای موسسهها، داشتن بهترین توالی انجام عملیات و زمانبندی مناسب فعالیتها یک نیاز اساسی به منظور بقاء تعریف میشود و بهعنوان یک فرآیند تصمیمگیری، مبنای کار بسیاری از صنایع تولیدی و خدماتی محسوب میشود. به بیان بهتر، زمانبندی را میتوان تخصیص منابع محدود در طول زمان بهمنظور اجرای مجموعهای از وظایف تعریف کرد. در دنیای امروز، زمان همواره یک محدودیت اساسی بوده است. بنابراین، زمانبندی صحیح فعالیتها بهمنظور حداقل کردن این منبع با توجه به هزینههای تولیدی و خدماتی در واحد زمان، امری ضروری به نظر میرسد.
با پیشرفت علم و بهدنبال آن توسعه و شکوفایی صنایع تولیدی و خدماتی، نقش منابع و نحوه تخصیص آنها از اهمیت دو چندانی برخوردار شده است. امروزه منابع در دسترس مانند نیروی انسانی، ماشینآلات، مواد اولیه و … به عنوان منابع بحرانی در تولید و فعالیتهای خدماتی در نظر گرفته میشوند و زمانبندی و تخصیص به موقع و مناسب این منابع منجر به ارتقاء کارایی، بهرهوری و در نهایت سودآوری بیشتر میشود. از آنجا که خواستگاه بسیاری از مسائل زمانبندی و توالی عملیات محیط های صنعتی میباشد، در بیان بسیاری از مفاهیم زمانبندی از واژههای بکار رفته در صنعت استفاده میشود. به عنوان مثال، در مباحث زمانبندی و توالی عملیات از منابع با عنوان ماشین2 و از فعالیتها با عنوان کار3 یاد میشود به نحوی که کارها اغلب بوسیله ماشینها در ایستگاههای مختلف کاری با توالی مشخص پردازش میشوند.
در مسائل زمانبندی، هدف از یافتن توالی انجام کارها میتواند متفاوت باشد. تعدادی از اهداف مورد استفاده در مسائل زمانبندی عبارتند از : کمینهسازی بیشترین زمان تکمیل کارها، کمینهسازی مجموع زمان تکمیل کارها، کمینهسازی بیشترین زمان دیرکرد و کمینهسازی تعداد کارهایی که دیرکرد دارند. همچنین بر حسب شرایط حاکم بر محیط مورد مطالعه، محدودیتهای گوناگونی در مسئله لحاظ میشود. تعدادی از محدودیتهای حاکم بر مسائل زمانبندی عبارتند از : زمانهای نصب وابسته به توالی ، محدودیت دسترسی به ماشینها، زمانهای دسترسی به کار، برش در کارها، خرابی ماشینها و محدودیت در اندازه صف کارها که مورد آخر در سیستمهای جریان کارگاهی می تواند لحاظ شود . در ابتدای فصل دوم، مسائل زمانبندی به تفکیک محیطهای کارگاهی، محدودیتهای پردازش و توابع هدف بصورت مختصر معرفی میشوند. یک مسئله زمانبندی بصورت یک مسئله بهینهسازی بیان میشود که با توجه به محدودیتهای موجود، به دنبال ارضاء کردن هدف (اهداف) مورد نظر میباشد.
در مباحث زمانبندی، بررسی مدلهای تک ماشینه به علت سادگی و به دلیل اینکه حالت خاصی از سایر مدلها میباشد از اهمیت بالایی برخوردار است. در مقابل، نظریه زمانبندی سه نوع اساسی از مدلهای چند ماشینی را پوشش میدهد: سیستمهای موازی، سیستمهای جریان کارگاهی و سیستمهای تولید کارگاهی. در سیستم ماشینهای موازی همانند مدلهای تک ماشینی، هر یک از کارها با انجام یک عملیات بر روی یکی از ماشینهای موازی موجود پردازش میشوند اما در سیستمهای جریان کارگاهی و ترکیبی ساختار مسائل پیچیدهتر است.
در ادامه به تعریف مسئله مورد بحث این تحقیق و مفروضات آن پرداخته میشود. در پایان اهداف و ضرورت تحقیق بیان

پایان نامه
Previous Entries پایان نامه ارشد رایگان درمورد نهج البلاغه، آیات و روایات، نماز جماعت Next Entries پایان نامه ارشد رایگان درمورد شرایط صحت، فضایل اخلاقی، عدالت اجتماعی