متن کامل پایان نامه مقطع کارشناسی ارشد رشته : صنایع

گرایش :سیستم های اقتصادی اجتماعی

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

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

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

 

پایان نامه

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

 

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

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

 

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

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

(بهار 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

شکل 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

قیمت : 17300تومان

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

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

پشتیبانی سایت :        ———- ****       [email protected]

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

*********  ********* *********