بر روشهای حل در محیط ماشینهای موازی.. 19

2-5- مسائل چند هدفه. 20

2-6- روشهای حل مسائل بهینهسازی چندهدفه. 23

بر الگوریتم NSGA-II 26

بر الگوریتم فراابتکاری تکاملی DE. 28

بر روشهای ارزیابی.. 30

2-7-1- نسبت خطا 31

2-7-2- منطقه زیر پوشش دو مجموعه. 31

2-7-3- فاصله عمومی.. 32

2-7-4- نسبت فوق مساحت… 32

2-7-5- فاصله‌گذاری.. 33

2-7-6- فاصله از نقطه ایده‌آل.. 33

2-7-7- گسترش… 34

2-7-8- بیشترین گسترش… 34

2-8- جمعبندی.. 35

فصل سوم: مدل ریاضی و روش حل پیشنهادی.. 36

3-1- مقدمه. 37

3-2- مدل کارها و عملیات.. 37

3-3- مدل ماشینها و پارامترهای مربوط به آنها 38

3-4- اهداف.. 38

3-5- مفرضات مسأله. 40

3-6- محدودیتهای مسأله. 40

3-7- شرح مسأله و ارائه مدل.. 41

3-8- مدل ریاضی پیشنهادی.. 42

3-9- تضاد موجود بین تابع هدفها 44

3-10- روش پیشنهادی حل مسأله مورد نظر. 44

3-10-1- ساختار کلی الگوریتم تکاملی DE. 45

3-10-2- ساختار پیشنهادی الگوریتم DE. 48

3-10-2-1- ساختار كلی روش پیشنهادی DE. 48

3-10-2-2- عملگر جهش…. 51

3-10-2-3- عملگر تقاطع. 52

3-10-2-4- عملگر انتخاب یا بازسازی.. 53

3-10-2-5- به روز رسانی آرشیو پارتو. 54

3-10-2-6- رویه بهبود. 54

3-10-2-7- انتخاب جواب.. 55

3-10-3- ساختار الگوریتم حل NSGA-II 55

3-10-3-1- روش سریع مرتبسازی جوابهای مغلوب NSGA-II 56

3-11- جمعبندی.. 60

فصل چهارم: نتایج محاسباتی.. 61

4-1- مقدمه. 62

4-2- اعتبار سنجی مدل.. 62

4-3- جبهه پارتو. 63

4-4- تنظیم پارامتر با استفاده از روش سطح پاسخ (RSM) 65

4-5- شاخصهای مقایسه. 68

4-6- نتایج مقایسهای.. 68

4-7- مقایسه زمان اجرا 72

4-8- جمعبندی.. 74

فصل پنجم: نتیجهگیری و پیشنهادها 75

5-1- نتیجهگیری.. 76

5-2- پیشنهادهای آتی.. 76

منابع و مراجع.. 78

پیوستها 83

پ 1- مدل ریاضی ارائه شده در نرمافزار GAMS. 84

پ 2- کد نوشته شده در محیط Matlab برای دو روش حل DE و NSGA-II و روشهای مقایسه آنها 88

چکیده لاتین.. 106

فهرست جداول:

عنوان شماره صفحه شماره صفحه

جدول 4-1- مفروضات اصلی کد نوشته شده در محیط GAMS. 62

جدول 4-2- اعداد توابع هدف.. 64

جدول 4-3- پارامترهای تعیین شده برای روشهای حل.. 67

جدول 4-4- نتایج مقایسهای دو الگوریتم DE و NSGA-II 70

جدول 4-5- زمانهای اجرا 73

فهرست اشکال:

عنوان شماره صفحه شماره صفحه

شکل 2-1- محیط متغیرهای تصمیم و فضای هدف… 21

شکل 2-2- مجموعه جوابهای مغلوب و غیرمغلوب… 22

شکل 2-3- بررسی وظیفه اول الگوریتم های چندهدفه. 25

شکل 2-4- بررسی وظیفه دوم الگوریتمهای چندهدفه. 25

شکل 3-1- ساختار کلی الگوریتم. 46

شكل 3-2- نمای كلی الگوریتم DE تلفیقی.. 48

شكل 3-3- نحوه نمایش جواب.. 49

شکل 3-4- ساختار کلی VNS. 55

شکل 3-5- میزان مغلوبیت جوابها 56

شکل 3-6- برتری جوابها در سطح اول.. 57

شکل 3-7- برتری جواب با فاصله ازدحام بیشتر. 57

شکل 3-8- محاسبه فاصله ازدحام برای جواب i 58

شکل 3-9- NSGA-II و عملگر مسابقهای دودویی.. 58

شکل 3-10- ساختار کلی الگوریتم NSGA-II 59

شکل 4-1- جواب حل مدل مورد نظر در محیط GAMS. 63

