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

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

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

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

رشته : فناوری اطلاعات

عنوان/موضوع:

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

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

جناب آقای دکتر جواد وحیدی – جناب آقای دکتر جواد رضاییان زیدی

استاد مشاور:

جناب آقای دکتر بابک شیرازی

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

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

فهرست مطالب:

1   فصل اول مقدمه و کلیات پژوهش………………… 1

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

1-2     اظهار مسئله………………… 2

1-3   ضرورت پژوهش…………………. 5

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

1-5     نوآوری پژوهش…………………. 6

1-6     پرسشهای اصلی پژوهش………………… 6

1-7   فرضیه های پژوهش…………………. 7

1-8     زمینه های کاربردی…………………. 7

1-8-1     تخصیص گیت در یک فرودگاه……………….. 8

1-8-2     زمانبندی در یک واحد پردازش مرکزی…………………. 9

1-8-3     زمانبندی در پالایشگاه نفت…………………. 10

1-8-4     کارخانه تولید پاکت کاغذی…………………. 10

1-8-5     کارخانه تولید تجهیزات لامپ های صنعتی…………… 11

1-9     تعریف کلمات کلیدی…………………. 12

1-10     ساختار پایان نامه………………… 14

2     فصل دوم ادبیات و پیشینه پژوهش…………………. 15

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

2-2      تعریف مربوط به زمانبندی…………………. 16

2-3       زمانبندی از دیدگاهی دیگر………………… 18

2-4       نظریه زمانبندی…………………. 19

2-5       مروری بر مدل های زمان بندی…………………. 20

1-5-2       چارچوب و نمادها ………………..20

2-5-2       ترکیب ماشین ها (محیط های کار)……………….. 21

2-5-3       مدل های تک ماشینه………………… 22

2-5-4       مدل های ماشین موازی…………………. 23

2-5-5       مدل های جریان کارگاهی…………………. 24

2-5-6       مدل های کار کارگاهی…………………. 28

2-5-7       مدل های کارگاه باز………………… 31

2-5-8       مدل های کارگاه وابسته………………… 33

2-5-9       مدل های پردازش دسته ای…………………. 33

2-5-10     مدل های خط مونتاژ………………… 33

2-5-11     مدل های خط مونتاژ ترکیبی…………………. 34

2-6       محدودیت های زمانبندی…………………. 34

2-6-1       معیارهای ارز یابی عملکرد………………… 36

2-7       الگوریتم ژنتیک………………….. 38

2-7-1       تکنیک‌های حل مسائل بهینه سازی…………………. 38

2-7-2       صورت کلی الگوریتم ژنتیک………………….. 40

2-7-3      تعاریف………………….. 41

2-7-4       نمایش کروموزوم………………… 41

2-7-4-1       نمایش باینری…………………. 41

2-7-4-2       نمایش جایگشتی…………………. 42

2-7-4-3       نمایش مقداری…………………. 42

2-7-4-4       نمایش درختی…………………. 43

2-7-5       تابع شایستگی…………………. 43

2-7-6       عملگر انتخاب…………………. 44

2-7-6-1       انتخاب تصادفی………………… 44

2-7-6-2       انتخاب چرخ گردان……………….. 44

2-7-6-3       انتخاب رتبه بندی…………………. 46

2-7-6-4       انتخاب نخبه‌گرا ………………..47

2-7-6-5       انتخاب مسابقه‌ای…………………. 47

2-7-7       عملگر تبادل………………… 48

2-7-7-1       عملگر تبادل تک نقطه ای…………………. 48

2-7-7-2       عملگر تبادل دو نقطه ای…………………. 49

2-7-8       عملگر جهش………………….. 50

شما می توانید مطالب مشابه این مطلب را با جستجو در همین سایت بخوانید                     

2-7-8-1       عملگر معکوس سازی…………………. 51

2-7-9      عملگر حذف و کپی…………………. 51

2-7-10       عملگر حذف وتولید مجدد………………… 52

2-7-11       پارامترهای الگوریتم ژنتیک………………….. 52

