وبلاگ

41

 

4-2. ساختار الگوریتم ژنتیک پیشنهادی41

 

4-2-1. ساختار کروموزوم41

 

4-2-2. جمعیت اولیه42

 

4-2-3. تابع برازش42

 

4-2-4. عملگر تقاطع43

 

4-2-5. عملگر جهش44

 

4-2-6. ارزیابی فرزندان45

 

4-2-7. جست و جوی محلی45

 

4-2-8. معیار توقف45

 

4-3.ساختار الگوریتم رقابت استعماری پیشنهادی46

 

4-4.  نتایج محاسباتی47

 

4-4-1. تنظیم پارامترها47

 

4-4-2. روش تاگوچی47

 

4-4-3. روش تاگوچی برای تنظیم الگوریتم ژنتیک49

 

4-4-4. روش تاگوچی برای تنظیم الگوریتم رقابت استعماری50

 

4-5. معیارهای عملکرد

 

4-5-1. شاخص زمان محاسباتی52

 

4-5-2. روش­های اندازه­گیری عملکرد الگوریتم­ها52

 

4-5-3. تحلیل نمودار زمان محاسباتی الگوریتم ژنتیک و رقابت استعماری55

 

4-6. جمع­ بندی56

 

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

 

5-1. جمع­ بندی59

 

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

 

ضمیمه یک60

 

ضمیمه دو65

 

منابع و مراجع71

 

 

 

 

 

لیست جدول­ها

 

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

 

جدول 3-1. داده­های مسئله اول برای کار و زمان                                                            18   

 

جدول 3-2. داده­های مسئله اول برای نرخ یادگیری                                                         18

 

جدول 3-3. داده­های مسئله اول برای نرخ استهلاک                                                        18

 

جدول 3-4. داده­های مربوط به زمان نگهداری برای مسئله اول                                           18        

 

جدول 3-5. داده­های مسئله دوم برای کار و زمان                                                           19

 

جدول 3-6. داده­های مسئله دوم برای نرخ یادگیری                                                        19

 

جدول 3-7. داده­های مسئله دوم برای نرخ استهلاک                                                        20

 

جدول 3-8. داده­های مربوط به زمان نگهداری برای مسئله دوم                                           20 

 

جدول 3-9. داده­های مسئله سوم برای کار و زمان                                                          21

 

جدول 3-10. داده­های مسئله سوم برای نرخ یادگیری                                                      21          

 

 

 

جدول 3-11. داده­های مربوط به زمان نگهداری برای مسئله سوم                                        21

 

جدول 3-12. داده­های مسئله سوم برای نرخ استهلاک                                                     22   

 

جدول 4-1. پارامترهای الگوریتم ژنتیک در سه سطح                                                      49

 

جدول 4-2.مقادیر بهینه برای پارامترهای GA50

 

جدول 4-3.پارامترهای الگوریتم ICAدر سه سطح 50

 

جدول 4-4. مقادیر بهینه برای پارامترهای ICA51

 

جدول 4-5. نتایج بدست­آمده از روش دقیق، الگوریتم ژنتیک و رقابت استعماری               53     

 

لیست شکل­ها

 

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

 

شکل 2-1. رویکردهای مدل­سازی اثر یادگیری                                                     9

 

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

 

شکل 3-2.تقاطع تک­نقطه­ای                                                                        29

 

شکل 3-3. تقاطع دو نقطه­ای                                                                        29

 

شکل 3-4. نحوه تخصیص کشورهای مستعمره به کشور استعمارگر                          32

 

شکل 3-5. حرکت خطی مستعمره در راستای استعمارگر                                      34

 

شکل 3-6. زاویه انحراف رسیدن کشور مستعمره به امپریالیسم                               34

 

شکل 3-7. مسیر انقلاب در یک کشور مستعمره                                                35

 

شکل 3-8 .جا­به­جایی قدرت مابین کشورهای استعمارگر و مستعمره36

 

شکل 3-9. سقوط امپراطوری­های ضعیف­تر37

 

شکل 4-1.ساختار دو بخش و نحوه کدگشایی کروموزوم42

 

شکل 4-2.نحوه عملکرد عملگرهای تقاطع44

 

شکل 4-3.نمایش و نحوه عملگر جهش45

 

شکل 4-4.مقادیر سطوح مختلف پارامترهای الگوریتم GA در نسبت S/N              49

 

شکل 4-5. مقادیر سطوح مختلف پارامترهای الگوریتم ICA در نسبت S/N            51

 

شکل 4-6.نمودار RPD مربوط به الگوریتم ژنتیک و رقابت  استعماری55

 

شکل 4-7. نمودار زمان محاسباتی الگوریتم ژنتیکو رقابت استعماری56

 

– نگاهی به مسئله ی زمان بندی

 

1-1.

 

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

 

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

 

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

 

[1] .Scheduling