واژه‌هاي كليدي: جريان کارگاهي انعطاف پذير، بدون وقفه، دو مرحله اي، الگوريتم زنتيک هيبريدي، شبيه سازي تبريد هيبريدي، شبکه عصبي فازي تطبيق پذير، چند هدفه، فازي فهرست مطالبفصل 1: کليات تحقيق11-1- مقدمه21-2- نگرش‌هاي عمومي در زمانبندي قطعي مسائل41-2-1- نگرش‌هاي سازنده41-2-2- روشهاي جستجوي محلي51-3- مسئله جريان کارگاهي انعطاف پذير دو مرحله اي بدون وقفه51-4-کاربردهاي مدل71-5- بيان مسئله و سوال تحقيق71-6- ضرورت انجام تحقيق و اهميت تحقيق81-7- اهداف تحقيق81-8- ساختار انجام تحقيق81-9- جمع بندي10فصل 2: مرور ادبيات و پيشينه تحقيق112-1- مقدمه122-2- مساله تک هدفه جريان کارگاهي بدون وقفه122-2-1- مسائل زمانبندي جريان كارگاهي122-3- پيش بيني ماکزيمم زمان اتمام کارها222-4-مساله چند هدفه جريان کارگاهي بدون وقفه232-4-1- جريان كارگاهي بدون وقفه232-4-2- جريان كارگاهي انعطاف پذير دو مرحله اي بدون وقفه242-5- جمع بندي24فصل 3: حل تک هدفه مسئلهي مورد مطالعه با استفاده از الگوريتم هاي ابتکاري253-1- مقدمه263-2- فاز اول-مسئله بدون زمان تحويل273-2-1- ساختار الگوريتم پيشنهادي MRS1283-3- فاز دوم- مسئله با زمان تحويل313-3-1- ساختار الگوريتم پيشنهادي MRS2313-3-2- ساختار الگوريتم پيشنهادي MRS3343-3-3- ساختار الگوريتم پيشنهادي MRS4383-4- فاز سوم- مسئله با زمان تحويل و زمان آماده کار403-4-1- ساختار الگوريتم پيشنهادي MRS5403-4-2- ساختار الگوريتم پيشنهادي MRS6433-4-3- ساختار الگوريتم پيشنهادي MRS7463-5- نتايج محاسباتي الگوريتم هاي ابتکاري493-5-1- مقدمه493-6- نتايج فاز اول503-6-1- آزمايشات عددي503-6-2- پارامترهاي مدل شبيه سازي503-6-3- فرايند شبيه سازي513-6-4- نتايج شبيه سازي523-7- نتايج فاز دوم543-7-1- آزمايشات عددي543-7-2- پارامترهاي مدل شبيه سازي543-7-3- فرايند شبيه سازي563-7-4- نتايج شبيه سازي563-8- نتايج فاز سوم643-8-1- آزمايشات عددي643-8-2- پارامترهاي مدل شبيه سازي643-8-3- فرايند شبيه سازي653-8-4- نتايج شبيه سازي653-9-جمع بندي74فصل 4: حل تک هدفه مسئلهي مورد مطالعه با استفاده از الگوريتم هاي فرا ابتکاري754-1- مقدمه764-2- الگوريتم ژنتيک764-2-1- ساختار کروموزوم784-2-2- تابع برازندگي794-2-3- عملگرهاي الگوريتم ژنتيک804-2-4- شرط خاتمهي الگوريتم844-2-5- نقاط قوت الگوريتم هاي ژنتيک844-2-6- رويه ي الگوريتم ژنتيک854-3- شبيه سازي تبريد864-3-2- برنامه سردسازي874-3-3- ساختار همسايگي جديد884-3-4- رويه ي الگوريتم شبيه سازي تبريد884-4- تنظيم پارامترهاي استفاده شده براي الگوريتم ها904-5- نتايج محاسباتي الگوريتم هاي فراابتکاري914-5-1- مقدمه914-5-2- آزمايشات عددي914-5-3- پارامترهاي مدل شبيه سازي914-5-4- فرايند شبيه سازي924-5-5- نتايج شبيه سازي934-5-6- نتيجه گيري:944-6- جمع بندي95فصل 5: حل مسئله پيشبيني ماکزيمم زمان اتمام کارها965-1- مقدمه975-2- مدل فازي سوگينو975-2-2- شبکه عصبي فازي ANFIS995-2-3- الگوريتم آموزش هيبريدي (مختلط)1025-3- پيش بيني ماکزيمم زمان اتمام کارها توسط شبکه عصبي فازي تطبيق پذير1025-4- مدل رگرسيون خطي1055-5- نتايج محاسباتي1055-5-1- نتايج کلي1055-5-2- نتايج آزمون هاي آماري مربوط به معيار MSE1085-5-3- نتايج آزمون هاي آماري مربوط به معيار RMSE1095-5-4- نتايج آزمون هاي آماري مربوط به معيار R-Square1115-6- جمع بندي113فصل 6: حل مساله مورد مطالعه با رويکرد چند هدفه1146-1- مقدمه1156-2- مفاهيم پايه اي مسائل بهينه سازي چند هدفه1166-2-1- کليات بهينه سازي چند هدفه1166-2-2- چيرگي پارتو و مجموعه حل هاي غير غالب1196-2-3- مرز بهينه پارتو و مجموعه حل هاي بهينه پارتو1196-3- مروري بر روش هاي حل مسائل بهينه سازي چند هدفه1206-3-1- طبقه بندي بر اساس تعداد حل هاي بهينه به دست آمده1206-3-2- طبقه بندي بر اساس روش حل1216-4- روش هاي پيشنهادي براي حل چند هدفه مسئله مورد مطالعه1226-4-1- روش وزني کلاسيک1236-4-2- روش مجموع وزني نرمالايز شده توابع هدف1246-4-3- روش فازي1266-5- معيارهاي مقايسه رويکردهاي چندهدفه1306-5-1- تعداد جواب هاي پارتو1306-5-2- پراکندگي جواب هاي پارتو1306-5-3- درصد چيرگي در پارتو ترکيبي1316-5-4- مجموع انحراف بهترين جواب هاي هر تابع هدف از بهترين جواب هاي پارتو1316-6- جمع بندي136فصل 7: جمع‌بندي و پيشنهاد براي تحقيقات آتي1377-1- مقدمه1387-2- جمع‌بندي و خلاصه ي نتايج1387-3- نوآوري و مشارکت علمي1387-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) فرايند اجراي الگوريتم ژنتيک براي مسئله ي NWTSFFS84شکل (4-8) نمودار الگوريتم ژنتيک هيبريدي براي مسئله ي NWTSFFS85شکل (4-9) نمودار الگوريتم شبيه سازي تبريد هيبريدي براي مسئله ي NWTSFFS89شکل (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) توالي به دست امده براي کارها توسط الگوريتم MRS130جدول (3-7) زمان هاي پردازش و موعد تحويل براي مثال ارائه شده32جدول (3-8) تکرار اول الگوريتم MRS232جدول (3-9) تکرار دوم الگوريتم MRS233جدول (3-10) توالي به دست آمده براي کارها توسط الگوريتم MRS234جدول (3-11) زمان هاي پردازش و موعد تحويل براي مثال ارائه شده35جدول (3-12) تکرار اول الگوريتمMRS336جدول (3-13) تکرار دوم الگوريتم MRS337جدول (3-14) توالي به دست امده براي کارها توسط الگوريتم MRS337جدول (3-15) زمان هاي پردازش و موعد تحويل براي مثال ارائه شده39جدول (3-16) چگونگي روش حل الگوريتم MRS439جدول(3-17) توالي به دست آمده براي کارها و ماشين ها توسط الگوريتم MRS440جدول (3-18) زمان هاي پردازش و موعد تحويل براي مثال ارائه شده42جدول(3-19) تکرار اول الگوريتم MRS542جدول (3-20) تکرار دوم الگوريتم MRS543جدول (3-21) توالي به دست امده براي کارها و ماشين ها توسط الگوريتم MRS543جدول (3-22) زمان هاي پردازش و موعد تحويل براي مثال ارائه شده44جدول(3-23) انتخاب کار درتکرار اول الگوريتم MRS644جدول (3-24) انتخا ب ماشين براي کار اول انتخاب شده توسط الگوريتم MRS645جدول (3-25) جدول اتتخاب کار درتکرار دوم الگوريتم MRS645جدول(3-26) انتخا ب ماشين براي کار دوم انتخاب شده توسط الگوريتم MRS645جدول (3-27) توالي به دست آمده براي کارها و ماشين ها توسط الگوريتم MRS646جدول(3-28) زمان هاي پردازش و موعد تحويل و زمان آماده کار براي مثال ارائه شده47جدول(3-29) نحوه محاسبه توالي به دست آمده براي کارها توسط الگوريتم MRS748جدول (3-30) توالي به دست آمده براي کارها و ماشين ها توسط الگوريتم MRS748جدول (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 و HGA90جدول (4-2) پارامترهاي مدل شبيه سازي براي الگوريتم هاي فراابتکاري92جدول (4-3) نتايج آماري الگوريتم هاي فراابتکاري93جدول (4-4) نتايج به دست آمده براي سايز کوچک94جدول (4-5) نتايج به دست آمده براي سايز بزرگ95جدول (5-1) پارامترهاي مدل شبيه سازي104جدول (5-2) پارامترهاي موثر روي مدل شبکه عصبي فازي تطبيق پذير105جدول (5-3) نتايج به دست آمده براي معيار R-Square106جدول (5-4) نتايج به دست آمده براي معيار MSE و RMSE107جدول (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: کليات تحقيق 1-1- مقدمهتوالي عمليات[1] و زمانبندي[2] نوعي فرايند تصميم گيري است که داراي نقشي اساسي در ارتقاي بهره وري درصنايع توليدي و خدماتي است. .بهطورکليزمانبندي،بهفعاليتتخصيصتعداديمنابعمحدود،درطولزمان،جهتانجاممجموعهاي محدودازفعاليتهاباهدفبهينهسازييکياچندمعيارعملکردگفتهميشود. ازجهتيديگرميتوانگفت زمانبندينوعيتابعتصميمگيريبودهوفرآيندياستکهدرآن،برنامهزمانيتعيينميشودودرنهايتيکيا چندهدفومعيارعملکردرابهينهسازيميکند. دراکثرسيستمهايساختوتوليديامحيطهايفرآينداطلاعات، زمانبنديبهعنوانيکپروسهمهمتصميمگيريعملميکند.]1 [توالي عمليات عبارتست از تعيين ترتيب پردازش عمليات و زمانبندي عبارتست از تعيين زمان آغاز و پايان عمليات براي منابع در دسترس. در دنياي رقابتي کنوني، براي شرکت ها، داشتن بهترين توالي انجام عمليات و زمان بندي مناسب فعاليت هايک نياز اساسي به منظور بقا مي باشد. از نظر دمپستر و همکاران ]2 [زمان بندي عبارت است از: "هنر تخصيص منابع به فعاليت ها جهت اطمينان از انجام کامل فعاليت ها در مدت زماني معقول" در عمل، زمان بندي با استفاده از الگوريتم هاي زمان بندي يا قوانين مبتني بر دانش صورت مي گيرد. امروزه به کارگيري الگوريتم هاي ابتکاري و فراابتکاري براي حل مسائل زمان بندي و به دست آوردن جواب هاي بهينه (يا نزديک بهينه) بسيار متداول است.مسائل زمان بندي معمولا داراي محدوديت و فرض هاي عمومي هستند. فرض هاي عمومي مسئله زمان بندي در ]3 [آمده است. براي مسائل زمان بندي دسته بندي هاي مختلفي ارائه شده است. محبوب ترين و پرکاربرد ترين نحوه نمايش مسائل زمان بندي توسط گراهام و همکاران ]4 [ارائه شده است. بنابرمدلطبقهبنديگراهام مسائلزمانبنديقطعيباسهتاييمرتب α│β│γ يا α/β/γ نمايش مي دهند. گريوز ]5 [يک دسته بندي براي مسائل زمان بندي ارائه کرده است. شکل (1-1) اين دسته بندي مسائل را با توجه به ابعاد زير طبقه بندي مي نمايد:شکل (1-1) دسته بندي مسائل زمانبنديزمان بندي را مي توان به دو صورت ايستا و پويا تقسيم نمود. به مسائل زمان بندي که در آن تعداد کارها و زمان لازم براي انجام هر عمل مشخص باشد، ايستا گفته مي شود. از طرف ديگر، مسائل زمان بندي که در آن تعداد کارها و ديگر عوامل مربوط به آن در طول زمان تغيير مي کند، پويا گفته مي شود ]7،6 [. کليات اشاره شده در مورد مسائل زمان بندي در ضميمه 1 به طور مفصل توضيح داده شده است. در اين پايان نامه، مسئله زمان بندي جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه بررسي شده و با استفاده از الگوريتم هاي ابتکاري و فراابتکاري براي مسائل تک هدفه و چند هدفه حل خواهد شدو يک روش براي تخصيص منطقي زمان هاي موعد تحويل ارائه مي شود. در اين فصل، ابتدا برخي از مفاهيم پايه اي بررسي خواهند شد، و در ادامه، کليات و مسئله تحقيق معرفي و بررسي خواهند شد و در نهايت ساختار تحقيق ارائه خواهد شد.1-2- نگرش‌هاي عمومي در زمانبندي قطعي مسائلبطور كلي دو نگرش عمده براي حل مسائل زمانبندي وجود دارد: نگرش‌هاي ايجادي و روشهاي جستجوي موضعي كه در ادامه شرح آن آمده است.1-2-1- نگرش‌هاي سازنده[8]اين نوع نگرش‌ها شامل قوانين توزيع[9]، برنامه‌ريزي پويا، برنامه‌ريزي خطي، برنامه‌ريزي اعداد صحيح، روشهاي شاخه و حد[10] و تكنيك‌هاي جستجوي شعاعي[11]مي‌باشد. برخي از اين تكنيك‌ها به جواب بهينه قطعي دست پيدا مي‌كنند كه اصطلاحاً به آنها روشهاي بهينه‌گرا گفته مي‌شود و برخي ديگر تنها جواب نزديك به بهينه را مي‌يابند. در روشهاي بهينه‌گرا در صورت وجود محدوديت‌ها و متغيرهاي بسيار زياد، فرموله‌سازي مسئله مشكل خواهد بود. عيب عمده ديگر بكارگيري روشهاي بهينه‌گرا اين است كه با افزايش ابعاد مسئله زمان حل مسئله، بصورت نمايي افزايش مي‌يابد. با توجه به اين نكته كه مسائل جريان كارگاهي انعطاف‌پذير از پيچيدگي بالايي برخوردارند لذا روشهاي مذكورتنها در برخي مسائل با ابعاد كوچك جواب مي‌دهند. افزودن فرض‌هاي جديد چون خرابي ماشين‌آلات، زمان راه‌اندازي ماشين‌آلات و... پيچيدگي هر چه بيشتر مسئله را بدنبال خواهد آورد و مسئله NP-Hardمي‌باشد.1-2-2- روشهاي جستجوي محلي[12]به منظور غلبه بر مشكلاتي كه در نگرش‌هاي ايجادي وجود دارد روشهاي جستجوي موضعي شكل گرفتند. اينگونه روش‌ها از طريق جستجو در همسايگي راه‌حل‌هاي موجود، به يافتن حل نزديك به بهينه مي‌پردازد كه از جمله آنها روشهاي فرا ابتكاري و تجزيه مسائل مي‌باشند كه در بسياري از تحقيقات جديد از روشهاي فرا ابتكاري مانند الگوريتم جستجوي ممنوع[13]، شبيه‌سازي تبريد[14]، الگوريتم ژنتيك، كلني مورچه‌ها[15]، جستجوي پراكنده[16] و... جهت حل مسائل زمانبندي استفاده شده است. در بسياري از اين تحقيقات كارايي روشهاي مذكور به اثبات رسيده و مي‌توان نتيجه گرفت كه به شرط طراحي صحيح يك الگوريتم فرا ابتكاري مي‌توان به نتايج قابل توجهي جهت حل مسائل با ابعاد بالا دست يافت1-3- مسئله جريان کارگاهي انعطاف پذير دو مرحله اي بدون وقفهبه طور کلي اين مدل حالت خاصي از مسئله جريان کارگاهي است. مسئله مورد مطالعه به شرح زير مي باشد. يک مجموعه شامل n کار است که قرار است پردازش شوند. هر کار نياز به دو عمليات دارد که بايد در دو مرحله متوالي و و بدون وقفه پردازش شوند. مرحله اول شامل ماشين يکسان و مشابه آن مرحله دو شامل ماشين يکسان است. اولين و دومين عمليات مربوط به کار بايد به ترتيب روي ماشين هاي مرحله اول و دوم با زمان هاي پردازش و و به ترتيب و بدون وقفه انجام شوند. اين مسئله را مي توانيم به صورت نمايش دهيم. مسئله مورد مطالعه در اين تحقيق به صورت شماتيک درشکل (1-2)نمايش داده شده است. همانطور که در شکل نيز ميبينيم هر کار حالت ممکن براي قرار گرفتن روي ماشين هاي مرحله اول و دوم دارد و همچنين n کار موجود حالت ممکن براي توالي دارند. به اين ترتيب در اين مسئله با توجه به ابعاد مسئله برنامه زماني مختلف مي توانيم داشته باشيم که تست کردن کليه اين برنامه ها بسيار سخت و پيچيده است. بنابراين هدف ما در گام اول ارائه يکي از برنامه هاي زماني در بينحالت مختلف است که کارايي مناسبي نيز نسبت به ساير الگوريتم هاي هيوريستيک موجود داشته باشد. و در گام دوم ارائه جواب هاي پارتو به اين منظور که تصميم گيرنده گزينه هاي بيشتري براي زمان بندي در اختيار داشته باشد.