2-7-12       همگرایی…………………. 53

2-7-13       شرط خاتمه الگوریتم ژنتیک………………….. 53

2-7-14      مزایای الگوریتم ژنتیک………………….. 53

2-7-15      معایب الگوریتم ژنتیک………………….. 54

2-8       کارهای انجام شده ………………..55

2-8-1       الگوریتم ETPN-GA………………….

2-8-2       الگوریتم AFS Petri Net…………………

2-8-3       الگوریتم GA-ACO………………….

2-8-4       الگوریتم GA-Fuzzy…………………

2-8-5       الگوریتم HGA………………….

2-8-6       الگوریتم GADG………………….

2-8-7       الگوریتم های دیگر………………… 61

3       روش پژوهش…………………. 63

3-1         مراحل الگوریتم پیشنهادی…………………. 64

3-2         نمایش کروموزوم………………… 65

3-3         توضیح پارامتر نگهداری ماشین…………………. 67

3-4         ایجاد جمعیت اولیه………………… 68

3-5         شایستگی…………………. 70

3-6       انتخاب…………………. 71

3-7         عملگر تبادل………………… 71

3-7-1         عملگر تبادل دو نقطه ای…………………. 72

3-7-2         عملگر تبادل تک نقطه ای………………73

3-7-3         عملگر تبادل چند نقطه ای…………………. 74

3-8         عملگر جهش………………….. 77

3-9         تعویض جمعیت…………………. 78

3-10       شرط خاتمه………………… 79

4       محاصبات و یافته های پژوهش…………………. 79

4-1       پیاده سازی الگوریتمها……………….. 80

4-2       طراحی داده های تست و پارامترهای الگوریتم…….. 80

4-3       نتایج حاصل از شبیه سازی…………………. 81

5       نتیجه گیری و پیشنهادات………………… 86

فهرست منابع و مأخذ………………… 88

چکیده:

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

فصل اول: مقدمه و کلیات پژوهش

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

1-1- مقدمه

مسئله زمانبندی سیستم های باز یکی از مهمترین مسائل زمانبندی در دنیای مهندسی و صنعت می باشد. در این مسئله m ماشین و n کار هست. هرکار شامل تعداد معینی از عملیات می باشد. هر عملیات دارای زمان از پیش تعیین شده ای برای پردازش[1] بر روی ماشین متناظر خود می باشد. ترتیب پردازش این عملیات در زمان به انجام رسیدن همه کارها بسیار تاثیر گذار می باشد. پس هدف از حل این مسئله یافتن ترتیب عملیاتی می باشد که با کمترین مدت زمانبندی قابل پردازش باشد. در این راستا مقالات زیادی با بهره گیری از الگوریتم های ابتکاری[2] مختلف ارائه شده می باشد که از بین آنها الگوریتم ژنتیک[3] یکی از بهترین ها، شناخته شده می باشد. در این پایان نامه یک روش جدید برای حل مسئله زمانبندی با در نظر گرفتن پارامتر نگهداری ماشین[4] ها بر پایه الگوریتم ژنتیک با ویژگی چند جمعیتی[5] ارائه شده می باشد. نتایج تجربی نشان می­ دهد­ الگوریتم ارائه شده به جواب بهینه تری دست پیدا می­کند [77].

2-1- اظهار مسئله

مسئله زمانبندی سیستم باز یک مسئله زمانبندی مهم و جهانی می باشد و این مسئله به گونه وسیع در صنعت کاربرد دارد. این مسئله جزء مسائل سخت می باشد. این مسئله شبیه به مسئله زمانبندی مغازه کارها می باشد با این تفاوت که در هر کار[6] هیچ اولویتی بین فرایند یا عملیات هر کار وجود ندارد. در مسئله زمانبندی سیستم باز فضای راه حل به گونه قابل ملاحظه­ای بزرگتر از مسئله زمان بندی مغازه کارها می باشد و به نظر می­رسد که در کتاب ها و مقالات به آن کمتر توجه شده می باشد. توضیح مسئله سیستم باز توسط گراهام و همکارانش به این شکل باشد: یک تعداد کار به تعداد n (J1,J2, … , Jn) هست که روی یک سلسله ماشین به تعداد m (M1,M2, … , Mm) قابل پردازش می باشد، هر کار متشکل از m عملیات می باشد (Oij). که j=1 to m و i=1 to n و هر کدام از عملیات بایستی روی یک ماشین متفاوت برای یک زمان مشخص شده پردازش شوند. عملیات هر کار می تواند در هر ماشینی پردازش گردد اما در هر زمان نهایتا یک اقدام روی هر ماشین می تواند پردازش گردد و یک اقدام از هر کار می تواند در یک زمان پردازش گردد [77 ، 1].

