دانشگاه صنعتي خواجه نصيرالدين طوسي
دانشکده مهندسي صنايع
حل مسئله جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه
ميثم ربيعي
پايان‌نامه براي دريافت مدرک کارشناسي ارشد
در رشته مهندسي صنايع گرايش صنايع
مهر ماه 1389
دانشگاه صنعتي خواجه نصيرالدين طوسي
دانشکده مهندسي صنايع
حل مسئله جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه
نام دانشجو: ميثم ربيعي
استاد راهنما: دكتر رسول شفائي
استاد مشاور: دکتر فريد خوش الحان
پاِيان نامه کارشناسِي ارشد
رشته مهندسِي صناِيع
مهر ماه 1389
تقديم به:
تقديم به پدر دلسوز
و
مادرمهربانم
حل مسئله جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه
ميثم ربيعي
تاييد هيئت داوران:
دکتر رسول شفائي
استاد راهنماي پروژه
دکتر فريد خوش الحان
استاد مشاور پروژه
دکتر
داور داخلي
دکتر
داور خارجي
پذيرش دانشکده :
دکتر مصطفي ستاک
معاون آموزشي و تحصيلات تکميلي دانشکده
تأييد پايان نامه کارشناسي ارشد توسط دانشجو
عنوان پايان نامه: حل مسئله جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه
نام دانشجو: ميثم ربيعي
شماره دانشجويي: 8705934
استاد راهنماي پروژه: دکتر رسول شفائي
اينجانب ميثم ربيعي دانشجوي کارشناسي ارشد رشته مهندسي صنايع دانشکده مهندسي صنايع دانشگاه خواجه نصيرالدين طوسي گواهي مي نمايم که تحقيقات ارائه شده در پايان نامه تحت عنوان فوق الذکر توسط شخص اينجانب انجام شده است و صحت و اصالت مطالب نگارش شده مورد تاييد مي باشد و در هر کجا که از مطالب نگارش شده ديگري استفاده شده است با ذکر منبع و ماخذ مي باشد. به علاوه گواهي مي نمايم که مطالب مندرج در پايان نامه تا کنون براي دريافت هيچ نوع مدرک يا امتيازي توسط اينجانب يا فرد ديگري در هيچ کجا ارائه نشده است و در تدوين متن پايان نامه شيوه نگارش مصوب دانشکده مهندسي صنايع را بطور کامل رعايت نموده ام. چنانچه در هر زمان خلاف آنچه گواهي نموده ام مشاهده گردد خود را از آثار حقيقي و حقوقي ناشي از دريافت مدرک کارشناسي ارشد محروم مي دانم و هيچگونه ادعايي نخواهم داشت.

