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

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

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

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

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

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

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

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: مساله معیاری برای 5 كار و 5 ماشین.. 4

جدول ‏2‑1: نمایش برخی از محیط های مختلف کار در مسائل زمان بندی با پارامتر α  22

جدول ‏2‑2: نمایش بعضی از محدودیت های مسائل زمان بندی با پارامتر β  34

جدول ‏2‑3: نمایش بعضی از معیارهای به کار رفته در مسائل زمانبندی با پارامتر g  36

جدول ‏2‑4: احتمال انتخاب در روش چرخ گردان برای داده‌های فرضی   45

جدول ‏4‑1: پارامترهای ورودی الگوریتم پیشنهادی.. 80

جدول ‏4‑2: نتایج اجرای داده های تست جدول 4-1.. 81

فهرست تصاویر

شکل ‏2‑1: مساله معیاری برای 5 کار و 5 ماشین.. 5

شکل ‏2‑1: رابطه تقذم برای n کار.. 25

شکل ‏2‑2: مساله 3 کار.. 26

شکل ‏2‑3: نمونه اول زمانبندی.. 26

شکل ‏2‑4: نمونه ای دیگر از زمانبندی.. 26

شکل ‏2‑5: قاعده جانسون.. 27

شکل ‏2‑6: مساله 3 کار و 3 ماشین.. 30

شکل ‏2‑7: نمودار گانت بر طبق ماشین.. 30

شکل ‏2‑8: نمودار گانت بر اساس كار.. 31

شکل ‏2‑9: تكنیک بكار برده شده برای مسائل job shop. 31

شکل ‏2‑10: دسته بندی استراتژی‌های جستجو.. 39

شکل ‏2‑11: مراحل کلی الگوریتمهای تکاملی.. 40

شکل ‏2‑12: نمایش کروموزوم به صورت درختی.. 43

شکل ‏2‑13: احتمال انتخاب در روش چرخ گردان.. 46

شکل ‏2‑14: احتمال انتخاب در روش رتبه بندی.. 47

شکل ‏2‑15: انتخاب مسابقه‌ای.. 48

شکل ‏2‑16: عملگر تبادل تک نقطه ای.. 49

شکل ‏2‑17: عملگر تبادل دو نقطه ای.. 50

شکل ‏2‑18: عملگر معکوس سازی.. 51

شکل ‏2‑19: عملگر حذف و کپی.. 51

شکل ‏2‑20: عملگر حذف و تولید مجدد.. 52

شکل ‏2‑21: مراحل الگوریتم GA-ACO.. 57

شکل ‏2‑22: عملگر مبتنی بر کار.. 58

شکل ‏2‑23: عملگر جهش شیفتی.. 58

شکل ‏2‑24: یک کروموزوم نمونه در الگوریتم GA-Fuzzy. 59

شکل ‏2‑25: یک کروموزوم نمونه در الگوریتم HGA.. 59

شکل ‏2‑26: فلوچارت الگوریتم HGA.. 60

شکل ‏2‑27: یک کروموزوم نمونه در الگوریتم GADG.. 61

شکل ‏3‑1: فلوچارت الگوریتم پیشنهادی.. 65

شکل ‏3‑2: یک کروموزوم نمونه.. 66

شکل ‏3‑3: نگهداری ماشین وابسته به سن ماشین.. 67

شکل ‏3‑4: یک کروموزوم نمونه با در نظر گرفتن نگهداری ماشین.. 68

شکل ‏3‑5: نمودار گانت شکل 3-4.. 68

شکل ‏3‑6: ایجاد جمعیت اولیه با بهره گرفتن از ویژگی چند جمعیتی.. 69

شکل ‏3‑7: عملگر تبادل دو نقطه ای.. 72

شکل ‏3‑8: عملگر تبادل تک نقطه ای.. 73

شکل ‏3‑9: عملگر تبادل چند  نقطه ای.. 74

شکل ‏3‑10: عملگر جهش دو نقطه ای.. 77

شکل ‏4‑1: نمودار مقایسه بهترین شایستگی الگوریتم ها برای داده تست 1   82

شکل ‏4‑2: نمودار مقایسه بهترین شایستگی الگوریتم ها برای داده تست 3   82

شکل ‏4‑3: نمودار بهترین شایستگی الگوریتم ها برای داده تست 4   83

شکل ‏4‑4: پراکندگی جمعیت اولیه برای داده تست 2.. 83

شکل ‏4‑5: پراکندگی جمعیت اولیه برای داده تست 4.. 84

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

1-1   مقدمه

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

1-2   بیان مسئله

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

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