شما می توانید تکه های دیگری از این مطلب را در شماره بندی انتهای صفحه بخوانید              

هدف مسئله زمانبندی سیستم باز بدست آوردن یک ترکیب امکان پذیر از سفارشات ماشین و کار تعیین شده می باشد که زمان کلی اتمام کارها در کمترین زمان ممکن باشد. در ادامه به اظهار چندین مثال که غیر از مسائل سیستم باز می باشد می پردازیم:

تعمیر کردن هواپیماهای بزرگ، که نیاز به تعمیر موتور و سیستم الکتریکی را دارد. این دو وظیفه (عملیات) ممکن می باشد در هر ترتیبی انجام گردد اما این غیر ممکن می باشد که این دو کار را با هم انجام دهیم. یا در مثالی دیگر یک گاراژ اتومبیل بزرگ با فروشگاه های اختصاصی را در نظر بگیرید. یک وسیله نقلیه ممکن می باشد به کار های زیر نیاز داشته باشد: تعمیر انباره لوله اگزوز، میزان کردن چرخ ها و تنظیم موتور که سه اقدام از یک کار ممکن می باشد به هر ترتیبی انجام شوند. به هر حال، مغازه های سیستم اگزوز، میزان کردن چرخ ها، و تنظیم موتور در ساختمان های مختلف هستند و پس انجام دو اقدام در یک زمان امکان پذیر نیست. در مسئله زمانبندی سیستم باز ما فرض می کنیم که چندین کار از این قبیل کار ها و چندین وسیله نقلیه که نیاز به تعمیر دارند را داریم، موارد دیگر می تواند شامل: کنترل کیفیت مرکزی، انتساب کلاس، معاینه فنی خودرو، مخابره ماهواره ای و بسیاری از موارد دیگر گردد [3].

در زیر یک مثال حل شده OSSP را نظاره می کنید:

در جدول هر کار شامل دقیقا یک عملکرد برای هر دستگاه می گردد. این معیارها به گونه کامل توسط یک مجموع منظم از زمان های پردازش m برای هر کار تعریف شده اند. برای مثال، جدول 1-1 یک مسئله معیاری 5*5 (5 کار و 5 ماشین) را نشان می دهد.

در مثال بالا عملکرد 4 از کار 1 بایستی به ماشین 4 برای 85 واحد از زمان پردازش برود و عملکرد 1 از کار 1 بایستی به ماشین 1 برای 64 واحد از زمان پردازش اختصاص یابد بدون هیچ محدودیتی در ترتیب آن که کدام کارها در چه زمانی پردازش شوند. مسئله، ایجاد یک راه حل معتبر با زمان کلی اتمام کارهای حداقل می باشد. شکل 1-1 یک برنامه زمان کلی اتمام کار حداقل300 را برای معیارهای ارائه شده در جدول 1-1 را نشان می دهد.

[1] Process

[2] Heuristic Search

[3] Genetic Algorithm

[4] Machine Maintenance

[5] Multi Generation

[6] Job

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

متن کامل را می توانید دانلود نمائید

زیرا فقط تکه هایی از متن پایان نامه در این صفحه درج شده (به گونه نمونه)

اما در فایل دانلودی متن کامل پایان نامه

 با فرمت ورد word که قابل ویرایش و کپی کردن می باشند

موجود می باشد

تعداد صفحه : 106

قیمت : چهارده هزار و هفتصد تومان