وزارت علوم، تحقیقات و فناوری

دانشگاه علوم و فنون مازندران

پایان‌نامه کارشناسی ارشد رشته مهندسی صنایع

گرایش صنایع

عنوان:

زمان­بندی ماشین ­های موازی نامرتبط به ­همراه دوباره­ کاری با در نظر­گرفتن محدودیت دسترسی به ماشین­ ها

استاد راهنما:

دکتر جواد رضائیان

فهرست مطالب:

فصل اول    1
کلیات تحقیق    1
1-1. مقدمه    2
1-2. تعریف مسئله    3
1-3. اهداف تحقیق    6
1-4. مفروضات عمومی مسئله    6
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 جای می­گیرد، در نتیجه الگوریتم­های دقیق از کارایی لازم برای حل مسائل در ابعاد متوسط و بزرگ برخوردار نیستند. بنابراین، به­منظور یافتن جواب­های بهینه و یا نزدیک به بهینه از الگوریتم­های فراابتکاری شامل الگوریتم ژنتیک و الگوریتم زنبور­عسل استفاده شده است. در حل مسائل با ابعاد کوچک که حتی در بعضی موارد از پیچیدگی بالایی برخوردار هستند، مقادیر بدست آمده از الگوریتم­های ژنتیک و زنبور­عسل با جواب­های بهینه مقایسه شده است که نتایج حاکی از آن است که الگوریتم­های یاد شده قادر به تولید جواب­هایی به خوبی جواب­های بدست آمده از الگوریتم­های دقیق در یک زمان محاسباتی بسیار کوتاه­تر می­باشند.

برای دانلود متن کامل پایان نامه اینجا کلیک کنید.