52
3-7- نتايج فاز دوم 54
3-7-1- آزمايشات عددي 54
3-7-2- پارامترهاي مدل شبيه سازي 54
3-7-3- فرايند شبيه سازي 56
3-7-4- نتايج شبيه سازي 56
3-8- نتايج فاز سوم 64
3-8-1- آزمايشات عددي 64
3-8-2- پارامترهاي مدل شبيه سازي 64
3-8-3- فرايند شبيه سازي 65
3-8-4- نتايج شبيه سازي 65
3-9-جمع بندي 74
فصل 4: حل تک هدفه مسئلهي مورد مطالعه با استفاده از الگوريتم هاي فرا ابتکاري 75
4-1- مقدمه 76
4-2- الگوريتم ژنتيک 76
4-2-1- ساختار کروموزوم 78
4-2-2- تابع برازندگي 79
4-2-3- عملگرهاي الگوريتم ژنتيک 80
4-2-4- شرط خاتمهي الگوريتم 84
4-2-5- نقاط قوت الگوريتم هاي ژنتيک 84
4-2-6- رويه ي الگوريتم ژنتيک 85
4-3- شبيه سازي تبريد 86
4-3-2- برنامه سردسازي 87
4-3-3- ساختار همسايگي جديد 88
4-3-4- رويه ي الگوريتم شبيه سازي تبريد 88
4-4- تنظيم پارامترهاي استفاده شده براي الگوريتم ها 90
4-5- نتايج محاسباتي الگوريتم هاي فراابتکاري 91
4-5-1- مقدمه 91
4-5-2- آزمايشات عددي 91
4-5-3- پارامترهاي مدل شبيه سازي 91
4-5-4- فرايند شبيه سازي 92
4-5-5- نتايج شبيه سازي 93
4-5-6- نتيجه گيري: 94
4-6- جمع بندي 95
فصل 5: حل مسئله پيش بيني ماکزيمم زمان اتمام کارها 96
5-1- مقدمه 97
5-2- مدل فازي سوگينو 97
5-2-2- شبکه عصبي فازي ANFIS 99
5-2-3- الگوريتم آموزش هيبريدي (مختلط) 102
5-3- پيش بيني ماکزيمم زمان اتمام کارها توسط شبکه عصبي فازي تطبيق پذير 102
5-4- مدل رگرسيون خطي 105
5-5- نتايج محاسباتي 105
5-5-1- نتايج کلي 105
5-5-2- نتايج آزمون هاي آماري مربوط به معيار MSE 108
5-5-3- نتايج آزمون هاي آماري مربوط به معيار RMSE 109
5-5-4- نتايج آزمون هاي آماري مربوط به معيار R-Square 111
5-6- جمع بندي 113
فصل 6: حل مساله مورد مطالعه با رويکرد چند هدفه 114
6-1- مقدمه 115
6-2- مفاهيم پايه اي مسائل بهينه سازي چند هدفه 116
6-2-1- کليات بهينه سازي چند هدفه 116
6-2-2- چيرگي پارتو و مجموعه حل هاي غير غالب 119
6-2-3- مرز بهينه پارتو و مجموعه حل هاي بهينه پارتو 119
6-3- مروري بر روش هاي حل مسائل بهينه سازي چند هدفه 120
6-3-1- طبقه بندي بر اساس تعداد حل هاي بهينه به دست آمده 120
6-3-2- طبقه بندي بر اساس روش حل 121
6-4- روش هاي پيشنهادي براي حل چند هدفه مسئله مورد مطالعه 122
6-4-1- روش وزني کلاسيک 123
6-4-2- روش مجموع وزني نرمالايز شده توابع هدف 124
6-4-3- روش فازي 126
6-5- معيارهاي مقايسه رويکردهاي چندهدفه 130
6-5-1- تعداد جواب هاي پارتو 130
6-5-2- پراکندگي جواب هاي پارتو 130
6-5-3- درصد چيرگي در پارتو ترکيبي 131
6-5-4- مجموع انحراف بهترين جواب هاي هر تابع هدف از بهترين جواب هاي پارتو 131
6-6- جمع بندي 136
فصل 7: جمع‌بندي و پيشنهاد براي تحقيقات آتي 137
7-1- مقدمه 138
7-2- جمع‌بندي و خلاصه ي نتايج 138
7-3- نوآوري و مشارکت علمي 138
7-4- پيشنهادها براي تحقيقات آينده 139
مراجع 140

