سایت مرجع دانلود پایان نامه -پشتیبانی 09361998026

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

ارسال شده در سایت پایان نامه

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

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

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

گرایش صنایع

عنوان:

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

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

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

فهرست مطالب:

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

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

 

مطالب مشابه را هم ببینید

141985615752731

فایل مورد نظر خودتان را پیدا نکردید ؟ نگران نباشید . این صفحه را نبندید ! سایت ما حاوی حجم عظیمی از پایان نامه ، تحقیق ، پروژه و مقالات دانشگاهی در رشته های مختلف است. مطالب مشابه را هم ببینید یا اینکه برای یافتن فایل مورد نظر کافیست از قسمت جستجو استفاده کنید. یا از منوی بالای سایت رشته مورد نظر خود را انتخاب کنید و همه فایل های رشته خودتان را ببینید فروش آرشیو پایان نامه روی دی وی دی

aca@

academicbooks@

پایان نامه بررسی تاثیر روش تدریس جیگ ساو و روش تدریس یادگیری در حد تسلط بر پیشرفت تحصیلی دانش آموزان...
پایان نامه مطالعه‌ی عددی تأثیر پارامترهای مؤثر شرایط اولیه‌ی حاکم بر محفظه‌ی احتراق موتور پاشش‌مستقی...
پایان نامه رابطه بين نمادهاي منزلتي سبک زندگي با نگرش شهروندان به جرم دربندر عباس
پایان نامه تعیین متغیرهای تعدیل کننده تاثیر گذار بر استرس شغلی
پایان نامه مداخله بشردوستانه و ارتباط آن با حاکمیت ملی کشورها