پایان نامه مهندسی صنایع گرایش صنایع: زمان بندی ماشین های موازی نامرتبط به همراه دوباره کاری با در نظر گرفتن محدودیت دسترسی به ماشین ها |
 |
1-5. ضرورت انجام تحقیق 6
1-6. محتویات تحقیق 7
فصل دوم 8
ادبیات و پیشینه تحقیق 8
2-1. مقدمه 9
2-2. محیط های کارگاهی 11
2-2-1. تک ماشینه 11
2-2-2 . ماشین های موازی 11
2-2-2-1. ماشین های موازی یکسان 11
2-2-2-2. ماشین های موازی یکنواخت 11
2-2-2-3. ماشین های موازی نامرتبط 12
2-2-3 . جریان کارگاهی 12
2-2-4 . جریان کارگاهی منعطف 12
2-2-5 . کار کارگاهی 12
2-2-6 . کار کارگاهی منعطف 12
2-2-7 . سیستم کارگاهی باز 13
2-2-8 . سیستم ساخت انعطاف پذیر 13
2-2-9. سیستم کارگاهی وابسته 13
2-3. جزئیات و محدودیت های نحوه پردازش کارها 13
2-3-1. زمان دسترسی به کار rj 13
2-3-2. زمان نصب وابسته به توالی Sijk 14
2-3-3. شکست در کارها prmp 14
2-3-4. اولویت در پردازش کارها prec 14
2-3-5. خرابی ماشین brkdwn 14
2-3-6. دسترسی محدود به ماشین ها Mj 14
2-3-7. جایگشت prmu 14
2-3-8. بلوکه شدن block 15
2-3-9. بدون انتظار nwt 15
2-3-10. گردش مجدد rcrc 15
2-3-11. گروه های کاری fmls 15
2-3-12. پردازش دسته ای batch(b) 15
2-4. توابع هدف 16
2-4-1. بیشینه زمان تکمیل کارها Cmax 16
2-4-2. بیشینه زمان تاخیر کارها Lmax 16
2-4-3. مجموع زمان تکمیل کارها Cj 16
2-4-4. مجموع وزنی زمان تکمیل کارها WjCj 16
2-4-5. مجموع زمان دیر کرد کارها Tj 16
2-4-6. مجموع وزنی زمان دیرکرد کارها WjTj 16
2-4-7. مجموع تعداد کارهای با تاخیر Uj 17
2-4-8. مجموع وزنی تعداد کار های با تاخیر WjUj 17
2-4-9. مجموع زمان های زودکرد و دیرکرد کارها Ej+Tj 17
2-4-10. مجموع وزنی زمان های زودکرد و دیرکرد کارها WjEj+W’jTj 17
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 و زنبور2 107
شکل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) در شرایط افزایش در زمان نصب کار شماره 3 42
شکل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% برای معیار RPD 107
چکیده
زمانبندی و توالی عملیات نوعی فرایند تصمیم گیری است که با هدف بهینهسازی یک یا چند معیار، بهدنبال تخصیص بهینه منابع محدود به تعدادی کار در طول افق زمانبندی است و نقشی حیاتی در بقای سیستمهای تولیدی و خدماتی ایفا می کند. در تحقیق پیش رو، مسئله زمانبندی ماشینهای موازی نامرتبط با فرض دسترسی محدود به ماشینها، زمانهای نصب وابسته به توالی و وابسته به نوع ماشین و احتمال تولید اقلام فاقد کیفیت مورد بررسی قرار میگیرد. از فرایندهای دوبارهکاری با هدف رساندن سطح کیفی اقلام معیوب به یک سطح قابل قبول استفاده می شود. بهمنظور مدلسازی مسئله یاد شده، یک مدل ریاضی پیشنهاد و از معیار بیشینه زمان تکمیل کارها بهعنوان تابع هدف در مسئله موردنظر استفاده شده است. از آنجایی که این مسئله از لحاظ پیچیدگی در دسته مسائل Strongly NP-hard جای میگیرد، در نتیجه الگوریتمهای دقیق از کارایی لازم برای حل مسائل در ابعاد متوسط و بزرگ برخوردار نیستند. بنابراین، بهمنظور یافتن جوابهای بهینه و یا نزدیک به بهینه از الگوریتمهای فراابتکاری شامل الگوریتم ژنتیک و الگوریتم زنبورعسل استفاده شده است. در حل مسائل با ابعاد کوچک که حتی در بعضی موارد از پیچیدگی بالایی برخوردار هستند، مقادیر بدست آمده از الگوریتمهای ژنتیک و زنبورعسل با جوابهای بهینه مقایسه شده است که نتایج حاکی از آن است که الگوریتمهای یاد شده قادر به تولید جوابهایی به خوبی جوابهای بدست آمده از الگوریتمهای دقیق در یک زمان محاسباتی بسیار کوتاهتر میباشند.
1-1. مقدمه
مسائل زمان بندی یکی از مهمترین مسائل دنیای امروز می باشند که تاثیر شگرفی در افزایش بهره وری سیستم های تولیدی و خدماتی دارند. زمان بندی در عمل به معنای تخصیص منابع محدود به فعالیت هایی است که به آن منبع نیاز دارند و در واقع نوعی فعالیت تصمیم گیری است که با هدف بهینه سازی یک و یا چند معیار انجام می گیرد. باید به این نکته توجه داشت که در دنیای رقابتی کنونی، برای موسسه ها، داشتن بهترین توالی انجام عملیات و زمان بندی مناسب فعالیت ها یک نیاز اساسی به منظور بقاء تعریف می شود و به عنوان یک فرایند تصمیم گیری، مبنای کار بسیاری از صنایع تولیدی و خدماتی محسوب می شود. به بیان بهتر، زمان بندی را می توان تخصیص منابع محدود در طول زمان به منظور اجرای مجموعه ای از وظایف تعریف کرد. در دنیای امروز، زمان همواره یک محدودیت اساسی بوده است. بنابراین، زمان بندی صحیح فعالیت ها به منظور حداقل کردن این منبع با توجه به هزینه های تولیدی و خدماتی در واحد زمان، امری ضروری به نظر می رسد.
با پیشرفت علم و به دنبال آن توسعه و شکوفایی صنایع تولیدی و خدماتی، نقش منابع و نحوه تخصیص آن ها از اهمیت دو چندانی برخوردار شده است. امروزه منابع در دسترس مانند نیروی انسانی، ماشین آلات، مواد اولیه و … به عنوان منابع بحرانی در تولید و فعالیت های خدماتی در نظر گرفته می شوند و زمان بندی و تخصیص به موقع و مناسب این منابع منجر به ارتقاء کارایی، بهره وری و در نهایت سودآوری بیشتر می شود. از آنجا که خواستگاه بسیاری از مسائل زمان بندی و توالی عملیات محیط های صنعتی می باشد، در بیان بسیاری از مفاهیم زمان بندی از واژه های بکار رفته در صنعت استفاده می شود. به عنوان مثال، در مباحث زمان بندی و توالی عملیات از منابع با عنوان ماشین و از فعالیت ها با عنوان کار یاد می شود به نحوی که کارها اغلب بوسیله ماشین ها در ایستگاه های مختلف کاری با توالی مشخص پردازش می شوند.
در مسائل زمان بندی، هدف از یافتن توالی انجام کارها می تواند متفاوت باشد. تعدادی از اهداف مورد استفاده در مسائل زمان بندی عبارتند از : کمینه سازی بیشترین زمان تکمیل کارها، کمینه سازی مجموع زمان تکمیل کارها، کمینه سازی بیشترین زمان دیرکرد و کمینه سازی تعداد کارهایی که دیرکرد دارند. همچنین بر حسب شرایط حاکم بر محیط مورد مطالعه، محدودیت های گوناگونی در مسئله لحاظ می شود. تعدادی از محدودیت های حاکم بر مسائل زمان بندی عبارتند از : زمان های نصب وابسته به توالی ، محدودیت دسترسی به ماشین ها، زمان های دسترسی به کار، برش در کارها، خرابی ماشین ها و محدودیت در اندازه صف کارها که مورد آخر در سیستم های جریان کارگاهی می تواند لحاظ شود . در ابتدای فصل دوم، مسائل زمان بندی به تفکیک محیط های کارگاهی، محدودیت های پردازش و توابع هدف بصورت مختصر معرفی می شوند. یک مسئله زمان بندی بصورت یک مسئله بهینه سازی بیان می-شود که با توجه به محدودیت های موجود، به دنبال ارضاء کردن هدف (اهداف) مورد نظر می باشد.
در مباحث زمان بندی، بررسی مدل های تک ماشینه به علت سادگی و به دلیل اینکه حالت خاصی از سایر مدل ها می باشد از اهمیت بالایی برخوردار است. در مقابل، نظریه زمان بندی سه نوع اساسی از مدل های چند ماشینی را پوشش می دهد: سیستم های موازی، سیستم های جریان کارگاهی و سیستم های تولید کارگاهی. در سیستم ماشین های موازی همانند مدل های تک ماشینی، هر یک از کارها با انجام یک عملیات بر روی یکی از ماشین های موازی موجود پردازش می شوند اما در سیستم های جریان کارگاهی و ترکیبی ساختار مسائل پیچیده تر است.
در ادامه به تعریف مسئله مورد بحث این تحقیق و مفروضات آن پرداخته می شود. در پایان اهداف و ضرورت تحقیق بیان می شود.
ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل و با فرمت ورد موجود است
متن کامل را می توانید دانلود نمائید
فرم در حال بارگذاری ...
|
[چهارشنبه 1399-10-03] [ 02:58:00 ب.ظ ]
|
