عنوان :  طراحی الگوریتم فراابتکاری برای زمانبندی ماشین­های موازی نامرتبط با تابع هدف چندگانه در محیط تولید بهنگام

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

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

 

پایان نامه

مقطع کارشناسی ارشد

 

رشته : مهندسی صنایع- مهندسی سیستم­های اقتصادی اجتماعی

عنوان: طراحی الگوریتم فراابتکاری برای زمانبندی ماشین­های موازی نامرتبط با تابع هدف چندگانه در محیط تولید بهنگام

 

اساتید راهنما: دکتر جواد رضائیان

دکتر ایرج مهدوی

(بهار 1393)

برای رعایت حریم خصوصی نام نگارنده پایان نامه درج نمی گردد

(در فایل دانلودی نام نویسنده موجود می باشد)

تکه هایی از متن پایان نامه به عنوان نمونه :

(ممکن می باشد هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود اما در فایل دانلودی همه چیز مرتب و کامل می باشد)

چکیده

در طول دهه گذشته، گسترش الگوریتم­های فراابتکاری بهینه سازی چند معیاره توجه بسیاری را به خود جلب نمود. مسائل برنامه ریزی تولید بهنگام به عنوان مهمترین مسئله برنامه­ریزی بهینه سازی نیز مستثنی نبود. البته بسیاری از الگوریتم­های بهینه سازی که برای مسائل گوناگون به کار برده می­شدند رویکردی نامناسب داشتند. به زبان دیگر بسیاری از آنها هدف­ ها را ترکیب می­کردند و مسائل را با رویکرد تک هدفه حل می­کردند. البته بعضی از محققان الگوریتم­های پارتویی به کار می­برند. در این پژوهش یک برنامه ریزی ماشین­های موازی نامرتبط با زمان آماده سازی وابسته به توالی، زمان دسترسی پویا به کارها، زمان تحویل متفاوت کارها و محدودیت مجموعه پردازشی نشان داده شده می باشد. توابع هدف مورد نظر، مجموع وزنی زمانهای زودکرد و دیرکرد کارها و همچنین مجموع زمان تکمیل کارها را کمینه می­کنند. برای حل مدل و اعتبار سنجی آن از الگوریتم­ مجموع وزنی و الگوریتم محدودیت اپسیلون بهره گیری شده می باشد. همچنین نشان داده شده می باشد که الگوریتم­هایی که از روش شاخه و کران برای حل بهره گیری می­کنند قادر به حل مسائل بزرگ در زمان معقول نمی­باشند. پس برای حل این مسئله برنامه ریزی چند معیاره که از نوع چند جمله­ای سخت (NP-Hard) می­باشد الگوربتم فراابتکاری (CENSGA)معرفی شده می باشد. الگوریتم ارائه شده را با بهره گیری از شاخص­های آماری با الگوریتم فراابتکاری (NSGA-II) مورد مقایسه و تحلیل قرار داده شده می باشد که نتایج نشان دهنده کارایی بهتر الگوریتم فراابتکاری (CENSGA) می­باشد.

کلمات کلیدی: تولید بهنگام; زمان آماده­سازی وابسته به توالی; کنترل نخبه­گرایی; بهینه سازی چند هدفه; الگوریتم مرتب سازی نامغلوب.

 

فهرست

1-1.        مقدمه. 2

1-2. تعریف مسأله زمانبندی.. 5

1-3. ضرورت انجام پژوهش.. 7

1-4. اهداف پژوهش.. 8

1-5. مفروضات مسئله. 9

1-6. جنبه های نوآوری پژوهش.. 10

1-7. محتوای پژوهش.. 10

2-1. مقدمه. 12

2-2. طبقه بندی محیط های زمانبندی.. 15

2-3. مسائل ماشینهای موازی.. 19

2-3-1. زمان نصب و آماده سازی.. 20

2-3-2. دسترسی محدود به ماشینها 26

2-3-3. زمان دسترسی متفاوت به کارها 27

2-4. مسائل با تمرکز بر موعد تحویل برای کارها 27

2-4-1. زمان تکمیل کارها 29

