فرمت فایل : WORD (قابل ویرایش)
تعداد صفحات:114
پایان نامه مقطع کارشناسی ارشد
مهندسی صنایع- مهندسی سیستم های اقتصادی اجتماعی
فهرست مطالب:
فصل اول مقدمه و کلیات 1
1-1. مقدمه 2
1-2. تعریف مسأله زمانبندی 5
1-3. ضرورت انجام تحقیق 7
1-4. اهداف تحقیق 8
1-5. مفروضات مسئله 9
1-6. جنبه های نوآوری تحقیق 10
1-7. محتوای تحقیق 10
فصل دوم ادبیات و پیشینه تحقیق 11
2-1. مقدمه 12
2-2. طبقه بندی محیط های زمانبندی 15
2-3. مسائل ماشینهای موازی 19
2-3-1. زمان نصب و آماده سازی 20
2-3-2. دسترسی محدود به ماشینها 26
2-3-3. زمان دسترسی متفاوت به کارها 27
2-4. مسائل با تمرکز بر موعد تحویل برای کارها 27
2-4-1. زمان تکمیل کارها 29
2-4-2. زمانهای زودکرد و دیرکرد 29
2-5. مروری بر رویکرد و اصول سیستم تولیدی بهنگام 31
2-6. توالی ماشینﻫای موازی با معیارهای زودکرد و دیرکرد 33
2-7. جمع بندی 34
فصل سوم مدل ریاضی و بهینه سازی چند هدفه 36
3-1. مقدمه 37
3-2. تعریف مسئله 37
3-2-1. مفروضات مسئله 39
3-3. مدل پیشنهادی 39
3-3-1.نمادها، تعاریف، پارامترها و متغیر های تصمیم 40
3-3-2. پارامترهای ورودی 40
3-3-3. توابع هدف 41
3-3-4. محدودیتها 41
3-4. اعتبارسنجی مدل 43
3-5. پیچیدگی مسئله 45
3-6 بهینه سازی چند معیاره 47
3-6-1. ارتباط غالب 47
3-6-2. نقاط بهینه موضعی 48
3-6-3. نقاط بهینه سراسری 48
3-6-4. مرز بهینه 48
3-7. روشهای بهینه سازی 49
3-7-1. روشهای اسکالر 49
3-7-2. روش مجموع وزنی 51
3-7-2-1. طراحی روش مجموع وزنی برای حل مسأله مورد نظر 54
3-7-3. روش محدودیت-ε 55
3-7-3-1. طراحی روش محدودیت – ε برای حل مسأله 57
3-7-4. روشهای عکس العملی 57
3-7-5. روش های مبتنی بر منطق فازی 58
3-7-6. روش های فرا ابتکاری 59
3-7-7. الگوریتم NSGA-II 60
3-7-7-1. مرتب سازی سریع 61
3-7-7-2. عملگر گزینش تورنمنت تراکمی 63
3-7-7-3. فاصله تراکمی 63
3-7-8. طراحی روش فراابتکاری NSGA-II برای حل مسأله 65
3-7-9. طراحی روش فراابتکاری CENSGA برای حل مسأله 70
3-8. مقایسه روش های بهینه سازی چند هدفه 71
3-8-1. شاخص متوسط فاصله از نقطه ایدهآل 73
3-8-2. شاخص نرخ دستیابی به توابع هدف 74
3-8-3. شاخص گستردگی جواب های غیر مغلوب (SNS) 74
3-8-4. شاخص یکنواختی فضا 74
3-9. جمعﺑندی 75
فصل چهارم محاسبات و نتایج تحقیق 77
4‐1. مقدمه 78
4‐2. تنطیمات پارامترها و شرایط اجرای الگوریتم ها 79
4-3. الگوریتمهای NSGA-II,CENSGA 80
4-4. روش مجموع وزنی 80
4-5. روش محدودیت-ε 81
4‐6. ساختار مسائل 82
4‐7. معیارهای ارزیابی الگوریتمها 83
4‐8. مسائل با ابعاد کوچک و متوسط 83
4-8-1. نتایج آزمایشات مسائل کوچک و متوسط 83
4‐9. مسائل با ابعاد بزرگ 90
4‐10. نتایج محاسباتی 90
4‐11. جمعﺑندی 96
فصل پنجم نتیجه گیری و پیشنهادات 97
5‐1. مقدمه 98
5‐2. نتیجهﮔیری 99
5‐3. پیشنهادهای آتی 100
فهرست منابع و مراجع 102
فهرست جداول
جدول 2-1. محیط¬های کارگاهی (نماد α) 13
جدول 2-2. توابع هدف رایج در ادبیات 15
جدول 3-1. زمان¬های پردازش،موعدهای تحویل و زمان دسترسی 44
جدول 3-2. زمان نصب ماشین یک و دو برای کارهای مختلف 44
جدول 4-1. حدهای بالا برای مسائل مختلف 82
جدول 4-2. جوابهای نامغلوب مربوط به مسأله 5j2m به تفکیک روش ها 84
جدول 4-3. ارزیابی روشهای حل مسئله با شاخصهای کمی برای 5j2m 85
جدول 4-4. جوابهای نامغلوب مربوط به مسأله 5j3m به تفکیک روش ها 85
جدول 4-5. ارزیابی روشهای حل مسئله با شاخصهای کمی برای 5j3m 86
جدول 4-6. جوابهای نامغلوب مربوط به مسأله 8j2m به تفکیک روش ها 87
جدول 4-7. ارزیابی روشهای حل مسئله با شاخصهای کمی برای 8j2m 88
جدول 4-8 . جوابهای نامغلوب مربوط به مسأله 8j3m به تفکیک روش ها 89
جدول 4-9. ارزیابی روشهای حل مسئله با شاخصهای کمی برای 8j3m 90
جدول 4-10 نتایج شاخص¬های متریک برای الگوریتم CENSGAوNSGA-II 91
جدول 4- 11. ارزیابی آماری الگوریتم¬های فراابتکاری بکار گرفته شده 94
فهرست شکل¬ها و نمودارها
شکل 2-1. دسته بندی مسائل زمانبندی بر اساس مسیر تولید 19
شکل 3-1. سلسله¬مراتب پیچیدگی محیط¬های کارگاهی در مسائل زمان¬بندی 46
شکل 3-2. سلسله¬مراتب پیچیدگی توابع هدف در مسائل زمان¬بندی 46
شکل 3-3. نقاط بهینه موضعی 48
شکل 3-4. رابطه فضای جواب و ارتباط غالب 48
شکل 3-5. نمایش روش مجموع وزنی با مرز بهینه پارتو محدب 52
شکل 3-6. نمایش روش مجموع وزنی با مرز بهینه پارتو غیر محدب 54
شکل 3-7. روش محدودیت- ε 56
شکل 3-8. نمایش الگوریتم NSGAII 61
شکل 3-9. محاسبه فاصله تراکمی 64
شکل 3-10. ساختار کروموزوم 66
شکل 3-11. نحوه ایجاد جمعیت اولیه 67
شکل 3-12. نحوه عملکرد عملگر تقاطع 69
شکل 3-13. عملگر تقاطع تک نقطه ای با نقطه برش 3 69
شکل 3-14. نحوه عملکرد عملگر جهش 70
شکل 3-15. استراتژی انتخاب در الگوریتم CENSGA و NSGA-II 71
شکل 3-16. دو هدف در بهینه سازی چند هدفه 72
شکل 3-17. یک مجموعه ایده آل از جواب های نامغلوب 72
شکل 3-18. همگرائی خوب، اما تنوع ضعیف (الگوریتم 1) 73
شکل 3-19. همگرائی ضعیف، اما تنوع خوب (الگوریتم 2) 73
شکل 4-1. نمایش جوابهای نامغلوب ε-محدودیت مسأله 5j2m 84
شکل 4-2. نمایش جوابهای نامغلوب روش وزنی مسأله 5j2m 84
شکل 4-3. نمایش جوابهای نامغلوب روش وزنی مسأله 5j3m 86
شکل 4-4. نمایش جوابهای نامغلوب روش محدودیت-ε مسأله 5j3m 86
شکل 4-5 . نمایش جوابهای نامغلوب روش وزنی مسأله 8j2m 88
شکل 4-6 . نمایش جوابهای نامغلوب روش محدودیت-ε مسأله 8j2m 88
شکل 4-7 . نمایش جوابهای نامغلوب روش وزنی مسأله 8j3m 89
شکل 4-8 . نمایش جوابهای نامغلوب روش محدودیت-ε مسأله 8j3m 89
شکل 4- 9 نمودار نتایج محاسباتی شاخص های متریک در مسائل مختل 92
شکل 4-10. نمودارجعبه ای (BoxPlot) نتایج ارزیابی الگوریتم¬های CENSGA,NSGA-II 93
شکل 4-11. نمودار میانگین و فواصل اطمینان (سطح اطمینان 95%)نتایج ارزیابی الگوریتم ها 95
چکیده
در طول دهه گذشته، گسترش الگوریتم¬های فراابتکاری بهینه سازی چند معیاره توجه بسیاری را به خود جلب کرد. مسائل برنامه ریزی تولید بهنگام به عنوان مهمترین مسئله برنامه¬ریزی بهینه سازی نیز مستثنی نبود. البته بسیاری از الگوریتم¬های بهینه سازی که برای مسائل گوناگون به کار برده می¬شدند رویکردی نامناسب داشتند. به زبان دیگر بسیاری از آنها هدف¬ ها را ترکیب می¬کردند و مسائل را با رویکرد تک هدفه حل می¬کردند. البته بعضی از محققان الگوریتم¬های پارتویی به کار می¬برند. در این تحقیق یک برنامه ریزی ماشین¬های موازی نامرتبط با زمان آماده سازی وابسته به توالی، زمان دسترسی پویا به کارها، زمان تحویل متفاوت کارها و محدودیت مجموعه پردازشی نشان داده شده است. توابع هدف مورد نظر، مجموع وزنی زمانهای زودکرد و دیرکرد کارها و همچنین مجموع زمان تکمیل کارها را کمینه می-کنند. برای حل مدل و اعتبار سنجی آن از الگوریتم¬ مجموع وزنی و الگوریتم محدودیت اپسیلون استفاده شده است. همچنین نشان داده شده است که الگوریتم¬هایی که از روش شاخه و کران برای حل استفاده می¬کنند قادر به حل مسائل بزرگ در زمان معقول نمی-باشند. بنابراین برای حل این مسئله برنامه ریزی چند معیاره که از نوع چند جمله¬ای سخت (NP-Hard) می¬باشد الگوربتم فراابتکاری (CENSGA)معرفی شده است. الگوریتم ارائه شده را با استفاده از شاخص¬های آماری با الگوریتم فراابتکاری (NSGA-II) مورد مقایسه و تحلیل قرار داده شده است که نتایج نشان دهنده کارایی بهتر الگوریتم فراابتکاری (CENSGA) می¬باشد.
کلمات کلیدی: تولید بهنگام; زمان آماده¬سازی وابسته به توالی; کنترل نخبه¬گرایی; بهینه سازی چند هدفه; الگوریتم مرتب سازی نامغلوب.