فهرست اشکال
شکل (1-1) دسته بندي مسائل زمانبندي 3
شکل (1-2) نماي شماتيک مسئله 6
شکل (1-3) متدولوژي تحقيق به صورت شماتيک 9
شکل (3-1) برنامه توليد شده توسط الگوريتم پيشنهادي MRS1 براي مثال ارائه شده 30
شکل (3-2) برنامه توليد شده توسط الگوريتم پيشنهادي MRS2 براي مثال ارائه شده 34
شکل (4-1) ساختار کلي کروموزوم 79
شکل (4-2) ساختار کلي کروموزوم مورد استفاده 79
شکل (4-3) ساختار کروموزوم تبديل يافته 79
شکل (4-4) ساختار چرخ رولت 81
شکل (4-5) نمونه عمليات تقاطع 82
شکل (4-6) نمونه عمليات جهش 83
شکل(4-7) فرايند اجراي الگوريتم ژنتيک براي مسئله ي NWTSFFS 84
شکل (4-8) نمودار الگوريتم ژنتيک هيبريدي براي مسئله ي NWTSFFS 85
شکل (4-9) نمودار الگوريتم شبيه سازي تبريد هيبريدي براي مسئله ي NWTSFFS 89
شکل (5-1) ساختار کلي شبکه فازي عصبي تطبيق پذير با دو ورودي 98
شکل (5-2) مدل استنتاج فازي سوگينو 99
شکل (5-3) تابع عضويت گوسين 100
شکل (6-1) نمونه اي از جواب هاي پارتو 117
شکل (6-2) نمايش عدد فازي مثلثي 127