2-4-2. زمانهای زودکرد و دیرکرد. 29

2-5. مروری بر رویکرد و اصول سیستم تولیدی بهنگام. 31

2-6. توالی ماشینﻫای موازی با معیارهای زودکرد و دیرکرد. 33

2-7. جمع بندی.. 34

3-1. مقدمه. 37

3-2. تعریف مسئله. 37

3-2-1. مفروضات مسئله. 39

3-3. مدل پیشنهادی.. 39

3-3-1.نمادها، تعاریف، پارامترها و متغیر های تصمیم. 40

3-3-2. پارامترهای ورودی.. 40

3-3-3. توابع هدف.. 41

3-3-4. محدودیتها 41

3-4. اعتبارسنجی مدل. 43

3-5. پیچیدگی مسئله. 45

3-6 بهینه سازی چند معیاره. 47

3-6-1. ارتباط غالب.. 47

3-6-2. نقاط بهینه موضعی.. 48

3-6-3. نقاط بهینه سراسری.. 48

3-6-4. مرز بهینه. 48

3-7. روشهای بهینه سازی.. 49

3-7-1. روشهای اسکالر. 49

3-7-2. روش مجموع وزنی.. 51

3-7-2-1. طراحی روش مجموع وزنی برای حل مسأله مورد نظر. 54

3-7-3. روش محدودیت- . 55

3-7-3-1. طراحی روش محدودیت – برای حل مسأله. 57

3-7-4. روشهای عکس العملی.. 57

3-7-5. روش های مبتنی بر منطق فازی.. 58

3-7-6. روش های فرا ابتکاری.. 59

3-7-7. الگوریتم NSGA-II. 60

3-7-7-1. مرتب سازی سریع. 61

3-7-7-2. عملگر گزینش تورنمنت تراکمی.. 63

3-7-7-3. فاصله تراکمی.. 63

3-7-8. طراحی روش فراابتکاری NSGA-II برای حل مسأله. 65

3-7-9. طراحی روش فراابتکاری CENSGA برای حل مسأله. 70

3-8. مقایسه روش های بهینه سازی چند هدفه. 71

3-8-1. شاخص متوسط فاصله از نقطه ایدهآل. 73

3-8-2. شاخص نرخ دستیابی به توابع هدف.. 74

3-8-3. شاخص گستردگی جواب های غیر مغلوب (SNS) 74

3-8-4. شاخص یکنواختی فضا 74

3-9. جمعﺑندی.. 75

4‐1. مقدمه. 78

4‐2. تنطیمات پارامترها و شرایط اجرای الگوریتم ها 79

4-3. الگوریتمهای NSGA-II,CENSGA.. 80

4-4. روش مجموع وزنی.. 80

4-5. روش محدودیت- . 81

4‐6. ساختار مسائل.. 82

4‐7. معیارهای ارزیابی الگوریتمها 83

4‐8. مسائل با ابعاد کوچک و متوسط.. 83

4-8-1. نتایج آزمایشات مسائل کوچک و متوسط.. 83

4‐9. مسائل با ابعاد بزرگ.. 90

4‐10. نتایج محاسباتی.. 90

4‐11. جمعﺑندی.. 96

5‐1. مقدمه. 98

5‐2. نتیجهﮔیری.. 99

5‐3. پیشنهادهای آتی.. 100

فهرست منابع و مراجع. 102

..

فهرست جداول

جدول 2-1. محیط­های کارگاهی (نماد α) 13

جدول 2-2. توابع هدف رایج در ادبیات 15

جدول 3-1. زمان­های پردازش،موعدهای تحویل و زمان دسترسی44

جدول 3-2. زمان نصب ماشین یک و دو برای کارهای مختلف 44

جدول 4-1. حدهای بالا برای مسائل مختلف 82

جدول 4-2. جوابهای نامغلوب مربوط به مسأله 5j2m به تفکیک روش ها84

جدول 4-3. ارزیابی روشهای حل مسئله با شاخصهای کمی برای 5j2m 85

جدول 4-4. جوابهای نامغلوب مربوط به مسأله 5j3m به تفکیک روش ها85

