مقطع کارشناسی ارشد
 

رشته : مهندسی صنایع- مهندسی سیستم­های اقتصادی اجتماعی
 

عنوان: طراحی الگوریتم فراابتکاری برای زمانبندی ماشین­های موازی نامرتبط با تابع هدف چندگانه در محیط تولید بهنگام
 

اساتید راهنما: دکتر جواد رضائیان
 

دکتر ایرج مهدوی
 

(بهار 1393)
 

(در فایل دانلودی نام نویسنده موجود است)
تکه هایی از متن پایان نامه به عنوان نمونه :
(ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است)
چکیده
در طول دهه گذشته، گسترش الگوریتم­های فراابتکاری بهینه سازی چند معیاره توجه بسیاری را به خود جلب کرد. مسائل برنامه ریزی تولید بهنگام به عنوان مهمترین مسئله برنامه ­ریزی بهینه سازی نیز مستثنی نبود. البته بسیاری از الگوریتم­های بهینه سازی که برای مسائل گوناگون به کار برده می­شدند رویکردی نامناسب داشتند. به زبان دیگر بسیاری از آنها هدف­ ها را ترکیب می­کردند و مسائل را با رویکرد تک هدفه حل می­کردند. البته بعضی از محققان الگوریتم­های پارتویی به کار می­برند. در این تحقیق یک برنامه ریزی ماشین­های موازی نامرتبط با زمان آماده سازی وابسته به توالی، زمان دسترسی پویا به کارها، زمان تحویل متفاوت کارها و محدودیت مجموعه پردازشی نشان داده شده است. توابع هدف مورد نظر، مجموع وزنی زمانهای زودکرد و دیرکرد کارها و همچنین مجموع زمان تکمیل کارها را کمینه می­ کنند. برای حل مدل و اعتبار سنجی آن از الگوریتم­ مجموع وزنی و الگوریتم محدودیت اپسیلون استفاده شده است. همچنین نشان داده شده است که الگوریتم­هایی که از روش شاخه و کران برای حل استفاده می­ کنند قادر به حل مسائل بزرگ در زمان معقول نمی­باشند. بنابراین برای حل این مسئله برنامه ریزی چند معیاره که از نوع چند جمله­ای سخت (NP-Hard) می­باشد الگوربتم فراابتکاری (CENSGA)معرفی شده است. الگوریتم ارائه شده را با بهره گرفتن از شاخص­های آماری با الگوریتم فراابتکاری (NSGA-II) مورد مقایسه و تحلیل قرار داده شده است که نتایج نشان دهنده کارایی بهتر الگوریتم فراابتکاری (CENSGA) می­باشد.
کلمات کلیدی: تولید بهنگام; زمان آماده­سازی وابسته به توالی; کنترل نخبه­گرایی; بهینه سازی چند هدفه; الگوریتم مرتب سازی نامغلوب.
 
فهرست

فصل اول مقدمه و کلیات 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. ارزیابی روش های حل مسئله با شاخصهای کمی برای 8j2m88
جدول 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. نمایش الگوریتم NSGAII61
شکل 3-9. محاسبه فاصله تراکمی 64
شکل 3-10. ساختار کروموزوم66
شکل 3-11. نحوه ایجاد جمعیت اولیه 67
شکل 3-12. نحوه عملکرد عملگر تقاطع 69