2-4-3. مجموع زمان تکمیل کارها Cj16
2-4-4. مجموع وزنی زمان تکمیل کارها WjCj16
2-4-5. مجموع زمان دیر کرد کارها Tj16
2-4-6. مجموع وزنی زمان دیرکرد کارها WjTj16
2-4-7. مجموع تعداد کارهای با تاخیر Uj17
2-4-8. مجموع وزنی تعداد کارهای با تاخیر WjUj17
2-4-9. مجموع زمانهای زودکرد و دیرکرد کارها Ej+Tj17
2-4-10. مجموع وزنی زمانهای زودکرد و دیرکرد کارها WjEj+W’jTj17
2-5. پیشینه تحقیق17
2-6. ماشینهای موازی نامرتبط18
2-7. دوبارهکاری21
2-8. زمان نصب وابسته به توالی کارها24
2-9. دسترسی محدود به ماشینها27
2-10. جمع بندی29
فصل سوم30
مدل ریاضی پیشنهادی30
3-1. مقدمه31
3-2. تعریف مسئله31
3-2. مفروضات مسئله32
3-3. مدل ریاضی پیشنهادی33
3-3-1. اندیسها و پارامترهای ورودی به مدل34
3-3-2. متغیرهای تصمیمگیری34
3-3-3. تابع هدف35
3-3-4. محدودیتها36
3-4. اعتبار سنجی مدل40
3-5. پیچیدگی مسئله43
3-6. الگوریتم ژنتیک46
3-6-1. تاریخچه الگوریتم ژنتیک47
3-6-2. واژگان ژنتیک48
3-6-3. ساختار الگوریتم ژنتیک49
3-6-4. کدگذاری50
3-6-5. ایجاد جمعیت اولیه51
3-6-6. اعمال ژنتیک52
3-6-6-1. عملگرهای تقاطعی52

در این سایت فقط تکه هایی از این مطلب با شماره بندی انتهای صفحه درج می شود که ممکن است هنگام انتقال از فایل ورد به داخل سایت کلمات به هم بریزد یا شکل ها درج نشود

شما می توانید تکه های دیگری از این مطلب را با جستجو در همین سایت بخوانید

ولی برای دانلود فایل اصلی با فرمت ورد حاوی تمامی قسمت ها با منابع کامل

اینجا کلیک کنید