جدول 4-5. ارزیابی روشهای حل مسئله با شاخصهای کمی برای 5j3m 86

جدول 4-6. جوابهای نامغلوب مربوط به مسأله 8j2m به تفکیک روش ها87

جدول 4-7. ارزیابی روشهای حل مسئله با شاخصهای کمی برای 8j2m88

جدول 4-8 . جوابهای نامغلوب مربوط به مسأله 8j3m به تفکیک روش ها 89

جدول 4-9. ارزیابی روشهای حل مسئله با شاخصهای کمی برای 8j3m 90

جدول 4-10 نتایج شاخص­های متریک برای الگوریتم CENSGAوNSGA-II 91

جدول 4- 11. ارزیابی آماری الگوریتم­های فراابتکاری بکار گرفته شده 94

فهرست شکل­ها و نمودارها

شکل 2-1. دسته بندی مسائل زمانبندی بر اساس مسیر تولید 19

شکل 3-1. سلسله­مراتب پیچیدگی محیط­های کارگاهی در مسائل زمان­بندی46

شکل 3-2. سلسله­مراتب پیچیدگی توابع هدف در مسائل زمان­بندی46

شکل 3-3. نقاط بهینه موضعی 48

شکل 3-4. ارتباط فضای جواب و ارتباط غالب 48

شکل 3-5. نمایش روش مجموع وزنی با مرز بهینه پارتو محدب 52

شکل 3-6. نمایش روش مجموع وزنی با مرز بهینه پارتو غیر محدب 54

شکل 3-7. روش محدودیت- 56

شکل 3-8. نمایش الگوریتم NSGAII61

شکل 3-9. محاسبه فاصله تراکمی 64

شکل 3-10. ساختار کروموزوم66

شکل 3-11. چگونگی ایجاد جمعیت اولیه 67

شکل 3-12. چگونگی عملکرد عملگر تقاطع 69

شکل 3-13. عملگر تقاطع تک نقطه ای با نقطه برش 369

شکل 3-14. چگونگی عملکرد عملگر جهش 70

شکل 3-15. استراتژی انتخاب در الگوریتم CENSGA و NSGA-II 71

شکل 3-16. دو هدف در بهینه سازی چند هدفه72

شکل 3-17. یک مجموعه ایده آل از جواب های نامغلوب72

شکل 3-18. همگرائی خوب، اما تنوع ضعیف (الگوریتم 1)73

شکل 3-19. همگرائی ضعیف، اما تنوع خوب (الگوریتم 2)73

شکل 4-1. نمایش جوابهای نامغلوب ε-محدودیت مسأله 5j2m 84

شکل 4-2. نمایش جوابهای نامغلوب روش وزنی مسأله 5j2m 84

شکل 4-3. نمایش جوابهای نامغلوب روش وزنی مسأله 5j3m86

این مطلب رو هم توصیه می کنم بخونین:   پایان نامه ارشد درباره:درجه بندی شدن مجازات تعزیری در قانون مجازات اسلامی 1392 در تطبیق با تقسیم بندی جرایم به جنحه، جنایت و خلاف

شکل 4-4. نمایش جوابهای نامغلوب روش محدودیت- مسأله 5j3m86

شکل 4-5 . نمایش جوابهای نامغلوب روش وزنی مسأله 8j2m88

شکل 4-6 . نمایش جوابهای نامغلوب روش محدودیت- مسأله 8j2m 88

شکل 4-7 . نمایش جوابهای نامغلوب روش وزنی مسأله 8j3m 89

شکل 4-8 . نمایش جوابهای نامغلوب روش محدودیت- مسأله 8j3m89

شکل 4- 9 نمودار نتایج محاسباتی شاخص های متریک در مسائل مختل92

شکل 4-10. نمودارجعبه ای (BoxPlot) نتایج ارزیابی الگوریتم­های CENSGA,NSGA-II 93

شکل 4-11. نمودار میانگین و فواصل اطمینان (سطح اطمینان 95%)نتایج ارزیابی الگوریتم ها 95

 

Article I.          فصل اول مقدمه و کلیات

 

1-1.          مقدمه