نام و نام خانوادگي:
امضا و تاريخ:
تشكر و قدرداني:
اکنون که دوره اي ديگر از دوران تحصيلم به پايان مي رسد، از ذات حق تعالي استعانت مي جويم براي ادامه اين مسير و اميدوارم در مسير آينده زندگي ام با لطف و کرمش همواره در راستاي بندگي قدم بردارم، نه بيش و نه کم.
همچنين بر خود لازم مي دانم که از راهنمائيها و کمک هاي بي دريغ استاد راهنما، جناب آقاي دکتر رسول شفائي که بي شک نقش انکار ناپذيري در به ثمررسيدن اين پايان نامه داشتند، نهايت سپاسگذاري و تشکر را داشته باشم . از جناب آقاي دکتر فريد خوش الحان که در طول انجام اين پايان نامه به عنوان استاد مشاور، نظرات سازنده و ارزشمندي ارائه کردند، تشکر مي نمايم.
چکيده
در شرايط حاضر و با توجه به افزايش شدت رقابت سازمان هاي توليدي، برنامه زمان بندي از اهميت بيشتري برخوردار مي باشد. در صورت انجام برنامه زمان بندي بهينه، امکان استفاده بهتر از منابع موجود فراهم شده و محصولات مطابق نايز مشتريان توليد و تحويل مي شوند. در اين تحقيق مسئله جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه حل شده است. در اين مسئله فرايند توليد همه قطعات مثل هم بوده و از دو مرحله تشکيل شده است. همچنين در هر مرحله امکان انجام کار توسط ماشين هاي موازي(مشابه هم) وجود دارد. علاوه بر آن بين مراحل اول و دوم هر قطعه هيچگونه وقفه اي وجود ندارد. در اين تحقيق دو هدف کلي براي مسئله در نظر گرفته شده است. هدف اول حل تک هدفه و حل چند هدفه مسئله فوق الذکر است. مسئله را با در نظر گرفتن زمان هاي پردازش مرحله اول و دوم توسط الگوريتم هاي ابتکاري و فراابتکاري حل نموده و در ادامه محدوديت زمان آماده کار را به مسئله اضافه نموده و مجددا توسط الگوريتم هاي ابتکاري حل مي نمائيم. توابع هدف در نظر گرفته شده براي مسئله تک هدفه عبارتند از:
حداکثر کردن درصد بهره برداري از ماشين آلات و حداقل سازي توابع حداکثر زمان اتمام کارها، متوسط زمان اتمام کارها، متوسط زمان در جريان کار، ماکزيمم تاخير، ماکزيمم ديرکرد، متوسط تاخير ، متوسط ديرکرد و تعداد کارهاي تاخيردار
در ادامه حل مسئله اشاره شده به صورت چند هدفه ( با زمان آماده کار صفر)، با استفاده از الگوريتم هاي شبيه سازي تبريد و با در نظر گرفتن سه رويکرد متفاوت در تابع برازندگي مد نظر مي باشد. توابع استفاده شده براي مسئله چند هدفه مينيمم سازي ماکزيمم زمان اتمام کارها و مينيمم سازي ماکزيمم تاخير مي باشد. هدف دوم اين تحقيق پيش بيني ماکزيمم زمان اتمام کارها براي مسئله ذکر شده است. کاربرد هدف در نظر گرفته شده براي اين مسئله تعيين زمان منطقي تحويل قطعات به مشتريان مي باشد. به اين منظور از مدل شبکه عصبي فازي تطبيق پذير استفاده شده است. در پايان عملکرد روشهاي ارائه شده بر روي حل مسئله جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه بررسي شده و نتايج حاصله به صورت آماري مورد ارزيابي قرار گرفته است.
واژه‌هاي كليدي: جريان کارگاهي انعطاف پذير، بدون وقفه، دو مرحله اي، الگوريتم زنتيک هيبريدي، شبيه سازي تبريد هيبريدي، شبکه عصبي فازي تطبيق پذير، چند هدفه، فازي
فهرست مطالب
فصل 1: کليات تحقيق1
1-1- مقدمه2
1-2- نگرش‌هاي عمومي در زمانبندي قطعي مسائل4
1-2-1- نگرش‌هاي سازنده4
1-2-2- روش‌هاي جستجوي محلي5
1-3- مسئله جريان کارگاهي انعطاف پذير دو مرحله اي بدون وقفه5
1-4-کاربردهاي مدل7
1-5- بيان مسئله و سوال تحقيق7
1-6- ضرورت انجام تحقيق و اهميت تحقيق8
1-7- اهداف تحقيق8
1-8- ساختار انجام تحقيق8
1-9- جمع بندي10
فصل 2: مرور ادبيات و پيشينه تحقيق11
2-1- مقدمه12
2-2- مساله تک هدفه جريان کارگاهي بدون وقفه12
2-2-1- مسائل زمان‌بندي جريان كارگاهي12
2-3- پيش بيني ماکزيمم زمان اتمام کارها22
2-4-مساله چند هدفه جريان کارگاهي بدون وقفه23
2-4-1- جريان كارگاهي بدون وقفه23
2-4-2- جريان كارگاهي انعطاف پذير دو مرحله اي بدون وقفه24
2-5- جمع بندي24
فصل 3: حل تک هدفه مسئله ي مورد مطالعه با استفاده از الگوريتم هاي ابتکاري25
3-1- مقدمه26
3-2- فاز اول-مسئله بدون زمان تحويل27
3-2-1- ساختار الگوريتم پيشنهادي MRS128
3-3- فاز دوم- مسئله با زمان تحويل31
3-3-1- ساختار الگوريتم پيشنهادي MRS231
3-3-2- ساختار الگوريتم پيشنهادي MRS334
3-3-3- ساختار الگوريتم پيشنهادي MRS438
3-4- فاز سوم- مسئله با زمان تحويل و زمان آماده کار40
3-4-1- ساختار الگوريتم پيشنهادي MRS540
3-4-2- ساختار الگوريتم پيشنهادي MRS643
3-4-3- ساختار الگوريتم پيشنهادي MRS746
3-5- نتايج محاسباتي الگوريتم هاي ابتکاري49
3-5-1- مقدمه49
3-6- نتايج فاز اول50
3-6-1- آزمايشات عددي50
3-6-2- پارامترهاي مدل شبيه سازي50
3-6-3- فرايند شبيه سازي51
3-6-4- نتايج شبيه سازي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- شبکه عصبي فازي ANFIS99
5-2-3- الگوريتم آموزش هيبريدي (مختلط)102
5-3- پيش بيني ماکزيمم زمان اتمام کارها توسط شبکه عصبي فازي تطبيق پذير102
5-4- مدل رگرسيون خطي105
5-5- نتايج محاسباتي105
5-5-1- نتايج کلي105
5-5-2- نتايج آزمون هاي آماري مربوط به معيار MSE108
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) فرايند اجراي الگوريتم ژنتيک براي مسئله ي 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 و زمان بندي2 نوعي فرايند تصميم گيري است که داراي نقشي اساسي در ارتقاي بهره وري درصنايع توليدي و خدماتي است. .به طور کلي زمان بندي، به فعاليت تخصيص تعدادي منابع محدود، در طول زمان، جهت انجام مجموعه اي محدود از فعاليت ها با هدف بهينه سازي يک يا چند معيار عملکرد گفته مي شود. از جهتي ديگر مي توان گفت زمان بندي نوعي تابع تصميم گيري بوده و فرآيندي است که در آن، برنامه زماني تعيين مي شود و در نهايت يک يا چند هدف و معيار عملکرد را بهينه سازي مي کند. در اکثر سيستم هاي ساخت و توليد يا محيط هاي فرآيند اطلاعات، زمان بندي به عنوان يک پروسه مهم تصميم گيري عمل مي کند.]1 [توالي عمليات عبارتست از تعيين ترتيب پردازش عمليات و زمان بندي عبارتست از تعيين زمان آغاز و پايان عمليات براي منابع در دسترس. در دنياي رقابتي کنوني، براي شرکت ها، داشتن بهترين توالي انجام عمليات و زمان بندي مناسب فعاليت ها يک نياز اساسي به منظور بقا مي باشد. از نظر دمپستر و همکاران ]2 [زمان بندي عبارت است از: “هنر تخصيص منابع به فعاليت ها جهت اطمينان از انجام کامل فعاليت ها در مدت زماني معقول” در عمل، زمان بندي با استفاده از الگوريتم هاي زمان بندي يا قوانين مبتني بر دانش صورت مي گيرد. امروزه به کارگيري الگوريتم هاي ابتکاري و فراابتکاري براي حل مسائل زمان بندي و به دست آوردن جواب هاي بهينه (يا نزديک بهينه) بسيار متداول است.مسائل زمان بندي معمولا داراي محدوديت و فرض هاي عمومي هستند. فرض هاي عمومي مسئله زمان بندي در ]3 [آمده است. براي مسائل زمان بندي دسته بندي هاي مختلفي ارائه شده است. محبوب ترين و پرکاربرد ترين نحوه نمايش مسائل زمان بندي توسط گراهام و همکاران ]4 [ارائه شده است. بنا بر مدل طبقه بندي گراهام مسائل زمانبندي قطعي با سه تايي مرتب α│β│γ يا α/β/γ نمايش مي دهند. گريوز ]5 [يک دسته بندي براي مسائل زمان بندي ارائه کرده است. شکل (1-1) اين دسته بندي مسائل را با توجه به ابعاد زير طبقه بندي مي نمايد:
تامين نيازمندي ها3
پيچيدگي فرآيند4
معيار زمان بندي5
متغير بودن پارامترها6
ترکيب کارگاه
محيط زمان بندي7
دسته بندي مسائل زمانبندي
زمان بندي را مي توان به دو صورت ايستا و پويا تقسيم نمود. به مسائل زمان بندي که در آن تعداد کارها و زمان لازم براي انجام هر عمل مشخص باشد، ايستا گفته مي شود. از طرف ديگر، مسائل زمان بندي که در آن تعداد کارها و ديگر عوامل مربوط به آن در طول زمان تغيير مي کند، پويا گفته مي شود ]7،6 [. کليات اشاره شده در مورد مسائل زمان بندي در ضميمه 1 به طور مفصل توضيح داده شده است. در اين پايان نامه، مسئله زمان بندي جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه بررسي شده و با استفاده از الگوريتم هاي ابتکاري و فراابتکاري براي مسائل تک هدفه و چند هدفه حل خواهد شدو يک روش براي تخصيص منطقي زمان هاي موعد تحويل ارائه مي شود. در اين فصل، ابتدا برخي از مفاهيم پايه اي بررسي خواهند شد، و در ادامه، کليات و مسئله تحقيق معرفي و بررسي خواهند شد و در نهايت ساختار تحقيق ارائه خواهد شد.
نگرش‌هاي عمومي در زمانبندي قطعي مسائل
بطور كلي دو نگرش عمده براي حل مسائل زمانبندي وجود دارد: نگرش‌هاي ايجادي و روش‌هاي جستجوي موضعي كه در ادامه شرح آن آمده است.
نگرش‌هاي سازنده8
اين نوع نگرش‌ها شامل قوانين توزيع9، برنامه‌ريزي پويا، برنامه‌ريزي خطي، برنامه‌ريزي اعداد صحيح، روش‌هاي شاخه و حد10 و تكنيك‌هاي جستجوي شعاعي11 مي‌باشد. برخي از اين تكنيك‌ها به جواب بهينه قطعي دست پيدا مي‌كنند كه اصطلاحاً به آنها روش‌هاي بهينه‌گرا گفته مي‌شود و برخي ديگر تنها جواب نزديك به بهينه را مي‌يابند. در روش‌هاي بهينه‌گرا در صورت وجود محدوديت‌ها و متغيرهاي بسيار زياد، فرموله‌سازي مسئله مشكل خواهد بود. عيب عمده ديگر بكارگيري روش‌هاي بهينه‌گرا اين است كه با افزايش ابعاد مسئله زمان حل مسئله، بصورت نمايي افزايش مي‌يابد. با توجه به اين نكته كه مسائل جريان كارگاهي انعطاف‌پذير از پيچيدگي بالايي برخوردارند لذا روش‌هاي مذكورتنها در برخي مسائل با ابعاد كوچك جواب مي‌دهند. افزودن فرض‌هاي جديد چون خرابي ماشين‌آلات، زمان راه‌اندازي ماشين‌آلات و… پيچيدگي هر چه بيشتر مسئله را بدنبال خواهد آورد و مسئله NP-Hard مي‌باشد.
روش‌هاي جستجوي محلي12
به منظور غلبه بر مشكلاتي كه در نگرش‌هاي ايجادي وجود دارد روش‌هاي جستجوي موضعي شكل گرفتند. اينگونه روش‌ها از طريق جستجو در همسايگي راه‌حل‌هاي موجود، به يافتن حل نزديك به بهينه مي‌پردازد كه از جمله آنها روش‌هاي فرا ابتكاري و تجزيه مسائل مي‌باشند كه در بسياري از تحقيقات جديد از روش‌هاي فرا ابتكاري مانند الگوريتم جستجوي ممنوع13، شبيه‌سازي تبريد14، الگوريتم ژنتيك، كلني مورچه‌ها15، جستجوي پراكنده16 و… جهت حل مسائل زمانبندي استفاده شده است. در بسياري از اين تحقيقات كارايي روش‌هاي مذكور به اثبات رسيده و مي‌توان نتيجه گرفت كه به شرط طراحي صحيح يك الگوريتم فرا ابتكاري مي‌توان به نتايج قابل توجهي جهت حل مسائل با ابعاد بالا دست يافت
مسئله جريان کارگاهي انعطاف پذير دو مرحله اي بدون وقفه
به طور کلي اين مدل حالت خاصي از مسئله جريان کارگاهي است. مسئله مورد مطالعه به شرح زير مي باشد. يک مجموعه شامل n کار است که قرار است پردازش شوند. هر کار نياز به دو عمليات دارد که بايد در دو مرحله متوالي و و بدون وقفه پردازش شوند. مرحله اول شامل ماشين يکسان و مشابه آن مرحله دو شامل ماشين يکسان است. اولين و دومين عمليات مربوط به کار بايد به ترتيب روي ماشين هاي مرحله اول و دوم با زمان هاي پردازش و و به ترتيب و بدون وقفه انجام شوند. اين مسئله را مي توانيم به صورت نمايش دهيم. مسئله مورد مطالعه در اين تحقيق به صورت شماتيک در شکل (1-2) نمايش داده شده است. همانطور که در شکل نيز ميبينيم هر کار حالت ممکن براي قرار گرفتن روي ماشين هاي مرحله اول و دوم دارد و همچنين n کار موجود حالت ممکن براي توالي دارند. به اين ترتيب در اين مسئله با توجه به ابعاد مسئله برنامه زماني مختلف مي توانيم داشته باشيم که تست کردن کليه اين برنامه ها بسيار سخت و پيچيده است. بنابراين هدف ما در گام اول ارائه يکي از برنامه هاي زماني در بينحالت مختلف است که کارايي مناسبي نيز نسبت به ساير الگوريتم هاي هيوريستيک موجود داشته باشد. و در گام دوم ارائه جواب هاي پارتو به اين منظور که تصميم گيرنده گزينه هاي بيشتري براي زمان بندي در اختيار داشته باشد.
نماي شماتيک مسئله
کاربردهاي مدل
مسائل زمان‌بندي بدون انتظار در آن دسته از محيط‌هاي توليدي رخ مي‌دهد كه در آن يك كار مي‌بايست از آغاز تا پايان بر روي يك ماشين يا در بين ماشينها بدون وقفه مورد پردازش قرار گيرد. علت وقوع چنين محيطهايي نوع فن‌آوري و يا فقدان توانايي ذخيره‌سازي بين ماشينها و ايستگاههاي كاري است. بطور نمونه عامل دما، غلظت و يا ديگر عوامل باعث مي‌شود هر عملياتي، عمليات پيش از خود را بلافاصله دنبال كند. در توليد فولاد، هنگامي كه فولاد مذاب در برابر يكسري عمليات متوالي مانند ريخته‌گري، ذوب و نورد قرار مي‌گيرد. چنين وضعيتي رخ مي‌دهد،. همچنين در صنايع غذايي، عمليات قرار دادن محصولات غذايي داخل قوطي هاي کنسرو بايد بلافاصله بعد از پخت انجام شود تا از تازه بودن اين محصولات اطمينان حاصل نمائيم. در صنايع دارويي، شيميايي، پتروشيمي و صنايع خدماتي و… چنين مواردي رخ مي‌دهد. محيط‌هاي توليدي جديد مانند توليد به هنگام17، سيستمهاي توليدي انعطاف‌پذير18 و سلولهاي روباتيك فرآيند توليدي منطبق با مسايل زمان‌بندي بدون انتظار را فراهم مي‌كنند.
بيان مسئله و سوال تحقيق
در اين تحقيق، مسئله جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه با هدف تعيين توالي توليد بهينه (نزديک بهينه) با توجه به اهداف کمينه سازي و بيشينه سازي مورد بررسي قرار مي گيرد. هم چنين، ارائه الگوريتم هاي کارا و مبتني بر رويکرد هاي ابتکاري و فراابتکاري در دستور کار قرار گرفته است که با استفاده از آن بتوان به مجموعه جواب هاي مناسب رسيد.
ضرورت انجام تحقيق و اهميت تحقيق
با توجه به کاربردهاي عنوان شده براي مسئله برنامه زمان بندي جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه از يک طرف و تحقيقات بسيار محدود انجام شده در اين زمينه از طرف ديگر، ضروري است تحقيقات بيش تري با هدف ارائه روش هاي کاراتر انجام پذيرد. از اين رو، اين موضوع به عنوان موضوع تحقيقي مورد نظر اين پايان نامه در نظر گرفته شده است.
اهداف تحقيق
به طور کلي اهداف اصلي اين تحقيق به شرح زير مي باشد:
گسترش مدل و سازگار نمودن هرچه بيش تر آن با مسائل دنياي واقعي با درنظر گرفتن چندين تابع هدف و در نظر گرفتن محدوديت زمان در دسترس بودن کارها
ارائه الگوريتم هاي ابتکاري براي مسئله جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه
اتخاذ رويکردي فراابتکاري در حل مسئله جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه
پيش بيني ماکزيمم زمان انجام کارها در مسئله جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه به منظور تخصيص منطقي زمان هاي موعد تحويل توسط شبکه عصبي فازي تطبيق پذير
حل مسئله چند هدفه جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه
ساختار انجام تحقيق
اين پايان نامه، با بررسي پيشينه و مطالعات صورت گرفته در رابطه مدل تحقيق، به تعيين خلاء هاي موجود در اين زمينه پرداخته و مسئله توسط روش هاي ابتکاري با در نظر گرفتن چندين تابع هدف (به صورت تک هدفه) و اضافه نمودن محدوديت زمان آماده به کار حل مي شود. در ادامه مسئله توسط روش هاي فراابتکاري الگوريتم ژنتيک هيبريدي و الگوريتم شبيه سازي تبريد هيبريدي حل مي شود. نتايج حاصله از الگوريتم ابتکاري و فرا ابتکاري با الگوريتم هاي ارائه شده در مطالعات قبلي مقايسه مي شود.. شکل (1-3) ساختار تحقيق را به صورت شماتيک نشان مي دهد.
ساختار تحقيق به صورت شماتيک
ساختار پايان نامه به شرح زير مي باشد:
در فصل اول، کليات تحقيق بيان شده ، مساله مورد مطالعه تعريف شده و اهدف تحقيق به تفصيل توضيح داده مي شود. در فصل دوم، ادبيات موضوع مرتبط با مساله تحقيق مرور شده و توانمندي روش هاي استفاده شده مورد تجزيه و تحليل قرار مي گيرد. در فصل سوم،حل مساله به صورت تک هدفه مد نظر مي باشد. هفت الگوريتم هاي ابتکاري پيشنهاد شده و نتايج حاصله در ادامه فصل آورده شده است. در فصل چهارم الگوريتم هاي فراابتکاري ژنتيک هيبريدي و شبيه سازي تبريد هيبريدي براي مساله مورد مطالعه، معرفي مي شوند و نتايج هر يک از آنها در ادامه فصل آورده شده است. در فصل پنجم به منظور تخصيص موعد هاي تحويل منطقي براي کارها، مدل عصبي فازي تطبيق پذير به منظور پيش بيني ماکزيمم زمان اتمام کارها معرفي شده است و نتايج حاصل از مقايسه اين مدل پيشنهادي با رگرسيون خطي در ادامه فصل براي برخي معيارهاي ارزيابي عملکرد در پيش بيني آورده شده است. در فصل ششم حل مساله جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه چند هدفه با در نظر گرفتن توابع مينيمم سازي ماکزيمم زمان اتمام کارها و مينيمم سازي ماکزيمم تاخير کارها مورد مطالعه قرار گرفته شده و 3 رويکرد متفاوت در تابع برازندگي با استفاده از الگوريتم شبيه سازي تبريد براي اين مساله معرفي شده است و در انتهاي فصل نتايج حاصل از مقايسه ميان رويکرد هاي پيشنهادي آورده شده است. و در نهايت ، فصل هفتم، خلاصه و جمع بندي تحقيق انجام شده را بيان مي کند و پيشنهادهايي براي تحقيقات آتي ارائه مي شود.
جمع بندي
در اين فصل، مسئله زمان بندي جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه به عنوان مسئله تحقيق معرفي، و ضرورت انجام تحقيق در اين خصوص بيان شد. با توجه به ساختار و سطح پيچيدگي مسئله انتخابي، رو ش هاي پيشنهادي جهت حل مسئله به همراه ساختار انجام تحقيق مطرح گرديد. در فصل بعد، تحقيقات انجام شده مرتبط با موضوع تحقيق بحث و بررسي خواهد شد.
مرور ادبيات و پيشينه تحقيق
مقدمه
در اين فصل به مرور ادبيات و بررسي پيشينه تحقيق، پرداخته مي شود. تحقيقات انجام شده پيرامون مسئله تحقيق بررسي شده و خلاء تحقيقاتي موجود معرفي مي گردد.
مساله تک هدفه جريان کارگاهي بدون وقفه
مسائل زمان‌بندي جريان كارگاهي
در اين بخش تاريخچه خلاصه‌اي از كارهاي صورت گرفته مسائل در زمان‌بندي جريان كارگاهي و همچنين تاريخچه‌اي از تحقيقات صورت گرفته در مسائل جريان كارگاهي انعطاف‌پذير و روشهايي كه براي حل اين مسائل به كار رفته است، مرور خواهيم كرد.
مسئله جريان كارگاهي ساده
اين مسئله يكي از رايج‌ترين انواع مسائل جريان كارگاهي است كه در مرور ادبيات موضوع جريان كارگاهي به وفور ديده مي‌شود. در سال 1954 جانسون [8] يك الگوريتم براي حل مسئله دو ماشينه جريان كارگاهي كه بدون هيچ‌گونه محدوديتي بوده ارائه نمود. از آن موقع به بعد كارهاي زيادي در اين حوزه انجام گرفته و كه شامل الگوريتم‌هاي ابتكاري، الگوريتم‌هاي دقيق براي چندين مسئله با ابعاد گوناگون و محدوديت‌هاي متنوع مي‌باشند. ثابت شده است كه مسئله با تعدناد ماشين‌هاي بيشتر يا مساوي با 3 يك مسئله Np-hard مي‌باشد. كارهاي بسيار زيادي در اين حوزه صورت گرفته ولي با توجه به اينكه تحقيق انجام شده از طرف ما بصورت مستقيم به اين مسئله مربوط نمي‌شود مرور ادبيات موضوع مربوط به مسائل جريان كارگاهي را به خوانندگان اين پژوهش‌ واگذار مي‌نمائيم. براي مطالعه بيشتر در اين خصوص به منبع [9] مراجعه فرمائيد.
مسئله جريان كارگاهي انعطاف‌پذير
اين مسئله در ادبيات موضوع معمولاً تحت عنوان مسئله جريان كارگاهي با ماشين‌هاي موازي و يا مسئله جريان كارگاهي هيبريدي نيز شناخته مي‌شود. مسئله جريان كارگاهي انعطاف پذير در واقع حالت عمومي مسئله جريان كارگاهي است با اين تفاوت كه m ماشين به صورت موازي تبديل به S مرحله به صورت موازي مي شود که در هر مرحله تعدادي ماشين به صورت موازي موجود است. مرور ادبيات موضوع مربوط به مسائل جريان كارگاهي انعطاف پذير در منبع [11،10] به طور مفصل شرح داده شده است. خلاصه‌اي كارهاي انجام شده با استفاده از روشهاي حل متعدد در ادامه ارائه شده است.
الف ) مسئله جريان كارگاهي انعطاف‌پذير دو مرحله‌اي
آرتاناري و راماسوامي 19[12] اولين بار مسئله جريان كارگاهي انعطاف‌پذير دو مرحله‌اي را معرفي نمودند. آنها حالت خاصي از اين مسئله را كه در مرحله اول و در مرحله دوم بود براي 10 كار با استفاده از روش شاخه و كران حل نمودند. اين مسئله توسط محققان ديگري نيز مورد مطالعه قرار گرفته است. [14،13]
گوپتا20 [13] استفاده از قاعده جانسون را براي تخصيص دادن كار به ترتيب در مرحله‌ اول و بعد از انجام مرحله اول آن در مرحله دوم پيشنهاد داد. بلازويچ و همكاران21 [14] نشان دادند كه مي‌توان اثبات كرد كه استفاده از قاعده جانسون و يا قاعده بزرگترين زمان پردازش به طي منجر مي‌شود كه يا جواب بهينه است و يا نزديك به جواب بهينه مي‌باشد.
ناراسيمهان و پانواكر22 [15] حالتي كه در آن چندين ماشين موازي در مرحله اول و چندين ماشين با سرعت‌هاي متفاوت در مرحله دوم وجود دارند را مورد بررسي قرار دادند. آنها يك الگوريتم ابتكاري ارائه دادند كه در هر تكرار از ميان كارهاي زمان‌بندي نشده، كارهايي كه افزايش مجموع زمان‌هاي بيكاري و انتظار ميان مراحل را مينيمم مي‌كند، يكي را انتخاب مي‌كنند.
وس23 [16] يك متدلوژي براي حل مسئله جريان كارگاهي دو مرحله‌اي با زمان‌هاي آماده‌سازي وابسته ارائه داد كه در تحقيق وي تعداد ماشين‌هاي مرحله دوم يك عدد بود. او از الگوريتم جستجوي ممنوع براي بهبود جواب‌ها استفاده نمود. جاينت و همكاران24 [17] مسئله جريان كارگاهي انعطاف‌پذير دو مرحله‌اي را بصورت يك مسئله برنامه‌ريزي اعداد صحيح مختلط فرمول‌بندي كردند و سه حد پائين براي پيش‌بيني جواب بهينه ارائه دادند. در روش آنها ابتدا توالي به دست آمده و سپس عمل تخصيص به ماشين‌ها صورت مي‌گيرد.
ب ) مسئله جريان كارگاهي انعطاف‌پذير چند مرحله‌اي
مسئله جريان كارگاهي چند مرحله‌اي انعطاف‌پذير شامل تعدادي مرحله‌ است كه در هر مرحله 1 يا بيشتر از 1 ماشين موازي وجود دارند (حداقل يكي از مراحل بايد بيشتر از يك ماشين داشته باشد) از انجائي كه در اكثر حالت‌هاي دنياي واقعي با اينگونه مسائل روبرو هستيم اين مسئله مورد توجه بسياري از محققان قرار گرفته است. با توجه به اينكه اين مسئله جزو مسائل NP-hard در حوزه مسائل زمان‌بندي است تكنيكهاي تقريبي و روشهاي حل فراواني براي اينگونه مسائل ارائه شده است.
براه و هانساكر25 [18] و راجندران و چادهوري26 [19] الگوريتم‌هاي شاخه و كران براي مسئله ارائه دادند. هر دو تحقيق فقط قادر به حل مسائل با سايز كوچك هستند. پورتمن و همكاران27 [20] هم روي همين مسئله مطالعه نمودند. آنها حد پائين ارائه شده توسط براه و هانساكر را بهبود دارند و تعداد شاخه‌هايي كه در درخت جستجو استفاده مي‌شد را كاهش دادند. آنها همچنين از الگوريتم ژنتيك براي بهبود فرايند جستجو استفاده نمودند. نتايج محاسباتي آنها نشان داد كه جواب بهينه‌اي كه از الگوريتم شاخه و كران بدست مي‌آمد در اكثر حالات الگوريتم ژنتيك نيز به آن مي‌رسد. به طوري كه فقط در %3 نتايج با روش شاخه و‌كران اختلاف داشت.
مدل‌هاي زمان‌بندي جريان كارگاهي بدون وقفه
جريان كارگاهي بدون وقفه
در سالهاي اخير علاقه بسياري از محققان به سوي مسائل بدون وقفه معطوف شده است.اين علاقه بيشتر از كاربردهاي اين مسائل در صنعت ناشي مي‌شود. يك مسئله زمان‌بندي بدون وقفه، در محيط‌هاي توليدي اتفاق مي‌افتد كه يك كار از ابتدا تا انتهاي مراحل پردازش بايد بدون وقفه روي ماشين‌ها قرار بگيرد و مراحل پردازش آن پشت سرهم و بدون هيچ‌گونه تاخيري انجام گيرد. به عبارت ديگر تفاوت ميان زمان اتمام هر كار و زمان شروع هر كار در محيط‌هاي توليدي بدون وقفه برابر مجموع زمان‌هاي پردازش مي‌باشد.
در بسياري از صنايع براي مثال در صنايع شيميايي و پتروشيمي، صنايع فولاد، صنعت شيشه و صنايع مرتبط با كاغذ در فرآيند توليد يك محدوديت وجود دارد. هنگامي كه زمان پردازش يك كار شروع مي‌شود فرآيندهاي بعدي بايد بدون تاخير از يك ماشين به ماشين بعد انجام شوند. حتي در صورت لزوم شروع كار در مرحله قبل بايد به اندازه‌اي به تاخير بيفتد كه فرآيندهاي بعدي بدون تاخير آغاز شوند. اين نوع از مسائل به اصطلاح، جريان کارگاهي بدون وقفه28 و يا جريان کارگاهي انتظار صفر29 ناميده مي شوند. يكي از دو دليل اصلي بروز اين گونه مسائل (بدون وقفه) در محيط‌هاي توليدي به ماهيت فرايندها و ماهيت تكنولوژي به كار گرفته شده، باز مي‌گردد. در بعضي از فرايندها، براي جلوگيري از تغييرات نامطلوب در مواد دما يا خصوصيات ديگر مواد (مثلا چسبندگي) نياز به انجام كارها به صورت پشت سرهم و بدون وقفه دارند چون در غير اينصورت به نتيجه دلخواه نخواهيم رسيد. وضعيت‌هاي مشابهي در صنايع گوناگون رخ مي‌دهند مثل صنايع فولاد، پلاستيك و صنايع شيميايي و پتروشيمي. يكي ديگر از مثال‌هاي ملموسي براي توصيف اين وضعيت در صنايع غذايي رخ مي‌دهد. هنگامي كه مواد پروسه پخت را طي نمودند عمليات كنسرو كرن و يا بسته‌بندي اين محصولات بايد بدون وقفه انجام گيرد چرا كه در غير اينصورت مدت زمان مصرف محصولات كاهش خواهد يافت. و سرانجام يك محيط بدون وقفه مي‌تواند در صنايع خدماتي نيز استفاده شود. كاربرد اين مسئله در صنايع خدماتي وقتي توجيه پيدا مي‌كند كه زمان انتظار براي مشتريان و ارائه دهنده خدمات هزينه زيادي را در برداشته باشد. دومين دليل بروز محيط‌هاي بدون وقفه به دليل فقدان وجود انبار ميان ماشين‌ها يا ايستگاه‌هاي كاري است. به غير از مثال‌هاي ذكر شده، با مسئله مورد مطالعه در سيستم‌هاي توليدي به هنگام30 يا سيستم‌هاي كششي نيز رو به رو مي‌شويم. به عبارت ديگر هر گاه جرياني از كارها به طور متوالي و بدون انباشت مياني انجام شوند در آن سيستم مدل كارگاهي بدون وقفه وجود دارد. مسئله جريان كارگاهي بدون وقفه در دهه‌هاي گذشته مورد مطالعه قرار گرفته است. كاربردهاي گوناگون اين مسئله در صنعت، علاقه زيادي را به منظور مدل‌سازي و ارائه روش‌هاي حل در محققان ايجاد نموده است. براي مثال چندين مقاله كه به دهه 70 ميلادي باز مي‌گردند، پيچيدگي محاسباتي اينگونه مسائل را مورد بررسي قراردادند. همچنين در سالهاي اخير اكثر تحقيقات در زمينه روش‌هاي ابتكاري و فرا ابتكاري براي حل اين نوع از مسائل ارائه شده است.
با توجه به اطلاعات و دانش ما يكي از اولين مطالعات صورت گرفته در اين زمينه توسط آقاي گيلمور و گوموري31 [21] انجام شده است. آنها از يك الگوريتم زمان نمايي استفاده كردند و مسئله جريان كارگاهي دو ماشينه بدون وقفه را حل كردند. ردي و رامامورتي32 [22] و ويسمر33 [23] جزو اولين كساني بودند كه مسئله m ماشينه جريان كارگاهي بدون وقفه با تاريخ هدف مينيمم كردن آخرين زمان اتمام كار را حل كردند. ردي و رامامورتي ساهني و چو 34[24] فهميدند كه مسئله جريان كارگاهي دو ماشينه با تابع هدف ماکزيمم زمان اتمام کارها پيچيدگي محاسباتي دارد. پاپا ديميمتريو و كانلاكيس35 [25] تحقيقي بر روي مسئله جريان كارگاهي تك مرحله‌اي با چهار ماشين انجام دادند. نتايج حاصل از تحقيق آنها نشان داد مسئله مورد مطالعه آنها از نظر محاسباتي پيچيده است. راك36 [26] نتيجه مشابهي براي مسئله جريان كارگاهي سه ماشينه بدون وقفه به دست آورد او همچنين نشان داد كه مسئله جريان كارگاهي دو ماشينه بدون وقفه با در نظر گرفتن تابع هدف متوسط زمان در گردش كار37 پيچيدگي محاسباتي دارد.
اسريسكانداراجا و لادت38 [27] مسئله جريان كارگاهي دو مرحله‌اي بدون وقفه با تابع هدف ماکزيمم زمان اتمام کارها در حالتي كه در مرحله اول يک ماشين مركزي و در مرحله دوم دو يا بيشتر از دو ماشين موازي داشته باشيم مورد بررسي قرار دادند و متوجه شدند كه اين مسئله پيچيدگي محاسباتي دارد.
گيلمور و گوموري [21] يك جواب بهينه براي مسئله جريان كارگاهي دو ماشينه بدون وقفه بدست آوردند كه براي رسيدن به آن به مرحله نياز بود. گويال و اسريسکانداراجا39 [28] براي مسئله خاص جريان كارگاهي دو ماشينه بدون وقفه كه زمان پردازش به طور خطي با زمان انتظار كارها قبل از پردازششان روي ماشين دوم رابطه دارد، يك الگوريتم ابتكاري به منظور مينيمم نمودن ماکزيمم زمان اتمام کارها ارائه دادند.
. يكي از اولين تحقيقات صورت گرفته در زمينه جريان كارگاهي بدون انبارهاي مياني توسط لونر40 ‍ [29] انجام شد. وي يك الگوريتم شاخه و كران به منظور مينيمم نمودن ماکزيمم زمان اتمام کارها ارائه داد.ون دمان و بيكر41 [30] همچنين يك روش شاخه و كران به منظور مينيمم نمودن ميانگين زمان در گردش كار براي مسئله جريان كارگاهي بدون انبارهاي مياني ارائه دادند.
براي به دست آوردن يك برنامه‌زماني خوب، مسئله زمان‌بندي جريان كارگاهي بدون وقفه به شكل مسئله فروشنده دوره‌گرد فرموله شده است. برخلاف تحقيقات سنتي صورت گرفته در جريان كارگاهي كه روي استفاده از تكنيكهاي شمارشي – برنامه‌ريزي رياضي و روشهاي ابتكاري براي رسيدن به يك جواب بهينه و يا نزديك بهينه استفاده مي‌كنند، تبديل و فرموله‌بندي كردن مسئله جريان كارگاهي بدون وقفه به مسئله فروشنده دوره گرد از رويكرد متفاوتي استفاده مي‌كند. ابتدا تاخيرهاي زمان پردازش بين كارها و ماشين‌ها را تبديل به ماتريس فاصله براي مسئله TSP مي‌كند. سپس از تكنيكهاي حل معمول كه براي حل اين مسئله به كار مي‌روند، استفاده مي‌شود. محققان مسئله جريان كارگاهي تك پردازنده را به مسئله TSP تعميم دادند. اگرچه آنها همچنين مسئله جريان كارگاهي چند پردازنده را تبديل به چند مسئله TSP كرده و سپس چند مسئله TSP را تبديل به يك مسئله TSP نمودند.
اولين كار انجام شده در تبديل مسئله جريان كارگاهي بدون وقفه به مسئله TSP توسط گيلمورو گوموري [21] در سال 1964 انجام شد. آنها مسئله جريان كارگاهي دو مرحله‌اي تك پردازنده را تبديل به مسئله TSP كردند. آنها دريافتند كه بواسطه بكارگيري الگوريتم شاخه و كران براي مسئله TSP يك جواب بهينه به سرعت براي مسئله جريان كارگاهي بدون وقفه به دست مي‌آيد. اين روش مورد توجه بسيراي از محققان قرار گرفته است. مشابه وضعيت الگوريتم جانسون در مسائل عمومي جريان كارگاهي روش گيلمور و گوموري بارها مورد استفاده محققان در تركيب با روشهاي ابتكاري براي بهبود جواب مينيمم نمئدن ماکزيمم زمان اتمام کارها و يا ساير توابع هدف قرار گرفته است. گويال و ناسريسكانداراجا [28] استراتژي تقسيم و غلبه42 را به كار گرفتند. آنها مسئله جريان كارگاهي m ماشينه را به مسئله جريان كارگاهي m-1 ماشينه كاهش داده و سپس به منظور پيدا كردن جواب خوب از روش گيلمورو گوموري استفاده نمودند. اين تبديل امكان استفاده محدوده وسيعي از تكنيهاي حل امكان‌پذير براي مسئله جريان كارگاهي بدون وقفه را فراهم آورد. اگرچه مسئله هنوز پيچيدگي محاسباتي خود را حفظ كرد.
مسئله TSP معمولاً توسط يك ماتريس فاصله نمايش داده مي‌شود كه حاوي فاصله سفر ميان شهرهاي موجود است.
ايگنيزيو وكاوالير43 [31] مسئله فروشنده دوره گردن به اين صورت تشريح كردند: يك فروشنده كه از شهر خود شروع به حركت مي‌كند و بايد از تمامي شهرهاي موجود در ليست عبور كند و در انتها به شهر خود بازگردد. هدف در اين مسئله مينيمم كردن مجموع فواصل طي شده توسط فروشنده دوره گرد است.
گوپتا44 [32] يك مدل بر اساس مدل ردي و رامامورتي توسعه داد. او يك الگوريتم ابتكاري ارائه داد كه عملكرد آن بهتر از الگوريتم ويسمر بود. بر اساس دانش ناشي از تحقيقات صورت گرفته، بعضي از محققان شروع به توسعه الگوريتم‌هاي جديد براي مسئله جريان كارگاهي بدون وقفه به خوبي تحقيقات صورت گرفته در مورد TSP نمونه آنها همچنين از تكنيكهاي الگوريتميك و برنامه‌ريزي رياضي براي ارزيابي كردن الگوريتم‌هايشان، استفاده كردند. بوني و گاندري45 [33] روش ابتكاري به نام جور كردن شيبدار هم بر اساس شكل كارها در برنامه توسعه دادند. الگوريتم شكل‌هايي با كشيدن خط ميان شروع و پايان عمليات‌ها از يك ماشين به ماشين ديگر ايجاد مي‌كرد. الگوريتم جور كردن شيدار تلاش كرد كه شكل دوكار متوالي را متناسب كند. آنها همچنين از فرمولاسيون TSP بر اساس زمان شناوري بين كارها استفاده كردند و دو روش ارائه شده خود را با دو روش ابتكاري رايج مقايسه كردند و نشان دادند روش جور كردن شيبدار46 عملكرد بهتري دارد. كينگ و اسپاچيس47 [34] نشان دادند كه الگوريتم‌هايي كه در محيط بدون وقفه عملكرد خوبي ندارند لزوماً عملكرد مناسبي در محيط انبارهاي مياني نامحدود از خود نشان نمي‌دهند.
كالاهان48 [35] يك تحقيق در صنعت فولاد روي فرآيندهاي بدون وقفه انجام دارد. وي يك مدل صف براي آناليز چندين مسئله استفاده نمود. در ادامه آزمون‌هاي محاسباتي را براي بررسي پيشنهاداتش به كار گرفت سالوادور49 [36] يك الگوريتم را كه نشأت گرفته شده از يك محيط توليدي نايلون بود توسعه داد.هدف وي مينيمم كردن ماكزيمم زمان انجام كارها براي يك مجموعه شامل n كار با تعيين توالي بهينه و تعيين زمان شروع كارها براي توالي بهينه بود. رويكرد به كار گرفته شده توسط وي برنامه‌ريزي پويا بود. وي از برنامه‌ريزي پويا براي پيدا كردن حدود پائين براي استفاده در روش شاخه و كران كمك گرفت. استفاده از نتايج به دست آمده توسط كارخانه حداكثر ظرفيت توليد كارخانه را به ميزان قابل قبولي افزايش داد.
جريان کارگاهي انعطاف پذير بدون وقفه
در جريان كارگاهي با ماشين‌هاي موازي، هر مرحله داراي ماشين يكسان است.که لزوما تعداد ماشين ها در تمامي مراحل يکسان نيست.
كوريان50 [37] يك حالت خاص در نظر گرفت كه در آن و بود هدف وي مينيمم كردن ماكزيمم زمان اتمام كارها بود. وي يك بدترين عملكرد مرز51 توسعه داد. همچنين نشان‌ داد اگر از ليست LPT استفاده شود، حد به بهبود مي‌يابد. نتايج حاصل از پژوهش كوريان و ركلايتيس52 [38] نشان داد كه اكثر الگوريتم‌هاي ابتكاري كالا تقريباً مشابه توالي توليد شده توسط LPT هستند كه با استفاده از يك جستجو در همسايگي تكميل مي‌شود. كوريان و ركلايتيس براي يك مسئله جريان كارگاهي دو مرحله‌اي انعطاف‌پذير بدون وقفه دو الگوريتم ابتكاري ارائه دادند.
رامودين و راتليف53 [39] مسئله جريان كارگاهي دو مرحله‌اي انعطاف‌‌پذير بدون وقفه ‌را با تابع هدف ماكزيمم كردن مجموع وزني سفارشات مشتريان در طول 8 ساعت شيفيت روزانه حل كردند.
مسئله حل شده توسط آنها را مي‌توان به صورت نشان داد. آنها مسئله را بصورت يك برنامه‌رياضي فرموله كردند و براي تبديل مسئله به چند زير سماله از آزادسازي لاگرانژين استفاده نمودند. بعضي از جواب‌هاي نشدني توسط الگوريتم جستجوي محلي حذف مي‌شوند. سپس توسط يك كارشناس خبره و به صورت تعاملي الگوريتم به يك جواب مناسب هدايت مي‌شود.
اسريسكانداراجا [40] از يك بدترين حد تنگ و با استفاده از يك توالي دلخواه براي مسئله استفاده كرد. در اين الگوريتم كارها به ترتيبي كه بصورت تصادفي توليد شده بودند، زمان بندي مي‌شوند. اگر كارهاي سفارشي داده شده به صورت غير صعودي (براي زمان پردازش مرحله دوم) مرتب شوند در اينصورت به جواب‌هاي بهتري خواهيم رسيد. فريبرز جولاي و همکاران [41] يک مسئله جريان کارگاهي چند مرحله اي بدون وقفه را با در نظر گرفتن محدوديت اتمام کارها در يک زمان از پيش تعيين شده يک مدل برنامه ريزي عدد صحيح مختلط خطي را پيشنهاد داده و مدل پيشنهادي با الگوريتم ژنتيک مقايسه شد. در مسئله مورد مطالعه آنها با توجه به محدوديت در نظر گرفته شده ممکن است بعضي از کارها رد شوند.تابع هدف در نظر گرفته شده در اين تحقيق تابع هدف در نظر گرفته شده، ماکزيمم سود حاصله مي باشد.
جريان كارگاهي انعطاف‌پذير دو مرحله‌اي بدون وقفه
گوپتا و همکاران [42] يک طبقه بندي جامع از پيچيدگي مسئله جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه همراه با زمان هاي آماده سازي و تغيير مکان به منظور مينيمم نمودن مجموع زمان هاي اتمام کار ارائه دادند ليو ژيژين54 [43] و همکاران يک مسئله جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه با اين شرايط که يک ماشين در مرحله اول و تعدادي ماشين که تعداد انها بزرگتر از يک است در مرحله دوم قرار دارند. يک الگوريتم ابتکاري با عنوان55 LD طراحي شده و عملکرد بدترين حد آن مورد بررسي قرار گرفت. الگوريتم پيشنهادي انها پيچيدگي محاسباتي بسيار کمي را داراست و اجراي ان ساده مي باشد بنابراين با توجه به نتايج حاصله انها پيشنهاد دادند که با توجه به خصوصيات الگوريتم پيشنهادي، به کارگيري اين الگوريتم در کاربردهاي دنياي واقعي مي تواند سودمند باشد. ژونلين چانگ و همکاران56 [44] روي مسئله جريان کارگاهي هيبريدي دو مرحله اي بدون وقفه را با در نظر گرفتن زمان هاي راه اندازي و انتقال به صورت مجزا مطالعه نمودند.با توجه به NP-complete بودن مسئله مورد مطالعه و از آنجائي که هيچ الگوريتم شناخته شده اي که با زمان نمايي قادر به حل اين مسئله باشد ، وجود نداشت، آنها از يک رويکرد حل تقريبي براي اين مسئله استفاده نموده و دو الگوريتم ابتکاري براي حل اين مسئله پيشنهاد نمودند.همچنين آنها براي مقايسه رويکرد پيشنهادي خود، جواب هاي به دست آمده را با حد پائين توسعه داده شده، مقايسه نمودند.نتايج حاصله نشان داد که اين الگوريتم به طور کارايي قابليت حل مسائل را با پيچيدگي محاسباتي کم داراست.جينکسينگ ژي و ژيجون وانگ57[45] روي مسئله جريان کارگاهي انعطاف پذير دو مرحله اي بدون وقفه با تابع هدف مينيمم نمودن ماکزيمم زمان اتمام کارها مطالعه نمودند. آنها يک الگوريتم ابتکاري به نام 58MDA براي حل اين مسئله پيشنهاد داده و الگوريتم پيشنهادي خودشان را با الگوريتم هاي ارائه شده در پيشينه تحقيق مقايسه نمودند. نتايج حاصل از مقايسه نشان داد الگوريتم MDA در اغلب موارد جواب بهتري نسبت به ساير الگوريتم ها به دست مي آورد. آخرين پژوهش انجام شده در اين حوزه توسط رونگ هوا هانگ و همکاران59 [46] انجام شده است. آنها مسئله جريان کارگاهي انعطاف پذير دو مرحله اي انعطاف پذير بدون وقفه را با در نظر گرفتن زمان راه اندازي به صورت مجزا و با تابع هدف مينيمم نمودن مجموع زمان اتمام کارها برررسي نمودند. انها يک مدل برنامه ريزي عدد صحيح مختلط غير خطي براي حل اين مساله ارائه دادند. همچنين الگوريتم بهينه سازي کلوني مورچگان براي اين مسئله پيشنهاد شد و براي سايز هاي مختلف اين رويکردها با يکديگر مقايسه شد.نتايج به دست آمده برتري در زمان حل،نيرومندي و کيفيت جواب به دست آمده براي الگوريتم بهينه سازي کلوني مورچگان را نشان داد. برای مطالعه بیشتر در خصوص ادبیات موضوع مسائل بدون وقفه توصیه می شود به [47] مراجعه شود.
پيش بيني ماکزيمم زمان اتمام کارها
تخصيص موعد تحويل يکي از مهمترين فعاليت هاي مراکز کنترل کارخانه است. معيار هاي مرتبط با موعد تحويل از کيفيت موعد تحويل تخصيص يافته تاثير مي پذيرند. در زمينه تخصيص موعد تحويل در برخي حوزه ها مطالعاتي صورت گرفته است ولي با توجه به اهميت اين موضوع، تعدد و کيفيت اين کارها با اهميت اين موضوع سنخيت ندارد. در مسئله جريان کارگاهي بدون وقفه چندين ترکيب از توالي کارها وتخصيص ماشين ها وجود دارد. از اينرو پيش بيني زمان اتمام کارها در اينگونه مسائل دشوار است. پيشبيني ماکزيمم زمان اتمام کارها در ادبيات موضوع تخصيص موعد تحويل مورد توجه قرار گرفته است. [48]
يکي از محبوب ترين رويکرد هاي استفاده شده در تخمين ماکزيمم زمان اتمام کارها، استفاده از شبکه عصبي است. سابونچوگلو60 [49] يک مرور بر ادبيات موضوع و تحقيقات صورت گرفته با استفاده از شبکه عصبي ارائه داد. سابونچوگلو و گورگان61 [50] شبکه عصبي را با يک رويکرد الگوريتميک به منظور حل يک مسئله تک ماشينه با تابع هدف مينيمم نمودن ميانگين تاخير، ترکيب نمودند. چن و موراکي62 [51] نيز يک شبکه استاندارد پيش بازخور براي زمانبندي مجدد آنلاين ارائه دادند. فيليپوم و همکاران63 [52] رويکرد رگرسيون غير خطي را با شبکه عصبي در تخصيص موعد هاي تحويل مسائل زمان بندي مقايسه نمودند.
مساله چند هدفه جريان کارگاهي بدون وقفه
جريان كارگاهي بدون وقفه
اگرچه الگوريتمهاي فراابتکاري فراواني براي حل مسائل چند هدفه از اواخر دهه 80 تا کنون ارائه شده است. ولي تعداد بسيار اندکي از آنها محدوديت بدون وقفه بودن را در مسائل چند هدفه لحاظ کرده است. با توجه به پژوهش هاي در دسترس، الله وردي و الدوايسان64 [53] اولين کساني بودند که دو الگوريتم شبيه سازي تبريد هيبريدي و الگوريتم ژنتيک هيبريدي را با توابع هدف مينيمم نمودن ماکزيمم زمان اتمام کارها و مينيمم نمودن ماکزيمم ديرشدگي65 براي مساله جريان کارگاهي بدون وقفه ارائه دادند. توکلي مقدم و همکاران [54] يک الگوريتم سيستم ايمني هيبريدي به منظور پيدا کردن جواب هاي پارتو براي مساله جريان کارگاهي بدون وقفه با توابع هدف مجموع وزني متوسط زمان اتمام کارها و مجموع وزني ميانگين تاخيرها ارائه دادند.
جريان كارگاهي انعطاف پذير دو مرحله اي بدون وقفه
در حوزه مسائل جريان کارگاهي انعطاف پذير بدون وقفه تاکنون هيچ پژوهشي صورت نگرفته است.
جمع بندي
در اين فصل، ابتدا پيشينه تحقيقات صورت گرفته براي مسائل تک معياره در حوزه جريان کارگاهي، جريان کارگاهي انعطاف پذير و جريان کارگاهي انعطاف پذير دو مرحله اي که فاقد محدوديت بدون وقفه بودن هستند، مورد مطالعه قرار داديم. سپس تحقيقات انجام گرفته در زمينهي مسائل مرتبط با جريان کارگاهي بدون وقفه، جريان کارگاهي انعطاف پذير بدون وقفه و جريان



قیمت: تومان

دسته بندی : مقاله و پایان نامه

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