ارائه روش ترکیبی فرا ابتکاری و تکنیک تولید ستون برای حل مساله زمان بندی جریان کارگاهی مختلط با در نظرگرفتن مجاز بودن بریدگی کارها

رشته صنایع یکی از مهمترین زیر شاخه های فنی و مهندسی شامل گرایش های متعددی در مقطع کارشناسی ارشد میباشد . در ادامه به معرفی نمونه پایان نامه ارشد مهندسی صنایع گرایش مهندسی سیستم های اقتصادی و اجتماعی با عنوان : ارائه روش ترکیبی فرا ابتکاری و تکنیک تولید ستون برای حل مساله زمان بندی جریان کارگاهی مختلط با در نظرگرفتن مجاز بودن بریدگی کارها   که در 92 صفحه در فرمت قابل ویرایش Word به نگارش در آمده میپردازیم .

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

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

تابع هدف مسئله، کمینه سازی زمان تکمیل برنامه زمانبندی می باشد. این مسئله جزء مسائل سخت NP-Hard می باشد. در روش های فرا ابتکاری ارائه شده، تکنیک تولید ستون با الگوریتم ژنتیک ( الگوریتم فرا ابتکاری (HG و الگوریتم بهینه سازی بر مبنای جغرافیای زیستی ( الگوریتم فرا ابتکاری (HB و الگویتم ترکیبی ژنتیک و بهینه سازی بر مبنای جغرافیای زیستی ( الگوریتم فرا ابتکاری (HH ترکیب شده است. نتایج محاسباتی در ارتباط با تحلیل عملکرد الگوریتم ها نشان می دهد که الگوریتم فرا ابتکاری  HH ، عملکرد مطلوبی در حل مسائل مختلف زمانبندی جریان کارگاهی دو مرحله ای نسبت به الگوریتم فرا ابتکاری هایHB  و  HG دارد و دو الگوریتم فرا ابتکاری HH و HB جواب های حل بهتری نسبت به الگوریتم فرا ابتکاری HG  به دست می آورند.

كلمات كليدي :

جریان کارگاهی مختلط ; زمانبندی کارهای دارای بریدگی؛ محدودیت های منابع ; الگوریتم تولید ستون ؛ الگوریتم های فرا ابتکاری ; الگوریتم ژنتیک ؛ الگوریتم بهینه سازی بر مبنای جغرافیای زیستی ؛ الگویتم ترکیبی ژنتیک و بهینه سازی بر مبنای جغرافیای زیستی.

Abstract :

In this paper, a heuristic is proposed for solving the problem of scheduling in a two-stage flowshop with parallel unrelated machines and additional renewable resources at the first stage and a single machine at the second stage. Resource requirements are arbitrary integers. The availability of additional resources is limited at every moment. The objective is the minimization of makespan. The problem is NP-hard. The proposed heuristic combines column generation technique with a genetic algorithm (the heuristic algorithm HG) or a biogeography  based optimization algorithm (the heuristic algorithm HB) or a hybrid algorithm of genetic algorithm and biogeography  based optimization algorithm (the heuristic algorithm HH).

The computational experiment  results of the performance analysis show that the heuristic algorithm  HH outperforms HG and HB for the different hybrid flow shop scheduling problems and that both the heuristic algorithms HH and HB yield good quality solutions than the heuristic algorithm HG.

Keywords :

Hybrid flowshop , Preemptive scheduling , Resource constraints , Column generetion algorithm,Heuristic algorithms , Genetic algorithm  , Biogeography  based optimization algorithm , Hybrid algorithm of genetic algorithm and biogeography  based optimization algorithm.

ضرورت انجام تحقیق

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

فهرست مطالب حل مساله زمان بندی جریان کارگاهی مختلط

 فصل1-بیان مسئله………………………………………………………1

1-1-مقدمه…………………………………………………….2

1-2-   تعریف مسئله…………………………………………………3

1-3-   فرضیات مسئله…………………………………………………4

1-4-   ضرورت انجام تحقیق…………………………………………….4

1-5-   اهداف تحقیق……………………………………………….5

1-6- جمع بندی……………………………………………………………………5

فصل2-مرور ادبیات و پیشینه تحقیق…………………………………………………7

2-1-  مقدمه……………………………………………………………………….8

2-2-  مرور ادبیات مسئله………………………………………………………….9

   2-3-مرور ادبیات الگوریتم تولید ستون…………………………………………………….13

2-3-1- معرفی الگوریتم تولید ستون…………………………………………………………13

2-3-2- ساختار الگوریتم تولید ستون ………………………………………………….15

2-4-   مرور ادبیات الگوریتم ژنتیک…………………………..18

2-4-1-   معرفی الگوریتم ژنتیک………………………………………………………..18

2-4-2-   فاکتورهای الگوریتم ژنتیک………………………………………………19

2-4-3-   ساختار کلی الگوریتم ژنتیک…………………………………20

2-5-   مرور ادبیات الگوریتم بهینه سازی بر مبنای جغرافیای………………………21

2-5-1-   بهینه سازی بر مبنای جغرافیای زیستی………………………………21

2-5-2-   مدل ریاضی جغرافیای زیستی………………………………………24

2-5-3-   ساختار کلی بهینه سازی بر مبنای جغرافیای زیستی…………………..28

2-5-3-1-   مهاجرت………………………………………………28

2-5-3-2-   جهش…………………………………………..29

2-5-4-   الگوریتم و تعاریف BBO

2-6- مرور ادبیات الگوریتم ترکیبی ژنتیک و بهینه سازی بر مبنای جغرافیای زیستی………………………..35

2-6-1- معرفی الگوریتم فرا ابتکاری ترکیبی ژنتیک و بهینه سازی بر مبنای جغرافیای زیستی……………………35

2-7-  جمع بندی………………………………35

فصل 3- ارائه یک مدل ریاضی، یک الگوریتم ژنتیک و یک الگوریتم بهینه سازی بر مبنای جغرافیای زیستی برای حل مساله………..37

3-1-   مقدمه……………………………………………..38

3-2-   شرح مسئله…………………………………………..38

3-3- روش حل مسئله جریان کارگاهی دو مرحله ای ………………………….39

3-4- الگوریتم های فراابتکاری………………………………………………………………..40

3-5- حل مسئله مرحله ی اول جریان کارگاهی دو مرحله ای در مرحله اول …………………………………………..42

3-5-1- فرمول بندی مسئله……………………………………………………………………………………………………………42

3-5-2- الگوریتم تولید ستون……………………………………………………………………………………………………….44

3-6- یافتن زمانبندی جریان کارگاهی دو مرحله ای با حداقل زمان تکمیل کارها با استفاده از الگوریتم های فرا

ابتکاری…………………………………………………………………………………………………………………………46

3-6-1- ارائه الگوریتم ژنتیک برای یافتن زمانبندی با حداقل زمان تکمیل کارها…………………………………. 47

3-6-1-1- روش نمایش جواب مسئله……………………………………………………………………………………………47

3-6-1-2- ايجاد جمعيت اوليه…………………………………………………………………………………………………….48

3-6-1-3- تابع برازش ………………………………………………………………………………………………………………48

3-6-1-4-  عملگرهای ژنتيك……………………………………………………………………………………………………49

3-6-1-4-1- عملگرهاي تقاطعي………………………………………………………………………………………………..49

3 -6-1-4-1-1- انتخاب بر اساس تورنامنت………………………………………………………………………………….50

3-6-1- 4-1-2- روش ترتیب …………………………………………………………………………………………………..50

3-6-1-4-2- عملگرهاي جهشي……………………………………………………………………………………………….. 51

3-6-1-4-2-1- جابجايي………………………………………………………………………………………………………..52

3-6-1-5- ایجاد تغییر در جمعیت برای تأخیر در همگرایی……………………………………………………………………….. 53

3-6-1- 6- مراحل الگوریتم ژنتیک به کار گرفته شده………………………………………………………………………53

3-6-2- ارائه الگوریتم بهینه سازی بر مبنای جغرافیای زیستی برای یافتن زمانبندی با حداقل زمان تکمیل   کارها……………………………………………………………………………………………………………………………………………54

   3-6-2-1- مهاجرت………………………………………………………………………………………………………………….55

   3-6-2-2- جهش……………………………………………………………………………………………………………………..56

   3-6-2-3- الگوریتم BBO ………………………………………………………………………………………………………57

3 -6-3- ارائه الگوریتم ترکیبی دو الگوریتم ژنتیک و بهینه سازی جغرافیای زیستی ……………………………… 60

3 -6-3-1- ساختار الگوریتم فرا ابتکاری ترکیبی ژنتیک و بهینه سازی بر مبنای جغرافیای زیستی………………60

3-6-3-2- عملگرهای الگوریتم فرا ابتکاری ترکیبی ژنتیک و بهینه سازی بر مبنای جغرافیای زیستی…………….61

3-6-4- جمع بندی………………………………………………………………………………………………………………………..61

فصل4- تجزیه و تحلیل نتایج…………………………………………………………………………………….62

4-1-   مقدمه……………………………………………………………………………………………………………………………..63

4-2-   روش تولید داده ها برای مسائل…………………………………………………………………………………………..63

4-3- تنظیم پارامترهای الگوریتم های فرا ابتکاری…………………………………………………………………………….63

4-4- مثال عددی…………………………………………………………………………………………………………………………………………65

4-5- اجرای الگوریتم ها و تجزیه و تحلیل آماری……………………………………………………………………………….68

4-5-1- نتایج محاسباتی………………………………………………………………………………………………………………69

4-5-2- تحلیل نتایج بهترین مقدار تابع هدف………………………………………………………………………………….71

4-5-3- تحلیل نتایج اولین زمان رسیدن به بهترین مقدار تابع هدف……………………………………………………..75

4-6- نتیجه گیری……………………………………………………………………………………………………………………….78

 فصل5- نتیجه گیری و پیشنهادات آتی………………………………………………………………………80

  5-1- نتیجه گیری………………………………………………………………………………………………………………………..81

5-2- پیشنهادات برای تحقیقات آتی………………………………………………………………………………………………..82

ضمائم

منابع

 فهرست جداول

جدول 4-1 پارامترهای مورد نیاز الگوریتم های ژنتیک و بهینه سازی جغرافیای زیستی……………………………………65

جدول 4-2 نتایج به دست آمده از اجرای الگوریتم ها بر روی مسئله با 60 کار و 2 ماشین……..……………………………66

جدول 4-3 مقایسه نتایج به دست آمده از اجرای الگوریتم ها از نظر بهترین مقدار تابع هدف و زمان رسیدن بر روی مسائل نمونه ……………………………………………………………………………………………………………………………………………………..70

جدول 4-4 مقایسه نتایج به دست آمده از RDI اجرای الگوریتم ها از نظر بهترین مقدار تابع هدف بر روی مسائل نمونه……………………………………………………………………………………………………………………………………………71

فهرست شکل ها

شکل 2-1- شکل شماتیک تجزیه مسئله اصلی در الگوریتم تولید ستون………………………………………………………………51

شکل 2-2- ساختار کلی الگوریتم تولید ستون……………………………………………………………………………………………..17

شکل 2-3 ساختار کلی الگوریتم ژنتیک……………………………………………………………………………………………21

شکل 2-4-  رابطه ی بین افزایش گونه ها و نرخ های مهاجرت به درون و برون………………………………………..24

شکل 2-5رابطه ی بین افزایش گونه ها و نرخ های مهاجرت زمانیکه ماکزیمم نرخ آنها………………………………26

شکل2-6 روش اصلاح سکونتگاه…………………………………………………………………………………………………….32

شکل 2-7  موتاسیون برای BBO……………………………………………………………………………………………………………33

شکل 3-1   نمونه ای از توالی 8 زمانبندی جزئی (T=8 , n=8 , m=2)…………………………………………………48

شکل 3-2 ارائه الگوریتم BBO برای مساله ی جریان کارگاهی دو مرحله ای……………………………………………59

شکل 4-1 به دست آمده از اجرای الگوریتم ها بر روی مسئله نمونه با 60 کار و 2 ماشین………………..……………….67

شکل4-2 به دست آمده ازاجرای الگوریتم فرا ابتکاری ترکیبی HH بر روی مسئله نمونه با 60 کار و 2 ماشین..68

شکل4-3 خروجی به دست آمده از آنالیز واریانس برای بهترین مقدار تابع هدف……………………………………..72

شکل4-4 خروجی به دست آمده از آزمون توکی برای بهترین مقدار تابع هدف………………………………………………….74

شکل4-5 نمودار میانگین و فاصله اطمینان 95% برای بهترین مقدار تابع هدف……………………………………………75

شکل4-6 خروجی به دست آمده از آنالیز واریانس برای بهترین اولین زمان رسیدن به بهترین مقدار تابع هدف.76

شکل4-7 خروجی به دست آمده از آزمون توکی برای بهترین اولین زمان رسیدن به بهترین مقدار تابع هدف…77

شکل4-8 نمودار میانگین و فاصله اطمینان 95% برای اولین زمان رسیدن به بهترین مقدار تابع هدف……………….78

راهنمای خرید و دانلود فایل

برای پرداخت، میتوانید از کلیه کارتهای عضو شتاب  استفاده نمائید.

بعد از پرداخت آنلاین لینک دانلود فعال و نمایش داده میشود ، همچنین یک نسخه از فایل همان لحظه به ایمیل شما ارسال میگردد.

در صورت بروز  هر مشکلی،میتوانید از طریق تماس با ما  پیغام بگذارید و یا در تلگرام با ما در تماس باشید، تا شکایت شما مورد بررسی قرار گیرد.

برای دانلود فابل روی دکمه خرید و دانلود  کلیک نمایید.