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

 

کلمات کلیدی: زمانبندی به­موقع، ماشین­های موازی یکنواخت، زمان آماده­سازی وابسته به توالی، تاثیر یادگیری و محدودیت مجموعه پردازش

فهرست مطالب

فصل اول: کلیات تحقیق.. 1

1-1. مقدمه. 2

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

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

1-4. مفروضات مسئله. 6

1-5. جنبه­های نوآوری تحقیق.. 6

1-6. محتویات تحقیق.. 7

فصل دوم: مرور ادبیات… 8

2-1. مقدمه. 9

2-2. زمان آماده­سازی وابسته به کار قبلی.. 10

2-3. تاثیر یادگیری.. 13

2-4. محدودیت مجموعه پردازش… 17

2-5. زمان­های زودکرد و دیرکرد 19

2-6. نتیجه­گیری.. 20

فصل سوم: مدل ریاضی.. 21

3-1. مقدمه. 22

3-2. تعریف مسئله. 22

3-3. مفروضات مسئله. 23

3-4. مدل پیشنهادی.. 24

3-5. اعتبارسنجی مدل. 27

3-6. پیچیدگی مسئله. 31

3-7. نتیجه گیری.. 33

فصل چهارم: الگوریتم­های پیشنهادی و نتایج محاسباتی.. 34

4-1. مقدمه. 35

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

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

4-2-2. کدگذاری.. 40

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

4-2-4. تابع شایستگی.. 41

4-2-5. عملگرهای ژنتیک… 41

4-2-5-1. عملگر انتخاب… 41

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

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

4-2-6. شرط توقف… 44

4-3. الگوریتم ازدحام ذرات… 45

4-3-1. ساختار کلی.. 45

4-3-2. مفاهیم پایه­ای الگوریتم ازدحام ذرات… 47

4-3-3. به­روز رسانی سرعت… 47

4-3-3-1. پارامتر شخصی c1 و پارامتر جمعی c2. 49

4-3-3-2. پارامتر وزن اینرسی.. 49

 

4-3-4. به­روز رسانی موقعیت… 49

4-4. تبرید شبیه­سازی­شده 50

4-4-1. مفاهیم الگوریتم تبرید شبیه­سازی­شده 52

4-5. الگوریتم­های پیشنهادی.. 54

4-5-1. تولید جامعه اولیه و نحوه­ی نمایش کروموزوم­ها 55

4-5-2. اجرای الگوریتم ژنتیک… 56

4-5-2-1. عملگر تقاطع. 57

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

4-5-3. اجرای الگوریتم بهینه­سازی ازدحام ذرات… 59

4-5-3-1. تعیین سرعت… 61

4-5-3-2. عمل جهش… 61

4-5-3-3. موقعیت جدید. 62

4-5-4. اجرای الگوریتم تبرید شبیه­سازی­شده 64

4-5-4-1. تعیین دمای اولیه. 65

4-5-4-2. تعیین دمای نهایی.. 66

4-5-4-3. روش کاهش دما 66

4-5-4-4. روش همسایگی.. 66

4-6. مجموعه داده­ها 67

4-7. تنظیم پارامترها 68

4-7-1. اندازه جامعه اولیه. 69

4-7-2. تقاطع. 71

4-7-3. نرخ جهش… 71

4-7-4. حداکثر تعداد نسل­ها 71

4-8. تنظیم پارامتر چندعاملی.. 72

4-9.  ارزیابی الگوریتم­ها 79

4-10. جمع­بندی.. 90

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

فهرست منابع.. 95

 

فهرست جداول

جدول 3-1. اطلاعات مسئله­ی ساخته شده 28

جدول 3-2. زمان­های آماده­سازی مسئله­ی ساخته شده 29

جدول 3-3. زمان پردازش(ثانیه) 29

جدول 3-4. موعدهای تحویل (ثانیه) و هزینه زودکرد و دیرکرد. 30

جدول 3-5. زمان آماده­سازی ماشین (ثانیه) 30

جدول 4-1. چیدمان کارها 56

جدول 4-2. خلاصه­ی داده­ها 68

جدول 4-3. پارامترهای کنترل کننده الگوریتم ژنتیک و محدوده­ی موثر آن. 71