3-6-6-1-1. یک نقطه برش53
3-6-6-1-2. دو نقطه برش54
3-6-6-2. عملگرهای جهشی54
3-6-6-2-1. جابجایی55
3-6-6-2-2. وارونگی56
3-6-6-2-3. الحاق یا جاسازی56
3-6-7. عمل تحول57
3-6-7-1. فضای نمونه گیری57
3-6-7-2. فضای نمونه گیری عادی57
3-6-7-3. مکانیسم نمونه گیری57
3-6-7-4. احتمال انتخاب58
3-6-8. تابع برازش59
3-6-9 . استراتژی برخورد با محدودیت59
3-6-9-1. استراتژی اصلاح عملگرهای ژنتیک60
3-6-9-2. استراتژی ردی60
3-6-9-3. استراتژی اصلاحی60
3-6-9-4. استراتژی جریمه ای60
3-6-10. معیار توقف61
3-7. الگوریتم زنبور عسل62
3-7-1. مراحل اجرای الگوریتم63
3-7-2. پارامتر های الگوریتم64
3-7-3. فلوچارت الگوریتم زنبور عسل64
3-7-4. شرح مراحل اجرای الگوریتم65
3-8. جمعبندی66
فصل چهارم67
نتایج محاسباتی و تحلیل آن67
4-1.مقدمه68
4-2. پیادهسازی الگوریتم ژنتیک68
4-2-1. ساختار کروموزوم69
4-2-2. جمعیت اولیه70
4-2-3. ارزیابی برازندگی تابع هدف71
4-2-4. استراتژی انتخاب71
4-2-5. اپراتورهای ژنتیک73
4-2-6. همگرایی الگوریتم ژنتیک75
4 -2-7. معیار توقف75
4-3. پیادهسازی الگوریتم زنبور عسل( شماره یک)76
4-3-1. مراحل اجرای الگوریتم زنبورعسل (شماره یک)76
4-3-2. پارامترهای الگوریتم زنبورعسل (شماره یک)77
4-3-3. روابط حاکم بر مقادیر پارامترها در الگوریتم زنبورعسل (شماره یک)77
4-4. پیادهسازی الگوریتم زنبور عسل(شماره دو)78
4-4-1. مراحل اجرای الگوریتم زنبورعسل (شماره دو)78
4-4-2. پارامترهای الگوریتم زنبورعسل (شماره دو)79
4-5. مجموعه دادهها81
4-6. تنظیم پارامترهای کنترلی الگوریتمها81
4-7. طراحی آزمایشات چندعاملی برای مسائل با ابعاد متوسط84
4-7-1.تحلیل نتایج آماری88
4-8. طراحی آزمایشات چندعاملی برای مسائل باابعاد بزرگ92
4-8-1.تحلیل نتایج آماری96
4-9. نتایج محاسباتی99
4-10. جمعبندی108
فصل پنجم109
نتیجه گیری و پیشنهادات109
5-1. مقدمه110
5-2. نتیجه گیری110
5-3. پیشنهادات آتی111
5-3-1. پیشنهادات در زمینه ماهیت مسئله طرح شده در تحقیق111
5-3-2. پیشنهادات در زمینه روش حل مسئله112
فهرست منابع113
پیوست119
جدول 4-1. مقادیر دادههای ورودی به مسائل آزمایشی81
جدول 4-2. پارامترهای کنترلی الگوریتم ژنتیک83
جدول 4-3. پارامترهای کنترلی الگوریتم زنبور شماره یک83
جدول 4-4. پارامترهای کنترلی الگوریتم زنبور شماره دو83
جدول 4-5. فاکتورها و سطوح آنها در الگوریتم زنبور شماره یک در ابعاد متوسط84
جدول 4-6. فاکتورها و سطوح آنها در الگوریتم زنبور شماره دو در ابعاد متوسط84
جدول 4-7. فاکتورها و سطوح آنها در الگوریتم ژنتیک در ابعاد متوسط84
جدول 4-8 . ترکیب فاکتورها و سطوح پاسخ مربوط به الگوریتم زنبور1 در مسائل با ابعاد متوسط85
جدول4-9 . ضرایب همبستگی تخمینی مدل برای نسبتهای SN، الگوریتم زنبور1، ابعاد متوسط86
جدول4-10. آنالیز واریانس برای نسبتهای SN، الگوریتم زنبور1، ابعاد متوسط86
جدول 4-11. ضرایب همبستگی تخمینی مدل برای میانگین پاسخها، الگوریتم زنبور1، ابعاد متوسط87
جدول 4-12. آنالیز واریانس برای میانگین پاسخها، الگوریتم زنبور1، ابعاد متوسط87
جدول 4-13. جدول پاسخ نسبتهای SN، الگوریتم زنبور1، ابعاد متوسط88
جدول4-14. جدول پاسخ میانگینها، الگوریتم زنبور1، ابعاد متوسط88
جدول 4-15. مقادیر پارامترهای کنترلی الگوریتم زنبور 1، ابعاد متوسط90
جدول 4-16.مقادیر پارامترهای کنترلی الگوریتم زنبور 2، ابعاد متوسط91
جدول 4-17. مقادیر پارامترهای کنترلی الگوریتم ژنتیک، ابعاد متوسط91
جدول 4-18. فاکتورها و سطوح آنها در الگوریتم زنبور شماره یک برای ابعاد بزرگ92
جدول 4-19. فاکتورها و سطوح آنها در الگوریتم زنبور شماره دو برای ابعاد بزرگ92
جدول 4-20. فاکتورها و سطوح آنها در الگوریتم ژنتیک برای ابعاد بزرگ92
جدول 4-21. ترکیب فاکتورها و سطوح پاسخ مربوط به الگوریتم زنبور1 در مسائل با ابعاد بزرگ93
جدول 4-22 . ضرایب همبستگی تخمینی مدل برای نسبتهای SN، الگوریتم زنبور1، ابعاد بزرگ94
جدول 4-23 . آنالیز واریانس برای نسبتهای SN، الگوریتم زنبور1، ابعاد بزرگ94
جدول 4-24. ضرایب همبستگی تخمینی مدل برای میانگین پاسخها، الگوریتم زنبور1، ابعاد بزرگ95
جدول 4-25. آنالیز واریانس برای میانگین پاسخها، الگوریتم زنبور1، ابعاد بزرگ95
جدول 4-26. جدول پاسخ نسبتهای SN، الگوریتم زنبور1، ابعاد بزرگ96
جدول4-27. جدول پاسخ میانگینها، الگوریتم زنبور1، ابعاد بزرگ96
جدول4-28. مقادیر پارامترهای کنترلی الگوریتم زنبور1، ابعاد بزرگ98
جدول4-29. مقادیر پارامترهای کنترلی الگوریتم زنبور2، ابعاد بزرگ98
جدول4-30. مقادیر پارامترهای کنترلی الگوریتم ژنتیک، ابعاد بزرگ98
جدول4-31. نتایج محاسباتی حاصل از حل مسائل با ابعاد کوچک100
جدول4-32. زمانهای محاسباتی و میانگین جوابهای حاصل از حل مسائل با ابعاد کوچک101
جدول4-33. نتایج محاسباتی حاصل از حل مسائل با ابعاد متوسط103
جدول4-34. زمانهای محاسباتی و میانگین جوابهای حاصل از حل مسائل با ابعاد متوسط103
جدول4-35. نتایج محاسباتی حاصل از حل مسائل با ابعاد بزرگ105
جدول4-36. زمانهای محاسباتی و میانگین جوابهای حاصل از حل مسائل با ابعاد بزرگ105
جدول4-37. مقادیر RPD برای الگوریتمهای ژنتیک، رنبور1 و زنبور2107
شکل3-1. حل گرافیکی مسئله (m=2,n=3,L=3) در شرایط فعال نبودن محدودیت دسترسی به ماشینها40
شکل3-2. حل گرافیکی مسئله (m=2,n=3,L=3) در شرایط اعمال محدودیت دسترسی به ماشینها41
شکل3-3. حل گرافیکی مسئله (m=2,n=3,L=3) در شرایط افزایش در زمان نصب کار شماره 342
شکل3-4. سلسله مراتب پیچیدگی محیطهای کارگاهی در مسائل زمانبندی ]4[44
شکل 3-5. سلسله مراتب پیچیدگی جزئیات نحوه پردازش و محدودیتها در مسائل زمانبندی ]4[44
شکل 3-6. سلسله مراتب پیچیدگی توابع هدف در مسائل زمانبندی ]4[44
شکل 3-7. سلسله مراتب پیچیدگی تعدادی از مسائل زمانبندی با تابع هدف Makespan ]4[45
شکل 3-8 .مقایسه فضاهای ژنوتیپ و فنوتیپ48
شکل 3-9. فضای موجه، ناموجه و غیرقانونی51
شکل3-10 . نحوه عملکرد اپراتور تقاطع یک نقطه برش53
شکل3-11. اپراتور تقاطع تک نقطهای54
شکل 4-1. رویه کلی الگوریتم ژنتیک68
شکل4-2. روش نمایش جواب70
شکل 4-3. عملیات تقاطع74

شکل 4-4. پاسخ میانگینها، الگوریتم زنبور1، ابعاد متوسط89
شکل 4-5. میانگین نسبت SN، الگوریتم زنبور1، ابعاد متوسط90
شکل 4-6 . پاسخ میانگینها، الگوریتم زنبور1 ، ابعاد بزرگ97
شکل 4-7 . میانگین نسبت SN، الگوریتم زنبور 1، ابعاد بزرگ97
شکل 4-8. میانگین زمان محاسباتی الگوریتمها در ابعاد کوچک (2ماشین)102
شکل 4-9. میانگین زمان محاسباتی الگوریتمها در ابعاد متوسط104
شکل 4-10. میانگین زمان محاسباتی الگوریتمها در ابعاد بزرگ106
شکل 4-11. نمودار LSD در سطح اطمینان 95% برای معیار RPD107
فصل اول
کلیات تحقیق
1-1. مقدمه
مسائل زمانبندی1 یکی از مهمترین مسائل دنیای امروز میباشند که تاثیر شگرفی در افزایش بهرهوری سیستمهای تولیدی و خدماتی دارند. زمانبندی در عمل بهمعنای تخصیص منابع محدود به فعالیتهایی است که به آن منبع نیاز دارند و در واقع نوعی فعالیت تصمیمگیری است که با هدف بهینهسازی یک و یا چند معیار انجام میگیرد. باید به این نکته توجه داشت که در دنیای رقابتی کنونی، برای موسسهها، داشتن بهترین توالی انجام عملیات و زمانبندی مناسب فعالیتها یک نیاز اساسی به منظور بقاء تعریف میشود و بهعنوان یک فرآیند تصمیمگیری، مبنای کار بسیاری از صنایع تولیدی و خدماتی محسوب میشود. به بیان بهتر، زمانبندی را میتوان تخصیص منابع محدود در طول زمان بهمنظور اجرای مجموعهای از وظایف تعریف کرد. در دنیای امروز، زمان همواره یک محدودیت اساسی بوده است. بنابراین، زمانبندی صحیح فعالیتها بهمنظور حداقل کردن این منبع با توجه به هزینههای تولیدی و خدماتی در واحد زمان، امری ضروری به نظر میرسد.
با پیشرفت علم و بهدنبال آن توسعه و شکوفایی صنایع تولیدی و خدماتی، نقش منابع و نحوه تخصیص آنها از اهمیت دو چندانی برخوردار شده است. امروزه منابع در دسترس مانند نیروی انسانی، ماشینآلات، مواد اولیه و … به عنوان منابع بحرانی در تولید و فعالیتهای خدماتی در نظر گرفته میشوند و زمانبندی و تخصیص به موقع و مناسب این منابع منجر به ارتقاء کارایی، بهرهوری و در نهایت سودآوری بیشتر میشود. از آنجا که خواستگاه بسیاری از مسائل زمانبندی و توالی عملیات محیط های صنعتی میباشد، در بیان بسیاری از مفاهیم زمانبندی از واژههای بکار رفته در صنعت استفاده میشود. به عنوان مثال، در مباحث زمانبندی و توالی عملیات از منابع با عنوان ماشین2 و از فعالیتها با عنوان کار3 یاد میشود به نحوی که کارها اغلب بوسیله ماشینها در ایستگاههای مختلف کاری با توالی مشخص پردازش میشوند.
در مسائل زمانبندی، هدف از یافتن توالی انجام کارها میتواند متفاوت باشد. تعدادی از اهداف مورد استفاده در مسائل زمانبندی عبارتند از : کمینهسازی بیشترین زمان تکمیل کارها، کمینهسازی مجموع زمان تکمیل کارها، کمینهسازی بیشترین زمان دیرکرد و کمینهسازی تعداد کارهایی که دیرکرد دارند. همچنین بر حسب شرایط حاکم بر محیط مورد مطالعه، محدودیتهای گوناگونی در مسئله لحاظ میشود. تعدادی از محدودیتهای حاکم بر مسائل زمانبندی عبارتند از : زمانهای نصب وابسته به توالی ، محدودیت دسترسی به ماشینها، زمانهای دسترسی به کار، برش در کارها، خرابی ماشینها و محدودیت در اندازه صف کارها که مورد آخر در سیستمهای جریان کارگاهی می تواند لحاظ شود . در ابتدای فصل دوم، مسائل زمانبندی به تفکیک محیطهای کارگاهی، محدودیتهای پردازش و توابع هدف بصورت مختصر معرفی میشوند. یک مسئله زمانبندی بصورت یک مسئله بهینهسازی بیان میشود که با توجه به محدودیتهای موجود، به دنبال ارضاء کردن هدف (اهداف) مورد نظر میباشد.
در مباحث زمانبندی، بررسی مدلهای تک ماشینه به علت سادگی و به دلیل اینکه حالت خاصی از سایر مدلها میباشد از اهمیت بالایی برخوردار است. در مقابل، نظریه زمانبندی سه نوع اساسی از مدلهای چند ماشینی را پوشش میدهد: سیستمهای موازی، سیستمهای جریان کارگاهی و سیستمهای تولید کارگاهی. در سیستم ماشینهای موازی همانند مدلهای تک ماشینی، هر یک از کارها با انجام یک عملیات بر روی یکی از ماشینهای موازی موجود پردازش میشوند اما در سیستمهای جریان کارگاهی و ترکیبی ساختار مسائل پیچیدهتر است.
در ادامه به تعریف مسئله مورد بحث این تحقیق و مفروضات آن پرداخته میشود. در پایان اهداف و ضرورت تحقیق بیان میشود.
1-2. تعریف مسئله
مسئله زمانبندی ماشینهای موازی نامرتبط4، بهعنوان دسته مهمی از مسائل زمانبندی که دارای اهمیت فراوان از نقطه نظر تئوری و تجربی است شناخته میشود. مسائل ماشینهای موازی نامرتبط حالت عمومیت یافته مسائل تک ماشینه و مسائل کلاسیک ماشینهای موازی و حالت خاصی از مسائل ماشینهای متوالی منعطف5 محسوب میشوند. در مسائل کلاسیک ماشینهای موازی، مجموعهای از کارهای مستقل وجود دارد که هر کدام از آنها بر روی یکی از ماشینهای موازی یکسان موجود پردازش میشود و زمان پردازش کار نوع j بر روی تمامی ماشینها یکسان است ولی در حالت نامرتبط بودن ماشینها، زمان پردازش کارها بر روی ماشینها نه تنها به نوع کار بلکه به نوع ماشین نیز وابسته است و رابطه مشخصی بین زمانهای پردازش کارها بر روی ماشینهای مختلف وجود ندارد.
در بسیاری از تحقیقات و مقالات ارائه شده در زمینه مسائل زمانبندی فرض بر این است که محصولات تولیدی توسط ماشینها دارای کیفیت قابل قبول هستند. ولی در دنیای واقعی این فرض چندان منطبق بر شرایط تولیدی نمیباشد و تولید اقلام معیوب به دلایل متعدد امری اجتناب ناپذیر است. از جمله این دلایل عبارتند از:
کارا نبودن سیستم تولیدی
از رده خارج بودن ماشینهای تولید
نداشتن یک سیستم تعمیرات و نگهداری مناسب و کارا
خطاهای انسانی
شرایط غیر قابل پیش بینی در تولید و …
در مسئله زمانبندی ماشینهای موازی نامرتبط از آنجایی که ممکن است دلیل نامرتبط بودن ماشینها، تفاوت میان عملیات قابل پردازش توسط آنها باشد و هر ماشین لزوما قادر به پردازش هر یک از کارهای موجود در مجموعه کارها نباشد، بنابراین دور از منطق نیست که محدودیت دسترسی به ماشینها6 در مسئله مورد بررسی در نظر گرفته شود. این محدودیت تضمین میکند که هر کار تنها توسط زیرمجموعهای از ماشینها قابل پردازش باشد و اصطلاحا پردازش کارها با دسترسی محدود به ماشینها صورت میپذیرد.
در بسیاری از مسائل زمانبندی فرض بر این بوده است که تمام کارها در ابتدای افق زمانبندی در دسترس هستند. واضح است که در دنیای واقعی لزوما این موضوع صحیح نیست و ممکن است کارها به تدریج وارد سیستم شوند و از ابتدا در دسترس نباشند. در نتیجه محدودیت زمان دسترسی به کارها7 در مدل پیشنهادی لحاظ خواهد شد.
مسائل زمانبندی غالبا به محیطهای تولیدی و خدماتی میپردازند که در آنها زمان نصب ماشین نادیده گرفته میشود و یا به عنوان بخشی از زمان پردازش کارها تلقی میشود. این نوع محیطهای تولیدی و یا خدماتی با این فرض مدلسازی میشوند که زمانهای نصب در مقایسه با زمانهای پردازش کوچک هستند، بنابراین میتوان آنها را نادیده گرفت و یا اینکه زمانهای نصب مستقل از توالی پردازش کارها بر روی ماشینها هستند، در نتیجه میتوان آنها را به زمان پردازش اضافه نمود. با این وجود در بسیاری از محیطهای صنعتی یک زمان نصب وابسته به توالی8 هنگام تعویض کارها بر روی ماشینها به وقوع میپیوندد ]3[. در این شرایط زمان نصب بهعنوان بخشی مجزا از زمان پردازش در نظر گرفته میشود که مقدار آن علاوه بر نوع کاری که بر روی ماشین پردازش خواهد شد، به نوع کار قبلی که بر روی آن ماشین پردازش شده است نیز بستگی دارد. بهعنوان مثال، در سوراخکاری صفحات فلزی، اگر دو پردازش متوالی از دو الگوی متفاوت پیروی کنند، آنگاه برای انجام پردازش بعدی باید زمانی صرف شود و تغییرات لازم به منظور آمادهسازی ماشین صورت پذیرد.
یکی از پرکاربرد ترین توابع هدف در مسائل بهینهسازی ماشینهای موازی، کمینهکردن بیشترین زمان تکمیل کارها9 میباشد. چرا که رسیدن به این هدف سبب میشود کارها تا حد ممکن با یکنواختی بیشتری بین ماشینها توزیع شوند و به نحوی از ظرفیت کاری تمام ماشینها تا حد مطلوب استفاده شود و در نتیجه از تجمع کارها بر روی یک یا تعدادی از ماشینها جلوگیری بهعمل میآورد. از این رو معیار بیشترین زمان تکمیل کارها به عنوان معیار بهینهسازی در مدل پیشنهادی مورد استفاده قرار گرفته است.
در این تحقیق، مسئله زمانبندی ماشینهای موازی نامرتبط با فرض وجود امکان دوبارهکاری10 اقلام معیوب به همراه محدودیتهای زمان دسترسی به کارها، زمان نصب وابسته به توالی کارها و وابسته به نوع ماشین و دسترسی محدود به ماشینها با هدف کمینهسازی بیشترین زمان تکمیل کارها معرفی و مورد بررسی قرار میگیرد. در ادامه، برای مسئله یاد شده یک مدل برنامه ریزی عدد صحیح ارئه میشود. همچنین از الگوریتمهای فراابتکاری شامل الگوریتم ژنتیک11 و الگوریتم زنبور عسل12 برای حل آن استفاده میشود.
از جمله کاربردهای مدل پیشنهادی در تحقیق پیش رو را میتوان در یک سیستم خدماتی همانند بانک مشاهده نمود. در یک بانک، چند اپراتور به صورت موازی وجود دارند که هر کدام مسئول رسیدگی به بخشی از امور بانکی هستند. بر فرض مثال اپراتور اول وظیفه بازگشایی حساب، باز گشایی ال سی، صدور انواع حوالههای بانکی و انجام امور مرتبط با انتقال وجه را بهعهده دارد و اپراتور دوم به سایر امور بانکی نظیر رسیدگی به درخواستهای وام مشتریان ، صدور گواهی سپرده، خرید و فروش اوراق مشارکت، تنظیم صورتحسابها و … میپردازد. در این سیستم خدماتی بهدنبال آن هستیم که بهترین توالی از انجام امور بانکی مشتریان را بهنحوی بدست آوریم که بیشترین زمان تکمیل امور بانکی کمینه شود.
1-3. اهداف تحقیق
در تحقیق پیش رو بهدنبال آن هستیم که با ارائه یک مدل ریاضی جدید برای مسئله ماشینهای موازی نامرتبط با فرض وجود امکان دوبارهکاری اقلام معیوب بههمراه محدودیتهای ذکر شده در بخش تعریف مسئله، به اهداف حاصل از طرح مسئله نظیر استفاده کارآمد از منابع و زمان، کاهش هزینههای تولیدی و خدماتی، جلب رضایت مشتریان و حفظ آنها و در نهایت نزدیکتر کردن مسئله زمانبندی ماشینهای موازی نا مرتبط به مسائل دنیای واقعی نائل شویم.
1-4. مفروضات عمومی مسئله
کارها مستقل از یکدیگر میباشند.
در سیستم تولیدی، احتمال تولید اقلام معیوب وجود دارد.
تعداد دوبارهکاری برای هر قلم کالا محدود است.
امکان شکست در کارها وجود ندارد.
زمان آمادهسازی وابسته به توالی کارها و وابسته به نوع ماشینآلات وجود دارد.
بیکاری ماشینها مجاز است.
تمام ماشینها بطور مستمر در دسترس هستند و امکان خرابی ماشینها وجود ندارد.
برای هر قلم کالا، محدودیت دسترسی به ماشینها وجود دارد.
محدودیت زمان دسترسی به کارها وجود دارد.(تمام کارها در لحظه صفر در دسترس نیستند)
زمان پردازش کارهای اصلی، زمان نصب ماشین، ضرایب کاهنده زمان، احتمالات معیوب بودن اقلام تولیدی و زمانهای دسترسی به کارها معین میباشند. فرض بر این است که دادههای فوق با توجه به اطلاعات جمعآوری شده مربوط به گذشته از محیط مورد بررسی گردآوری شدهاند.
1-5. ضرورت انجام تحقیق
مسائل زمانبندی ماشینهای موازی نامرتبط، یکی از کاربردی ترین مسائل در سیستمهای تولیدی و خدماتی میباشد که در مقایسه با انواع دیگر مسائل ماشینهای موازی، با توجه کمتری از سوی محققین روبرو بوده است. همچنین، موضوع کاهش هزینههای تولید همواره بهعنوان یکی از اهداف عملیاتی بیشتر واحدهای تولیدی مطرح بوده است و یکی از موثرین روشها در تحقق این هدف، دوبارهکاری اقلام معیوب میباشد. لذا در این تحقیق، مسئله زمانبندی ماشینهای موازی نامرتبط با فرض امکان دوبارهکاری اقلام معیوب مورد بررسی قرار میگیرد. همچنین در مسئله فوق، بدلیل اهمیت زمانهای آمادهسازی وابسته به توالی در بسیاری از صنایع، فرض وابسته بودن زمان آمادهسازی ماشین به توالی کارها و نوع ماشینآلات در مسئله لحاظ شده است. با تحقیقات صورتگرفته در زمینه مسائل زمانبندی ماشینهای موازی، جای خالی تحقیقی که در آن مسئله ماشینهای موازی نامرتبط با فرض امکان دوبارهکاری اقلام فاقد کیفیت و محدودیتهای زمان دسترسی به کارها، زمان نصب وابسته به توالی و وابسته به نوع ماشین و دسترسی محدود به ماشینها مورد بررسی قرار گرفته باشد، احساس میشد. لذا در تحقیق پیش رو، مسئله یاد شده مورد مطالعه قرار گرفته است و یک مدل بهینهسازی برای آن ارائه میشود و از الگوریتمهای فراابتکاری شامل الگوریتم ژنتیک و الگوریتم زنبور عسل بهمنظور حل مدل در اندازههای کاربردی استفاده می شود.
1-6. محتویات تحقیق
مطالب ارائه شده در این تحقیق در پنج فصل سازماندهی میشوند: کلیات تحقیق در فصل اول ارائه شده است. در فصل دوم، مروری بر ادبیات تحقیق مسائل زمانبندی ماشینهای موازی بویژه ماشینهای موازی نامرتبط صورت میگیرد. در فصل سوم، مدل پیشنهادی برای مسئله مورد بررسی در این تحقیق ارائه و تشریح میگردد و کلیاتی راجع به الگوریتمهای ژنتیک و زنبور عسل بیان میشود. شرح نحوه پیادهسازی الگوریتمهای یاد شده بههمراه نتایج محاسباتی حاصل از حل مسائل معیار توسط هر کدام از الگوریتمها در فصل چهارم صورت میگیرد و در پایان، فصل پنجم شامل نتیجهگیری و پیشنهادات برای انجام تحقیقات آتی میباشد.
فصل دوم
مرور ادبیات و پیشینه تحقیق
2-1. مقدمه
تحقیق در زمینه مباحث زمانبندی در اوایل دهه پنجاه میلادی شکل جدیتری به خود گرفت و اولین مقالههای علمی در این زمینه، در اوایل این دهه به چاپ رسید. با این وجود، یکی از اولین مطالعات در زمینه مسائل زمانبندی به سالها قبل و در حین جنگ جهانی اول باز میگردد. هنری لارنس گانت13 یکی از پیشگامان مباحث زمانبندی میباشد که یک مهندس صنایع و از پیروان نظریات فردریک تیلور14 در این زمینه بود. وی در زمان جنگ جهانی اول نمودار معروف خود که به نمودار گانت15 معروف است را طراحی کرد. نموداری که در آن محور افقی نشان دهنده زمان و محور عمودی نشان دهنده منابع و یا فعالیت ها میباشد ]4[.
تحقیق در زمینه مسائل زمانبندی در طی پنجاه سال گذشته به شکل گستردهتری دنبال شده و تکامل یافته است و به موضوعی با تاریخچه تحقیقاتی غنی از قواعد و الگوریتمهای ساده و پیچیده نظیر قاعده جانسون16 ، قاعده زودترین موعد تحویل17 ، الگوریتم مور18 ، روش شاخه و حد19، روشهای برنامهریزی پویا20، و بسیاری از روشهای ابتکاری و فراابتکاری تبدیل شده است.
در دهه شصت میلادی در اغلب مقالهها از تکنیکهای برنامهریزی پویا و یا مدلسازی برنامهریزی عدد صحیح برای حل مسایل زمانبندی و توالی عملیات21 استفاده میشد. پس از انتشار مقاله ریچارد کارپ ]5[ در اوایل دهه هفتاد میلادی در زمینه نظریه پیچیدگی، بسیاری از مطالعات انجام شده در این دهه بر روی سلسله مراتب پیچیدگی مسائل زمانبندی متمرکز شد. نتایج مطالعات حاکی از آن بود که طیف گستردهای از مسائل زمانبندی دارای پیچیدگی ساختاری میباشند و به همین دلیل الگوریتم های دقیق22 قادر نخواهند بود که در یک زمان محاسباتی قابل قبول جواب بهینه این مسائل را بیابند. از این رو در سالهای بعد تلاشهای جدی به منظور ایجاد و توسعه الگوریتمهای ابتکاری و فراابتکاری صورت پذیرفت. یکی از اولین و در عین حال معروفترین الگوریتمهای فراابتکاری، الگوریتم ژنتیک میباشد که اصول اولیه آن توسط هالند23و همکارانش در زمینه مدلسازی فرآیند سازگاری سیستمهای طبیعی در قالب سیستمهای مصنوعی ارائه شد و ایده اصلی آن مبتنی بر نظریه تکاملی داروین24 میباشد. از جمله دیگر الگوریتمهای فراابتکاری شناخته شده در حل مسائل بهینهسازی میتوان به الگوریتمهای شبکه عصبی25، ایمنی مصنوعی26، شبیهسازی تبرید27 ، اجتماع مورچگان28 و جستجوی ممنوع29 اشاره کرد. در راستای همین تلاشها در سالهای اخیر نیز الگوریتمهای متعددی به منظور حل مسائل بهینهسازی در یک زمان محاسباتی قابل قبول ارائه شده است که از آن جمله میتوان از الگوریتم زنبورعسل، الگوریتم رقابت استعماری30، الگوریتم کرم شبتاب31، الگوریتم جستجوی هارمونی32 و چند الگوریتم دیگر یاد کرد.
الگوهای زیادی در تعریف مسائل زمانبندی و طبقهبندی آنها مطرح هستند. برای مسائل زمانبندی از نظر فرآیند تولید محصولات و بسته به تعداد عملیات مورد نیاز برای پردازش یک کار و نیز تعداد ماشینهای موجود برای پردازش هر عملیات الگوهای زیادی را میتوان برشمرد. در کل یک مسئله زمانبندی عمومی میتواند با استفاده از سه نماد بصورتα/β/γ تعریف شود که α بیانگر وضعیت و شرایط ماشین یا منبع است و معمولا دارای یک نماد است، β خصوصیات و جزئیات نحوه پردازش و محدودیتهای موجود را بیان میکند و ممکن است شامل هیچ نمادی نباشد و یا چندین نماد باشد، γ بیانگر تابع هدف مسئله است و معمولا شامل تنها یک نماد است. در ادامه مبحث به بیان شرایط متداول برای هر نماد بصورت خلاصه پرداخته میشود.

2-2. محیطهای کارگاهی
2-2-1. تک ماشینه33
سادهترین حالت ممکن است که معمولا حالت خاص سایر مسایل در نظر گرفته میشود. در این حالت فقط یک ماشین در دسترس بوده و این ماشین قادر به پردازش تنها یک کار در هر لحظه میباشد و هر کار فقط به یک عملیات برای تکمیل شدن نیاز دارد. این مدل، مبنا و اساس کار برای ایجاد قوانین و قواعد زمانبندی برای استفاده در سایر مدلها میباشد. بهعبارت دیگر، عموما روشها و راهکارها ابتدا برای یک مدل تک ماشینه تبیین میگردد و سپس برای سایر مدلها بسط داده میشوند.
2-2-2 . ماشینهای موازی34
در این سیستم تعدادی ماشین بصورت موازی در دسترس هستند. هر کار تک عملیاتی میباشد و بر روی یکی از ماشینهای موجود پردازش میشود. این سیستم، از لحاظ ویژگیهای ماشین از قبیل سرعت پردازش، کیفیت محصولات تولیدی و هزینه تولید به سه دسته ماشینهای موازی یکسان35، ماشینهای موازی یکنواخت36 و ماشینهای موازی نامرتبط37 تقسیم میشوند.
2-2-2-1. ماشینهای موازی یکسان
حالتی است که در آن ماشینهای کاملا یکسان به موازات یکدیگر قرار میگیرند. در این حالت زمان پردازش کار نوع j روی تمامی ماشینها یکسان است.
2-2-2-2. ماشینهای موازی یکنواخت
حالتی است که در آن ماشینها دارای سرعتهای متفاوتی هستند ولی هر ماشین با یک نرخ ثابت کار میکند.
2-2-2-3. ماشینهای موازی نامرتبط
حالتی است که در آن ماشینها دارای سرعتهای متفاوتی هستند و هیچ رابطه مشخصی بین سرعت پردازش ماشینها وجود ندارد. در این حالت زمان مورد نیاز برای پردازش هر کار هم به نوع کار و هم به نوع ماشین وابسته است.
2-2-3 . جریان کارگاهی38
در این سیستم تولیدی، هر کار به چند عملیات برای تکمیل شدن نیاز دارد. کارها روی چند ماشین در یک توالی یکسان پردازش میشوند، اما زمان پردازش هر کار روی هر ماشین ممکن است متفاوت با زمان پردازش سایر کارها روی همان ماشین باشد.
2-2-4 . جریان کارگاهی منعطف39
این حالت تعمیمیافته حالت جریان کارگاهی و ماشینهای موازی میباشد. در این سیستم تعدادی کارگاه بهصورت متوالی وجود دارد که در هر کارگاه، تعدادی ماشین به طور موازی کار میکنند و در هر کارگاه، یک کار حداکثر روی یک ماشین میتواند انجام شود. اغلب مسائل دنیای واقعی، سازگار با محیط جریان کارگاهی منعطف میباشند.
2-2-5 . کار کارگاهی40
هر کار به چند عملیات نیاز دارد، تعدادی ماشین مختلف در کارگاه وجود دارند. هر کار ممکن است به برخی یا تمام ماشینها در یک توالی مشخص مربوط به خود، نیاز داشته باشد. یک کار میتواند برای پردازش به یکی از ماشینها یک و یا چند مرتبه مراجعه نماید.
2-2-6 . کار کارگاهی منعطف41
این حالت تعمیمیافته حالت جریان کارگاهی و ماشینهای موازی میباشد. در این حالت تعدادی مرکز کاری برای پردازش کارها موجود است که در هر مرکز کاری، تعدادی ماشین بصورت موازی کار میکنند. هر کار باید بهترتیب در هر مرحله توسط یکی از ماشینهای موجود پردازش شده و به مرحله بعد برود.
2-2-7 . سیستم کارگاهی باز42
این محیط تولیدی، مشابه سیستم کار کارگاهی است، با این تفاوت که یک کار میتواند روی ماشینها به هر توالی دلخواهی پردازش شود. به عبارت دیگر هیچ تقدم و تأخر عملیاتی در فرآیند تولید محصولات وجود ندارد. معمولا هدف در این سیستم تولیدی، حداقلسازی زمان اتمام کلیه کارها است.
2-2-8 . سیستم ساخت انعطاف پذیر43
در این سیستم هر ماشین ممکن است قادر به انجام بیش از یک عملیات باشد. بنابراین هر دو ماشین در انجام یک سری از عملیات ممکن است حکم دو ماشین موازی را داشته باشند و در مورد یکسری از عملیات با یکدیگر اشتراکی نداشته باشند.
2-2-9. سیستم کارگاهی وابسته44
یک محیط سیستم کار کارگاهی است که در آن، زمان شروع و پایان یکسری از کارها، به هم وابسته است. مثال بارز این سیستم، خطوط مونتاژ است. در مورد هر یک از سیستمهای تولیدی فوق، وابستگی زمان و هزینه نصب وابسته به توالی، میتواند دو سیستم مختلف را پدید آورد. از طرفی، سیستمهای تولیدی در دنیای واقعی با پدیدههای تصادفی بسیاری روبرو هستند که موجب قطع یا شکست سیستم میگردد. این رویدادها به عنوان رویدادهای زمان واقعی شناخته میشوند.

2-3. جزئیات و محدودیتهای نحوه پردازش کارها
2-3-1. زمان دسترسی به کار45 (r_j )
این محدودیت بدان معنی است که پردازش کار نوع j نمیتواند پیش از زمان دسترسی آن آغاز شود و در شرایطی برقرار است که تمام کارها در ابتدای افق زمانبندی در دسترس نباشند.
2-3-2. زمان نصب وابسته به توالی46 (S_ijk )
نشان دهنده زمان مورد نیاز برای آمادهسازی ماشین نوع i می باشد هنگامیکه پردازش کار نوع jتمام شده و قرار است پردازش کار نوع k شروع شود.
2-3-3. شکست در کارها47 (prmp)
در این حالت برنامهریز می تواند پردازش یک کار را بر روی یک ماشین پیش از تکمیل شدن آن قطع و کار دیگری را بر روی ماشین جایگزین کند.
2-3-4. اولویت در پردازش کارها48 (prec)
این محدودیت بدان معنی است که آغاز پردازش یک یا چند کار وابسته به این است که کار دیگری پیش از آنها انجام شده باشد.
2-3-5. خرابی ماشین49 (brkdwn)
زمانی در قالب یک محدودیت مشاهده میشود که ماشینها بطور مستمر در دسترس نباشند.
2-3-6. دسترسی محدود به ماشین ها50 (M_j )
این حالت زمانی رخ می دهد که m ماشین بطور موازی در دسترس باشند ولی تنها تعدادی از ماشینها قادر به پردازش کار نوع j باشند. مجموعه M_j شامل ماشینهایی است که قابلیت پردازش کار نوع j را دارند.
2-3-7. جایگشت51 (prmu)
در شرایطی برقرار است که ترتیب پردازش کارها روی تمامی ماشینها یکسان است. غالبا در مسائل جریان کارگاهی برقرار است.
2-3-8. بلوکه شدن52 (block)
در مسائل جریان کارگاهی با ظرفیت محدود برای بافر، هنگامی که ظرفیت صف بین دو ماشین متوالی تکمیل میشود، کار تکمیل شده بر روی ماشین بالادستی باقی میماند و از پردازش کار بعدی بر روی آن جلوگیری میشود.
2-3-9. بدون انتظار53 (nwt)
در مسائل جریان کارگاهی، یک کار نبایستی در حین پردازش میان دو ماشین متوقف شود.
2-3-10. گردش مجدد54 (rcrc)
در شرایطی برقرار است که در مسائل کار کارگاهی و یا کار کارگاهی منعطف، حداقل یکی از کارها بتواند از یکی از ماشینها و یا یکی از مراکز کاری بیش از یک مرتبه عبور کند.
2-3-11. گروه های کاری55 (fmls)
حالتی است که در آن کارهای تخصیص یافته برای پردازش متعلق به خانوادههای مختلف هستند. زمان پردازش اعضای هر گروه میتواند متفاوت باشد اما آنها میتوانند بصورت متوالی بر روی یک ماشین بدون نیاز به زمان نصب پردازش شوند.
2-3-12. پردازش دسته ای56 (batch(b))
در این فرآیند، کارها به صورت دستهایی بصورت همزمان پردازش میشوند. پردازش هر دسته، نیازمند زمان مشخصی است و ممکن است برای تعداد کارهایی که میتوانند در یک زمان پردازش شوند یک محدودیت ظرفیتی وجود داشته باشد.

2-4. توابع هدف
2-4-1. بیشینه زمان تکمیل کارها57 (C_max )
به مفهوم زمان تکمیل آخرین کاری است که سیستم را ترک میکند. این ضابطه بهرهوری ماشینآلات را به طرز چشمگیری افزایش میدهد.
2-4-2. بیشینه زمان تاخیر کارها58 (L_max )
بیشترین انحراف زمانی از موعدهای تحویل کارها را نشان میدهد.
2-4-3. مجموع زمان تکمیل کارها59 (∑▒C_j )
مجموع زمانهای تکمیل کارها را اندازهگیری میکند و سعی بر کمینه کردن آن موجب کاهش هزینههای نگهداری میشود. در ادبیات زمانبندی از کمینهسازی مجموع زمانهای تکمیل کارها با عنوان کمینهسازی مجموع زمانهای در جریان ساخت60 نیز یاد میشود.
2-4-4. مجموع وزنی زمان تکمیل کارها61 (∑▒〖W_j C_j 〗)
حالت کلیتر تابع هدف مجموع زمان تکمیل کارها میباشد. در این حالت به کارهای با هزینه نگهداری بیشتر، وزن بالاتری داده میشود.
2-4-5. مجموع زمان دیرکرد کارها62 (∑▒T_j )
مجموع انحرافهای زمانی کارها از موعدهای تحویل را محاسبه مینماید.
2-4-6. مجموع وزنی زمان دیرکرد کارها63 (∑▒〖W_j T〗_j )
مجموع انحرافهای زمانی وزنی کارها از موعدهای تحویل را محاسبه مینماید.
2-4-7. مجموع تعداد کارهای با تاخیر64 (∑▒U_j )
تعداد کارهایی که موعد تحویل آنها گذشته است را نشان میدهد.
2-4-8. مجموع وزنی تعداد کار های با تاخیر65 (∑▒〖W_j U_j 〗)
حالت کلیتر تابع هدف مجموع تعداد کارهای با تاخیر میباشد. در این حالت به کارهایی که از لحاظ اهمیت تحویل در موعد مقرر از درجه اهمیت بالاتری برخوردار هستند، ضرایب وزنی بالاتری داده میشود.
2-4-9. مجموع زمان های زودکرد و دیرکرد کارها66 (∑▒〖E_j+∑▒T_j 〗)
این تابع هدف از نوع توابع هدف معمولی که در بالا به آنها اشاره شد نمیباشد چرا که در آنها با اتمام کارها مقدار تابع هدف بصورت غیر نزولی افزایش مییابد ولی تابع هدف مجموع زمانهای زودکرد و دیرکرد از این جنس نمیباشد. در این تابع هدف بهدنبال آن هستیم که کارها تا حد امکان در موعد تحویل مربوطه آماده شوند. از کاربردهای آن می توان به صنایع تولید مواد فاسد شدنی اشاره کرد.
2-4-10. مجموع وزنی زمانهای زودکرد و دیرکرد کارها67 (∑▒〖〖W_j E〗_j+∑▒〖〖W’〗_j T_j 〗〗)
حالت کلیتر تابع هدف مجموع زمانهای زودکرد و دیرکرد کارها میباشد که در آن با توجه به اهمیت هر کار و میزان بحرانی بودن زودکرد و دیرکردد آن نسبت به موعد تحویل، به هر کار دو ضریب وزنی اختصاص مییابد.
2-5. پیشینه تحقیق
از اواسط قرن گذشته مباحث زمانبندی و توالی عملیات بصورت فزایندهای مورد توجه محققین و دانشمندان قرار گرفت و تحقیقات گستردهای در این حیطه صورت پذیرفت. از آنجایی که این مسائل در دنیای واقعی عموما دارای تعداد زیادی فعالیت و منبع میباشند، در نتیجه یک مجموعه گوناگون از اهداف و محدودیت بهرهبرداری از منابع در مورد آنها مطرح میشود. به همین دلیل است که تلاشهای انجام شده بهمنظور حل برنامهریزی ریاضی و یا حتی فرموله نمودن آن ها وقت گیر و پر زحمت میباشد. یکی از انواع مسائل مورد بررسی در این زمینه، مسئله زمانبندی ماشینهای موازی میباشد که از نقطه نظر تئوری و تجربی دارای اهمیت فراوانی میباشد. از دیدگاه آکادمیک، اهمیت مسئله زمانبندی ماشینهای موازی از آنجایی است که این مسئله حالت عمومیت یافته مسئله زمانبندی تک ماشینه و حالت خاصی از مسائل زمانبندی جریان کارگاهی منعطف و کار کارگاهی منعطف میباشد. از نقطه نظر تجربی نیز اهمیت این مسئله در آن است که در بسیاری از محیطهای تولیدی و خدماتی وضعیت قرار گیری ماشینها (اپراتورها) نسبت به یکدیگر بصورت یکی از انواع سه گانه مسائل ماشینهای موازی میباشد.
در این تحقیق، مسئله زمانبندی ماشینهای موازی نامرتبط با فرض وجود امکان دوبارهکاری اقلام معیوب بههمراه محدودیتهای زمان دسترسی به کارها، زمان نصب وابسته به توالی کارها و وابسته به نوع ماشینآلات و دسترسی محدود به ماشینها با هدف کمینهسازی بیشترین زمان تکمیل کارها مورد مطالعه قرار میگیرد. در ادامه به منظور مروری بر ادبیات و مطالعات صورت پذیرفته، تحقیقات مرتبط با مسئله مورد بررسی در این تحقیق به تفکیک نوع محیط کارگاهی و محدودیتهای قید شده در صورت مسئله در بخشهای جداگانهای آدرسدهی میشوند. بدلیل گستردگی مطالب در ادبیات زمانبندی، در این تحقیق سعی بر آن است که در بخش بررسی محدودیتها، تحقیقاتی مورد بررسی قرار بگیرند که در حیطه مسائل زمانبندی ماشینهای موازی بویژه ماشینهای موازی نامرتبط میباشند.
2-6. ماشینهای موازی نامرتبط
مسئله زمانبندی ماشینهای موازی، یکی از پرکاربرد ترین مسائل زمانبندی در سیستمهای تولیدی و خدماتی میباشد و در سه گروه ماشینهای موازی یکسان، ماشینهای موازی یکنواخت و ماشینهای موازی نامرتبط دستهبندی میشود. در یک تعریف ساده، مسئله زمانبندی ماشینهای موازی بدین صورت بیان میشود که یک مجموعه از n کار متمایز، N={1,2,…,n}، بر روی مجموعه ای از m ماشین موجود و در دسترس، M ={1,2,…,m} ، که بصورت موازی نسبت به هم قرار گرفتهاند پردازش میشوند. هر کار تنها بر روی یک ماشین پردازش میشود و هر ماشین در هر لحظه قادر به انجام تنها یک کار میباشد.
در سالهای اخیر، یک مطالعه جامع و کامل بر روی مسائل زمانبندی توسط الله وردی و همکاران ]6[ صورت پذیرفت. آنها یک مرور کامل بر مسائل تک ماشینه، ماشینهای موازی، جریان کارگاهی، جریان کارگاهی بدون تاخیر68 ، جریان کارگاهی منعطف، کار کارگاهی و سیستم کارگاهی باز انجام دادند و آنها را در دو قالب پردازش دستهای و غیر دستهای69 و زمان نصب وابسته به توالی و زمان نصب مستقل از توالی70 واکاوی کردند. یکی از اولین تحقیقات در زمینه مسائل زمانبندی ماشینهای موازی توسط مک ناتن ]7[ در اواخر دهه پنجاه میلادی صورت پذیرفت. همچنین محققان دیگری همچون موکوتوف ]8[ ،لام و ژینگ ]9[ و چنگ و سین ]10[ بررسیها و مطالعاتی بر روی مسائل ماشینهای موازی انجام دادند ولی بیشتر این تحقیقات در زمینه مسائل ماشینهای موازی یکسان بود و مسائل ماشینهای موازی نامرتبط در حجم بسیار کمتری مورد مطالعه قرار میگرفت. در ادامه این بخش، تعدادی از تحقیقات صورت پذیرفته در زمینه مسائل ماشینهای موازی نامرتبط آدرسدهی میشوند.

دسته بندی : پایان نامه ارشد

پاسخ دهید