زمان­بندی[1]، فرایند تخصیص منابع به فعالیت­ها با درنظر گرفتن دوره­های زمانی مربوط به آنها به مقصود بهینه­سازی یک یا چند هدف می­باشد. این فرایند به عنوان یک فرایند تصمیم­گیری مبنای کار بسیاری از صنایع تولیدی و خدماتی محسوب می­گردد. زمان­بندی کارای فعالیت­ها زمینه­ساز بهبود عملکرد سیستم­های تولیدی می­باشد و ضرورتی برای بقا در فضای رقابتی بازار به ­شمار می­آید.

تئوری زمان­بندی در ارتباط با مدل­های ریاضی می باشد که فرایند زمان­بندی را تشریح می­کنند. چشم­انداز تئوریک یک توجه کمی برای بدست آوردن ساختار مسائل در چهارچوب مدل­های ریاضی به­دست می­دهد که این امر با تشریح منابع و فعالیت­ها و تبدیل اهداف تصمیم­گیری به یک تابع­ هدف، صورت می­پذیرد. اقدام زمانبندی در یک سازمان از مدل ها و روش های ریاضی و یا روش های ابتکاری برای تخصیص منابع محدود به کارهای در حال جریان بهره گیری می کند. اهمیت توالی ماشین های موازی، با هدف متمرکز بر دیرکرد از آن جهت مورد توجه می باشد که در محیط کسب و کار حاضر، رقابت شرکت های تولیدی از طریق قابلیت آنها برای پاسخگویی سریع به تغییرات سریع در زمینه تجارتی و تولید محصولات با کیفیت بالاتر و هزینه های کمتر تعیین می گردد. در نتیجه، منابع، فعالیت­ها و توابع هدف عناصر کلیدی مدل­های زمان­بندی محسوب می­شوند.

منابع بر حسب قابلیت­های کمی و کیفی خود مشخص می­شوند، بطوریکه هر مدل نشان­ دهنده نوع و اندازه منابع بکار رفته در آن می­باشد. از سوی دیگر، فعالیت­ها بر حسب اطلاعاتی از قبیل منابع مورد نیاز، مدت زمان انجام، زمان آغاز و زمان پایان آنها توصیف می­شوند. توابع هدف نیز دربرگیرنده هزینه­های سیستم برای اجرای تصمیمات مربوط به تخصیص منابع به فعالیت­ها می­باشند. تصمیمات عمده در فرایند زمان­بندی شامل بهره­برداری کارا از منابع، پاسخگویی سریع به تقاضا و انطباق دقیق زمان­های تحویل با موعد­های تحویل تعیین­شده می­شوند. شرکت های تولیدی در کوشش هستند تا این قابلیت ها را از طریق اتوماسیون و مفاهیم خلاق مانند تولید به موقع[2] (JIT) ، پاسخگوی سریع[3] (QR) ، تکنولوژی گروهی[4] (GT) و مدیریت کیفیت جامع[5] (TQM) بدست آورند[58].

این مفاهیم ( برای مثال JIT و GT ) به بسیاری از شرکت ها در بدست آوردن سود اقتصادی کمک کرده می باشد. در سیسستم های JIT کار نباید نه زودتر و نه دیرتر تکمیل گردد، که به مسائل زمانبندی با هزینه های زودکرد و دیرکرد و تخصیص موعدهای تحویل منجر می گردد. در یک بازار رقابتی دیرکرد کارها با در نظر داشتن موعد تحویل آنها یک مقیاس عملکرد بسیار مهم برای محیط های تولید متنوع می باشد.

مسائل با تعیین موعد تحویل در 25 سال گذشته بعلت روشهای جدید مدیریت مانند مفاهیم JIT مورد توجه بسیار قرار گرفته می باشد. چنگ که کمک زیادی به مسائل زمانبندی و تخصیص موعد تحویل نمود اظهار می کند که تکمیل یک کار زودتر از موعد تحویل به معنی تحمیل هزینه های نگهداری موجودی غیر ضروری می باشد ، در حالیکه تکمیل یک کار دیرتر از موعد تحویل منجر به جریمه های قراردادی و از دست دادن اعتبار مشتری می گردد[33].