فهرست جداول
جدول (3-1) علائم و نمادهاي به کار رفته در الگوريتم هاي ابتکاري و فراابتکاري 26
جدول (3-2) توابع هدف استفاده شده در الگوريتم هاي ابتکاري و فراابتکاري 27
جدول (3-3) زمان هاي پردازش مرحله اول و دوم براي مثال ارائه شده 29
جدول (3-4) تکرار اول الگوريتم 29
جدول (3-5) تکرار دوم الگوريتم 29
جدول (3-6) توالي به دست امده براي کارها توسط الگوريتم MRS1 30
جدول (3-7) زمان هاي پردازش و موعد تحويل براي مثال ارائه شده 32
جدول (3-8) تکرار اول الگوريتم MRS2 32
جدول (3-9) تکرار دوم الگوريتم MRS2 33
جدول (3-10) توالي به دست آمده براي کارها توسط الگوريتم MRS2 34
جدول (3-11) زمان هاي پردازش و موعد تحويل براي مثال ارائه شده 35
جدول (3-12) تکرار اول الگوريتم MRS3 36
جدول (3-13) تکرار دوم الگوريتم MRS3 37
جدول (3-14) توالي به دست امده براي کارها توسط الگوريتم MRS3 37
جدول (3-15) زمان هاي پردازش و موعد تحويل براي مثال ارائه شده 39
جدول (3-16) چگونگي روش حل الگوريتم MRS4 39
جدول(3-17) توالي به دست آمده براي کارها و ماشين ها توسط الگوريتم MRS4 40
جدول (3-18) زمان هاي پردازش و موعد تحويل براي مثال ارائه شده 42
جدول(3-19) تکرار اول الگوريتم MRS5 42
جدول (3-20) تکرار دوم الگوريتم MRS5 43
جدول (3-21) توالي به دست امده براي کارها و ماشين ها توسط الگوريتم MRS5 43
جدول (3-22) زمان هاي پردازش و موعد تحويل براي مثال ارائه شده 44
جدول(3-23) انتخاب کار درتکرار اول الگوريتم MRS6 44
جدول (3-24) انتخا ب ماشين براي کار اول انتخاب شده توسط الگوريتم MRS6 45
جدول (3
-25) جدول اتتخاب کار درتکرار دوم الگوريتم MRS6 45
جدول(3-26) انتخا ب ماشين براي کار دوم انتخاب شده توسط الگوريتم MRS6 45
جدول (3-27) توالي به دست آمده براي کارها و ماشين ها توسط الگوريتم MRS6 46
جدول(3-28) زمان هاي پردازش و موعد تحويل و زمان آماده کار براي مثال ارائه شده 47
جدول(3-29) نحوه محاسبه توالي به دست آمده براي کارها توسط الگوريتم MRS7 48
جدول (3-30) توالي به دست آمده براي کارها و ماشين ها توسط الگوريتم MRS7 48
جدول (3-31) پارامترهاي مدل شبيه سازي براي فاز اول 52
جدول (3-32) نتايج فاز اول براي تابع هدف ماکزيمم کردن درصد بهرهبرداري از ماشين آلات 53
جدول(3-33) پارامترهاي مدل شبيه سازي براي فاز دوم 55
جدول (3-34) نتايج فاز دوم براي تابع هدف مينيمم سازي ماکزيمم زمان کارها 56
جدول (3-35) نتايج فاز دوم براي تابع هدف مينيمم سازي متوسط زمان در گردش 58
جدول (3-36) نتايج فاز دوم براي تابع هدف مينيمم سازي متوسط ديرشدگي 59
جدول (3-37) نتايج مربوط به فاز دوم براي تابع هدف مينيمم سازي متوسط تاخير 60
جدول (3-38) نتايج فاز دوم براي تابع هدف مينيمم سازي ماکزيمم تاخير 61
جدول (3-39) نتايج فاز دوم براي تابع هدف مينيمم سازي تعداد کارهاي تاخيردار 62
جدول (3-40) ميانگين توابع هدف، تعداد موفقيت و زمان اجراي الگوريتم ها در فاز دوم 63
جدول (3-41) پارامترهاي مدل شبيه سازي براي فاز سوم 65
جدول (3-42) نتايج مربوط به فاز سوم براي تابع هدف مينيمم سازي ماکزيمم زمان اتمام کارها 66
جدول (3-43) نتايج مربوط به فاز سوم براي تابع هدف مينيمم سازي متوسط زمان اتمام کارها 67
جدول (3-44) نتايج مربوط به فاز سوم براي تابع هدف مينيمم سازي متوسط زمان در گردش 68
جدول (3-45) نتايج مربوط به فاز سوم براي تابع هدف مينيمم سازي متوسط ديرشدگي 69
جدول (3-46) نتايج مربوط به فاز سوم براي تابع هدف مينيمم سازي ماکزيمم زمان اتمام کارها 70
جدول (3-47) نتايج مربوط به فاز سوم براي تابع هدف مينيمم سازي ماکزيمم تاخير 71
جدول (3-48) نتايج مربوط به فاز سوم براي تابع هدف مينيمم سازي کارهاي تاخيردار 72
جدول (3-49) ميانگين توابع هدف، تعداد موفقيت و زمان اجراي الگوريتم ها در فاز سوم 73
جدول (4-1) محدوده ي پارامترهاي استفاده شده براي الگوريتم هاي HSA و HGA 90
جدول (4-2) پارامترهاي مدل شبيه سازي براي الگوريتم هاي فراابتکاري 92
جدول (4-3) نتايج آماري الگوريتم هاي فراابتکاري 93
جدول (4-4) نتايج به دست آمده براي سايز کوچک 94
جدول (4-5) نتايج به دست آمده براي سايز بزرگ 95
جدول (5-1) پارامترهاي مدل شبيه سازي 104
جدول (5-2) پارامترهاي موثر روي مدل شبکه عصبي فازي تطبيق پذير 105
جدول (5-3) نتايج به دست آمده براي معيار R-Square 106
جدول (5-4) نتايج به دست آمده براي معيار MSE و RMSE 107
جدول (5-5) نتايج آماري معيار MSE در فرايند آموزش 108
جدول (5-6) نتايج آماري معيار MSE در فرايند تست 109
جدول (5-7) نتايج آماري معيار RMSE در فرايند آموزش 110
جدول (5-8) نتايج آماري معيار RMSE در فرايند تست 110
جدول (5-9) نتايج آماري معيار R-Square در فرايند آموزش 111
جدول (5-10) نتايج آماري معيار R-Square در فرايند تست 112
جدول (5-11) متوسط مقادير معيارها براي الگوريتم هاي در نظر گرفته شده 112
جدول (6-1) وزن هاي در نظر گرفته شده براي روش وزني کلاسيک 123
جدول (6-2) وزن هاي در نظر گرفته شده براي روش مجموع وزني نرمالايز شده 124
جدول (6-3) ضرايب در نظر گرفته شده براي مسئله 125
جدول(6-4) مشخصات مسائل حل شده 132
جدول (6-5) تعداد جواب هاي پارتو به دست آمده براي سه رويکرد پيشنهادي 133
جدول (6-6) پراکندگي جواب هاي پارتو به دست آمده براي سه رويکرد پيشنهادي 134
جدول (6-7) درصد چيرگي جواب هاي پارتو به دست آمده براي سه رويکرد پيشنهادي 135
جدول (6-8) مجموع انحراف بهترين جواب هاي هر تابع هدف از بهترين جواب هاي پارتوبراي سه رويکرد پيشنهادي 136