شکل 4-2- جبهه پارتو برای 50 جواب مختلف.. 65

شکل 4-3- نتیجه حاصل از استفاده از روش RSM برای الگوریتم حل DE. 66

شکل 4-4- نتیجه حاصل از استفاده از روش RSM برای الگوریتم حل NSGA-II 67

شکل 4-5- نمودار مقایسهای شاخص کیفیت برای دو الگوریتم DE و NSGA-II 71

شکل 4-6- نمودار مقایسهای شاخص فاصلهگذاری برای دو الگوریتم DE و NSGA-II 71

شکل 4-7- نمودار مقایسهای شاخص پراکندگی برای دو الگوریتم DE و NSGA-II 72

شکل 4-8- نمودار زمانهای اجرا 73

فصل اول

کلیات تحقیق

1-1- مقدمه

در جهان رقابتی حاضر، توالی و زمانبندی مناسب، ضرورتی برای بقا در فضای بازار است. زمانبندی، ابزاری است كه استفاده از منابع در دسترس را بهینه میكند. منابع و كارها در زمانبندی ممكن است انواع گوناگونی داشته باشد [1]. با توسعه جهان صنعتی، منابع بحرانیتر میشوند. زمانبندی این منابع، افزایش كارایی و بهرهبرداری از ظرفیت، كاهش زمان مورد نیاز برای تكمیل كارها و نهایتاً افزایش سوددهی یك سازمان را به دنبال خواهد داشت. در نتیجه، زمانبندی مناسب و مؤثر منابع مانند ماشینها، نیروی انسانی و غیره در محیط به شدت رقابتی امروز الزامیست [1،2].

زمانبندی یك فرآیند تصمیمگیری است كه نقش مهمی را در اكثر صنایع تولیدی و خدماتی ایفا میكند. زمانبندی در تداركات، تولید، حمل و نقل، توزیع، پردازش اطلاعات و ارتباطات كاربرد دارد. عمل زمانبندی در یك سازمان، از مدلها و روشهای ریاضی یا روشهای ابتكاری برای تخصیص منابع محدود به كارهای در حال جریان استفاده میكند. تخصیص درست منابع، سازمان را برای بهینه كردن اهداف و به دست آوردن آرمانها توانمند میسازد. منابع میتوانند ماشینها در كارگاه تولیدی، خطوط هوایی در فرودگاه، كارگران در پروژه ساختمانی یا واحدهای پردازشی در محیط كامپیوتر باشند. كارها نیز میتوانند عملیات در كارگاه تولیدی، پرواز و فرود در فرودگاه، مراحل در یك پروژه ساختمانی و برنامههای كامپیوتری در محیط كامپیوتر باشند. هر كار دارای ویژگیهایی همچون سطح اولویت، زمان آماده به كار بودن و موعد تحویل[1] میباشد. تابع هدف همچنین میتواند به صورتهای مختلفی مانند حداقل كردن زمان اتمام كل كارها یا حداقل كردن تعداد كارهای دارای دیركرد در نظر گرفته شود [3].

مسأله زمانبندی ماشین، زمینهای غنی و مناسب برای تحقیقات است كه كاربردهای فراوانی در تولید، پشتیبانی، معماری كامپیوتر و مانند این را به همراه خواهد داشت. حوزه مورد بررسی در این پایاننامه، مسأله ماشینهای موازی[2] است. زمانبندی ماشینهای موازی در ارتباط با چگونگی زمانبندی گروهی از كارها بر روی تعدادی از ماشینها به منظور اطمینان از پردازش كارها در مدت زمانی منطقی میباشد. ماشینهای موازی از دو دیدگاه تئوری و عملی دارای اهمیت میباشند. از دیدگاه تئوری، تعمیمی از تك ماشین[3] و حالت خاصی از محیط جریان كارگاهی انعطافپذیر[4] است. از دیدگاه عملی به این جهت كه در دنیای واقعی بسیار معمول هستند دارای اهمیت میباشند [1]. علاوه بر این، روشهایی كه در محیط ماشینهای موازی مورد استفاده قرار میگیرند، قابل استفاده در فرآیندهای تجزیه برای سیستمهای چند مرحلهای نیز میباشد. زمانبندی صنایع به طور كلی از كاربرد مدل ماشینهای موازی سود برده است. ماشینهای موازی توانایی انجام عملیات یكسان با داشتن ظرفیتها و استعدادهای متفاوت را دارا میباشند. در واقع ماشینهای موازی، افزایش ظرفیت و انعطافپذیری سیستم را با پردازش كارهای متفاوت به همراه خواهند داشت.

موضوعات: بدون موضوع لینک ثابت

فرم در حال بارگذاری ...

فید نظر برای این مطلب