بطور جالب توجه هدف مسئله حداقل دیرکرد و زودکرد[6] (ET) کاملا با سیاست کنترل تولید JIT مطابقت دارد.مسئله ماشین های موازی از دو دیدگاه تئوری و عملی دارای اهمیت می باشند. از دیدگاه تئوری به این خاطر که تعمیمی از حالت تک ماشینه می باشد و از دیدگاه عملی به این جهت که در دنیای واقعی بسیارمعمول می باشد مورد توجه قرار گرفته شده می باشد.

مسئله به کارگیری ماشین های موازی از آنجا مورد توجه می باشد که اگر زمانبندی روی یک ماشین منجر به هزینه زیادی گردد ممکن می باشد در نظر گرفتن ماشین های بیشتر سبب کاهش هزینه گردد. ضمن این که مقدار دیرکرد یا زودکرد نیز می تواند با افزایش تعداد ماشین ها کاهش یابد. در این شرایط هزینه به کارگیری ماشین یا نگهداری ماشین اضافه می گردد که با حل مسئله بهینه سازی می توان تعیین نمود چه ماشین هایی به کار گرفته شوند و کدام کارها با چه توالی روی این ماشین ها انجام گردد.

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

بطور کلی، مسائل زمان­بندی به صورت مسائل بهینه­سازی محدودیت­دار اظهار می­شوند که در آنها به مطالعه تصمیمات مربوط به تخصیص ماشین­ها وتوالی پردازش کارها پرداخته می­گردد. درحالتی که تنها یک ماشین موجود می باشد، تعیین توالی پردازش کارها یک برنامه زمانی کامل را تشکیل می­دهد. مسائل تک­ماشینه با وجود سادگی ذاتی، سنگ­بنای درک فراگیر مفاهیم زمان­بندی را تشکیل می­دهند. درمقابل، زمان­بندی مسائل چند­ماشینه شامل سیستم­های موازی، سیستم­های متوالی و سیستم­های ترکیبی می­باشد. در سیستم­های موازی، هر یک از کارها با انجام یک عملیات همانند مسائل تک­ماشینه بر روی یکی از ماشین­های موازی موجود پردازش می­شوند و به­ دنبال آن تخصیص ماشین­ها به­ کارها موضوعیت پیدا می­کند. این درحالی می باشد که در سیستم های متوالی و ترکیبی، کارها با انجام چند عملیات بر روی ماشین­ها پردازش می­شوند و مسائل مربوطه ساختار نسبتا پیچیده­تری را تجربه می­کنند.

در این پژوهش، به مطالعه مسئله زمان­بندی ماشین­های موازی نامرتبط[7] به عنوان دسته مهمی از مسائل زمان­بندی که دارای اهمیت فراوان از نقطه­نظر تئوری و تجربی می باشد، پرداخته می­گردد. مسائل ماشین­های موازی نامرتبط حالت عمومیت­یافته مسائل تک­ماشینه و حالت خاصی از مسائل ماشین­های متوالی منعطف محسوب می­شوند. تکنیک­های به­کار رفته در بهینه­سازی این نوع مسائل با اعمال رویه­های ترکیبی در مسائل زمان­بندی پیچیده­تر بهره گیری می­شوند. در بخش­های آتی این فصل، تبیین تفصیلی مسئله مورد مطالعه این پژوهش ارائه می­گردد.

[1] Scheduling

[2] Just In Time

[3] Quick Response

[4] Group Technology

[5] Total Quality Management

[6] Earliness-Tardiness

[7] Unrelated Parallel Machine Scheduling

تعداد صفحه : 120

قیمت : 14700تومان

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

و در ضمن فایل خریداری شده به ایمیل شما ارسال می گردد.

پشتیبانی سایت :        ****       serderehi@gmail.com

در صورتی که مشکلی با پرداخت آنلاین دارید می توانید مبلغ مورد نظر برای هر فایل را کارت به کارت کرده و فایل درخواستی و اطلاعات واریز را به ایمیل ما ارسال کنید تا فایل را از طریق ایمیل دریافت کنید.

***  *** ***