جدول 4-4. فاکتورها و سطوح آن­ها 72

جدول 4-5. ترکیب فاکتورها و سطوح پاسخ مربوطه در آزمایشات چند­عاملی.. 73

جدول 4-6. ضرایب همبستگی تخمینی مدل برای نسبت­های SN… 74

جدول4-7. آنالیز واریانس برای نسبت­های SN… 74

جدول 4-8. ضرایب همبستگی تخمینی مدل برای میانگین پاسخ­ها 75

جدول4-9. آنالیز واریانس برای میانگین پاسخ­ها 75

جدول4-10.  پاسخ SN… 76

جدول4-11.  پاسخ میانگین­ها 76

جدول 4-12. مقادیر تنظیم شده­ی پارامترهای ژنتیک… 78

جدول 4-13. مقادیر تنظیم شده­ی پارامترهای تبرید شبیه­سازی­شده 78

جدول 4-14. مقادیر تنظیم شده­ی پارامترهای الگوریتم ازدحام ذرات… 78

جدول 4-15. خلاصه مسائل.. 79

جدول 4-16. مسائل با اندازه­ی کوچک… 80

جدول 4-17. مسائل با اندازه­ی متوسط.. 81

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

جدول 4-19. مقدار PRE و زمان حل برای سطح کوچک… 84

جدول 4-20. مقدار RPD و زمان حل برای سطح متوسط.. 85

جدول 4-21. مقدار RPD و زمان حل برای سطح بزرگ… 86

جدول 4-22. میانگین زمان حل و RPD برای تعداد مختلف کارها 88

جدول 4-23. مجموع مقایسه شده­ی پارامتر الگوریتم­ها 89

جدول 4-24. درصد جواب­های بهتر الگوریتم­ها 89

 

فهرست اشکال

شکل 3-1. سلسله مراتب پیچیدگی محیط­های کاری ]57[ 32

شکل 3-2. سلسله مراتب پیچیدگی توابع هدف ]57[ 32

شکل4-1. نمای کلی الگوریتم ژنتیک کلاسیک… 39

شکل 4-2. نمایش کروموزوم. 56

شکل 4-3. عملیات تقاطع. 58

شکل 4-4. جهش نوع اول. 58

شکل 4-5. جهش اول نوع دوم. 59

شکل 4-6. جهش دوم نوع دوم. 59

 شکل4-7. تغییر موقعیت ذره 62

شکل4-8. تغییر موقعیت ذره همراه با اصلاحیات… 63

 شکل4-9. تغییر موقعیت ذره با توجه به محدودیت پردازشی.. 64

 شکل4-10. کیفیت جواب­ها و اندازه­ی جامعه. 70

شکل4-11. زمان محاسباتی و اندازه­ی جامعه. 70

شکل4-12. پاسخ میانگین­ها 77

شکل4-13. پاسخ ضرایب SN… 77

شکل 4-14. نمودار میانگین و فواصل LSD… 87

شکل 4-15. RPD برای تعداد مختلف کارها 88

 

فصل اول
کلیات تحقیق

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

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

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

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

در این تحقیق، به بررسی مسئله زمانبندی ماشین­های موازی با سرعت­های مختلف[3] پرداخته می­شود. مسائل ماشین­های موازی با سرعت­های مختلف حالت عمومی یافته مسائل تک­ماشینه و حالت خاصی از مسائل ماشین­های متوالی منعطف محسوب می­شوند. در بخش­های آتی این فصل، شرح تفصیلی مسئله مورد بررسی این تحقیق ارائه می­شود.

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

در کارخانه­ها وقتی ماشین­­ها و دستگاه­­های جدید خریداری می­شوند و در کنار ماشین­های قدیمی قرار می­گیرند، تفاوت سرعت بین ماشین­های جدید و قدیمی بوجود می­آید که این تفاوت سرعت، مسئله­ی چندین ماشین با سرعت­های متفاوت را بوجود می­آورد.

در برخی از محیط­های کاری زمانبندی ماشین­های موازی با سرعت متفاوت، ممکن است که تمامی ماشین­ها نتوانند تمامی کارها را پردازش کنند که در این حالت هر کار توسط