بسیاری از آنها هدف ها را ترکیب میکردند و مسائل را با رویکرد تک هدفه حل میکردند. البته بعضی از محققان الگوریتمهای پارتویی به کار میبرند. در این تحقیق یک برنامه ریزی ماشینهای موازی نامرتبط با زمان آماده سازی وابسته به توالی، زمان دسترسی پویا به کارها، زمان تحویل متفاوت کارها و محدودیت مجموعه پردازشی نشان داده شده است. توابع هدف مورد نظر، مجموع وزنی زمانهای زودکرد و دیرکرد کارها و همچنین مجموع زمان تکمیل کارها را کمینه میکنند. برای حل مدل و اعتبار سنجی آن از الگوریتم مجموع وزنی و الگوریتم محدودیت اپسیلون استفاده شده است. همچنین نشان داده شده است که الگوریتمهایی که از روش شاخه و کران برای حل استفاده میکنند قادر به حل مسائل بزرگ در زمان معقول نمیباشند. بنابراین برای حل این مسئله برنامه ریزی چند معیاره که از نوع چند جملهای سخت (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
شکل 3-13. عملگر تقاطع تک نقطه ای با نقطه برش 369
شکل 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. نمایش جوابهای نامغلوب روش وزنی مسأله 5j3m86
شکل 4-4. نمایش جوابهای نامغلوب روش محدودیت- مسأله 5j3m86
شکل 4-5 . نمایش جوابهای نامغلوب روش وزنی مسأله 8j2m88
شکل 4-6 . نمایش جوابهای نامغلوب روش محدودیت- مسأله 8j2m 88
شکل 4-7 . نمایش جوابهای نامغلوب روش وزنی مسأله 8j3m 89
شکل 4-8 . نمایش جوابهای نامغلوب روش محدودیت- مسأله 8j3m89
شکل 4- 9 نمودار نتایج محاسباتی شاخص های متریک در مسائل مختل92
شکل 4-10. نمودارجعبه ای (BoxPlot) نتایج ارزیابی الگوریتمهای CENSGA,NSGA-II 93
شکل 4-11. نمودار میانگین و فواصل اطمینان (سطح اطمینان 95%)نتایج ارزیابی الگوریتم ها 95
Article I. فصل اول مقدمه و کلیات
1-1. مقدمه
زمانبندی[1]، فرایند تخصیص منابع به فعالیتها با درنظر گرفتن دورههای زمانی مربوط به آنها به منظور بهینهسازی یک یا چند هدف میباشد. این فرایند به عنوان یک فرایند تصمیمگیری مبنای کار بسیاری از صنایع تولیدی و خدماتی محسوب میشود. زمانبندی کارای فعالیتها زمینهساز بهبود عملکرد سیستمهای تولیدی میباشد و ضرورتی برای بقا در فضای رقابتی بازار به شمار میآید.
تئوری زمانبندی در ارتباط با مدلهای ریاضی است که فرایند زمانبندی را تشریح میکنند. چشمانداز تئوریک یک نگرش کمی برای بدست آوردن ساختار مسائل در چهارچوب مدلهای ریاضی بهدست میدهد که این امر با تشریح منابع و فعالیتها و تبدیل اهداف تصمیمگیری به یک تابع هدف، صورت میپذیرد. عمل زمانبندی در یک سازمان از مدل ها و روش های ریاضی و یا روش های ابتکاری برای تخصیص منابع محدود به کارهای در حال جریان استفاده می کند. اهمیت توالی ماشین های موازی، با هدف متمرکز بر دیرکرد از آن جهت مورد توجه است که در محیط کسب و کار حاضر، رقابت شرکت های تولیدی از طریق قابلیت آنها برای پاسخگویی سریع به تغییرات سریع در زمینه تجارتی و تولید محصولات با کیفیت بالاتر و هزینه های کمتر تعیین می شود. در نتیجه، منابع، فعالیتها و توابع هدف عناصر کلیدی مدلهای زمانبندی محسوب میشوند.
منابع بر حسب قابلیتهای کمی و کیفی خود مشخص میشوند، بطوریکه هر مدل نشان دهنده نوع و میزان منابع بکار رفته در آن میباشد. از سوی دیگر، فعالیتها بر حسب اطلاعاتی از قبیل منابع مورد نیاز، مدت زمان انجام، زمان آغاز و زمان پایان آنها توصیف میشوند. توابع هدف نیز دربرگیرنده هزینههای سیستم برای اجرای تصمیمات مربوط به تخصیص منابع به فعالیتها میباشند. تصمیمات عمده در فرایند زمانبندی شامل بهرهبرداری کارا از منابع، پاسخگویی سریع به تقاضا و انطباق دقیق زمانهای تحویل با موعدهای تحویل تعیینشده میشوند. شرکت های تولیدی در تلاش هستند تا این قابلیت ها را از طریق اتوماسیون و مفاهیم خلاق مانند تولید به موقع[2] (JIT) ، پاسخگوی سریع[3] (QR) ، تکنولوژی گروهی[4] (GT) و مدیریت کیفیت جامع[5] (TQM) بدست آورند[58].
این مفاهیم ( برای مثال JIT و GT ) به بسیاری از شرکت ها در بدست آوردن سود اقتصادی کمک کرده است. در سیسستم های JIT کار نباید نه زودتر و نه دیرتر تکمیل شود، که