کليات تحقيق

مقدمه
توالي عمليات1 و زمان بندي2 نوعي فرايند تصميم گيري است که داراي نقشي اساسي در ارتقاي بهره وري درصنايع توليدي و خدماتي است. .به طور کلي زمان بندي، به فعاليت تخصيص تعدادي منابع محدود، در طول زمان، جهت انجام مجموعه اي محدود از فعاليت ها با هدف بهينه سازي يک يا چند معيار عملکرد گفته مي شود. از جهتي ديگر مي توان گفت زمان بندي نوعي تابع تصميم گيري بوده و فرآيندي است که در آن، برنامه زماني تعيين مي شود و در نهايت يک يا چند هدف و معيار عملکرد را بهينه سازي مي کند. در اکثر سيستم هاي ساخت و توليد يا محيط هاي فرآيند اطلاعات، زمان بندي به عنوان يک پروسه مهم تصميم گيري عمل مي کند.]1 [توالي عمليات عبارتست از تعيين ترتيب پردازش عمليات و زمان بندي عبارتست از تعيين زمان آغاز و پايان عمليات براي منابع در دسترس. در دنياي رقابتي کنوني، براي شرکت ها، داشتن بهترين توالي انجام عمليات و زمان بندي مناسب فعاليت ها يک نياز اساسي به منظور بقا مي باشد. از نظر دمپستر و همکاران ]2 [زمان بندي عبارت است از: “هنر تخصيص منابع به فعاليت ها جهت اطمينان از انجام کامل فعاليت ها در مدت زماني معقول” در عمل، زمان بندي با استفاده از الگوريتم هاي زمان بندي يا قوانين مبتني بر دانش صورت مي گيرد. امروزه به کارگيري الگوريتم هاي ابتکاري و فراابتکاري براي حل مسائل زمان بندي و به دست آوردن جواب هاي بهينه (يا نزديک بهينه) بسيار متداول است.مسائل زمان بندي معمولا داراي محدوديت و فرض هاي عمومي هستند. فرض هاي عمومي مسئله زمان
بندي در ]3 [آمده است. براي مسائل زمان بندي دسته بندي هاي مختلفي ارائه شده است. محبوب ترين و پرکاربرد ترين نحوه نمايش مسائل زمان بندي توسط گراهام و همکاران ]4 [ارائه شده است. بنا بر مدل طبقه بندي گراهام مسائل زمانبندي قطعي با سه تايي مرتب ????? يا ?/?/? نمايش مي دهند. گريوز ]5 [يک دسته بندي براي مسائل زمان بندي ارائه کرده است. شکل (1-1) اين دسته بندي مسائل را با توجه به ابعاد زير طبقه بندي مي نمايد:
تامين نيازمندي ها3
پيچيدگي فرآيند4
معيار زمان بندي5
متغير بودن پارامترها6
ترکيب کارگاه
محيط زمان بندي7

دسته بندي مسائل زمانبندي
زمان بندي را مي توان به دو صورت ايستا و پويا تقسيم نمود. به مسائل زمان بندي که در آن تعداد کارها و زمان لازم براي انجام هر عمل مشخص باشد، ايستا گفته مي شود. از طرف ديگر، مسائل زمان بندي که در آن تعداد کارها و ديگر عوامل مربوط به آن در طول زمان تغيير مي کند، پويا گفته مي شود ]7،6 [. کليات اشاره شده در مورد مسائل زمان بندي در ضميمه 1 به طور مفصل توضيح داده شده است. در اين پايان نامه، مسئله زمان بندي جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه بررسي شده و با استفاده از الگوريتم هاي ابتکاري و فراابتکاري براي مسائل تک هدفه و چند هدفه حل خواهد شدو يک روش براي تخصيص منطقي زمان هاي موعد تحويل ارائه مي شود. در اين فصل، ابتدا برخي از مفاهيم پايه اي بررسي خواهند شد، و در ادامه، کليات و مسئله تحقيق معرفي و بررسي خواهند شد و در نهايت ساختار تحقيق ارائه خواهد شد.
نگرش‌هاي عمومي در زمانبندي قطعي مسائل
بطور كلي دو نگرش عمده براي حل مسائل زمانبندي وجود دارد: نگرش‌هاي ايجادي و روش‌هاي جستجوي موضعي كه در ادامه شرح آن آمده است.
نگرش‌هاي سازنده8
اين نوع نگرش‌ها شامل قوانين توزيع9، برنامه‌ريزي پويا، برنامه‌ريزي خطي، برنامه‌ريزي اعداد صحيح، روش‌هاي شاخه و حد10 و تكنيك‌هاي جستجوي شعاعي11 مي‌باشد. برخي از اين تكنيك‌ها به جواب بهينه قطعي دست پيدا مي‌كنند كه اصطلاحاً به آنها روش‌هاي بهينه‌گرا گفته مي‌شود و برخي ديگر تنها جواب نزديك به بهينه را مي‌يابند. در روش‌هاي بهينه‌گرا در صورت وجود محدوديت‌ها و متغيرهاي بسيار زياد، فرموله‌سازي مسئله مشكل خواهد بود. عيب عمده ديگر بكارگيري روش‌هاي بهينه‌گرا اين است كه با افزايش ابعاد مسئله زمان حل مسئله، بصورت نمايي افزايش مي‌يابد. با توجه به اين نكته كه مسائل جريان كارگاهي انعطاف‌پذير از پيچيدگي بالايي برخوردارند لذا روش‌هاي مذكورتنها در برخي مسائل با ابعاد كوچك جواب مي‌دهند. افزودن فرض‌هاي جديد چون خرابي ماشين‌آلات، زمان راه‌اندازي ماشين‌آلات و… پيچيدگي هر چه بيشتر مسئله را بدنبال خواهد آورد و مسئله NP-Hard مي‌باشد.
روش‌هاي جستجوي محلي12
به منظور غلبه بر مشكلاتي كه در نگرش‌هاي ايجادي وجود دارد روش‌هاي جستجوي موضعي شكل گرفتند. اينگونه روش‌ها از طريق جستجو در همسايگي


دیدگاهتان را بنویسید