2

1-1- مقدمه

2

1-2- مفهوم زمان­بندی

3

1-3- اهمیت و ضرورت زمان­بندی

4

1-4- طبقه­بندی و مفاهیم پایه مسایل زمان­بندی تولید

6

1-4-1- طبقه­بندی محیط­های تولیدی

8

1-4-2- خصوصیات کار و محدودیت­هایی که بر محیط اعمال می­شود

9

1-4-2-1-محدودیت رد یا پذیرش سفارشات

10

1-4-2-2- محدودیت دسترسی به ماشین­ها

12

1-4-3- توابع هدف و ویژگی­های آنها

14

1-4-3-1- نظام تولید بهنگام

15

1-5- بیان مساله جریان کارگاهی در نظر گرفته شده در این مطالعه

16

1-6- روش حل

17

1-7- اهداف تحقیق

17

1-8- نتیجه­گیری

19

فصل دوم : ادبیات تحقیق

20

2-1- مقدمه

20

2-2- بر ادبیات کارگاه گردش کاری

22

2-3- زمان­بندی و محدودیت دسترسی ماشین­ها

23

2-3-1- بر ادبیات مساله کارگاه گردش کاری با محدودیت دسترسی ماشین­ها

25

2-4- بر ادبیات محدودیت رد یا پذیرش سفارشات

27

فصل سوم : روش­های حل

28

3-1- مقدمه

28

3-2- تعریف مساله

29

3-3- مدل پیشنهادی

33

3-4-اعتبارسنجیمدل

34

3-5- پیچیدگی مساله

36

3-6- الگوریتم ژنتیک

37

3-6-1- واژگان الگوریتم ژنتیک

38

3-6-2- شمای کلی الگوریتم ژنتیک

39

3-6-3- مفاهیم الگوریتم ژنتیک

39

3-6-3-1- کدگذاری

42

3-6-3-2- جامعه اولیه

42

3-6-3-3- عملیات ژنتیک

47

3-6-3-4- تابع برازش

47

3-6-3-5- شرط توقف الگوریتم

48

3-7- پیاده­سازی الگوریتم ژنتیک پیشنهادی

48

3-7-1- کدگذاری الگوریتم

49

3-7-2- ایجاد جمعیت اولیه

50

3-7-3- تابع برازش

50

3-7-4- عملگرهای ژنتیک

50

3-7-4-1- عملگر تقاطع

53

3-7-4-2- عملگر جهش

54

3-7-4-3- عملگر نخبه­گرایی

54

3-7-4-4- معیار توقف

54

3-7-4-5- جستجوی موضعی

55

3-8- تبرید شبیه­سازی شده

57

3-8-1- مفاهیم الگوریتم

57

3-8-1-1- جواب همسایگی

57

3-8-1-2- دما

57

3-8-1-3- الگوی کاهش دما

58

3-8-1-4- احتمال پذیرش جواب­ها

58

3-8-1-5- شرط توقف

59

3-9- پیاده­سازی الگوریتم شبیه­سازی تبرید پیشنهادی

59

3-9-1- روش نمایش جواب

59

3-9-2- جواب اولیه

59

3-9-3- ساختار همسایگی

60

3-9-4- برنامه انجماد

60

3-9-5- قاعده توقف

61

3-10- نتیجه­گیری

62

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

63

4-1- مقدمه

63

4-2- تولید مسایل نمونه

64

4-3- تنظیم پارامتر

66

4-3-1- تنظیم پارامتر الگوریتم ژنتیک

67

4-3-1-1- طراحی آزمایشات چند عاملی

72

4-3-2- تنظیم پارامتر الگوریتم شبیه­سازی تبرید

73

4-3-2-1- طراحی آزمایشات چند عاملی برای الگوریتم شبیه­سازی تبرید

79

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

85

4-5- جمع­بندی

86

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

87

5-1- نتیجه­گیری

87

5-2- پیشنهادها

89

فهرست مراجع

فهرست جدول­ها
جدول4-1- حدود پارامترهای مسایل تولید شده	64
جدول4-2- پارامترهای کنترل­کننده الگوریتم ژنتیک و محدوده موثر آنها	67
جدول4-3- ترکیبات عامل­ها و سطوح پاسخ نرمال شده در آزمایشات چند عاملی الگوریتم ژنتیک	68
جدول4-4- پاسخ نسبت ­های S/N در الگوریتم ژنتیک	68
جدول 4-5- پاسخ میانگین­ها در الگوریتم ژنتیک	68
جدول 4-6- مقادیر بهینه­ی پارامترهای کنترل کننده الگوریتم ژنتیک	70
جدول 4-7- پارامترهای کنترل کننده الگوریتم شبیه­سازی تبرید و محدوده موثر آنها	74
جدول4-8- ترکیبات عامل­ها و سطوح پاسخ نرمال شده در آزمایشات چند عاملی الگوریتم شبیه­سازی تبرید	74
جدول4-9- پاسخ نسبت­های S/N در الگوریتم شبیه­سازی تبرید	75
جدول 4-10- پاسخ میانگین­ها در الگوریتم شبیه­سازی تبرید	75
جدول 4-11- مقادیر بهینه­ی پارامترهای کنترل کننده الگوریتم شبیه­سازی تبرید	77
جدول 4-12- حل مسایل کوچک با روش شاخه و کران و الگوریتم­های فراابتکاری پیشنهادی	79
جدول 4-13- مقایسه جواب­های الگوریتم­های فراابتکاری در ده تکرار برای مسایل مختلف	82
جدول 4-14- مقایسه RPD% برای مسایل مختلف	84

فهرست شکل­ها
شکل 1-1- تقسیم­بندی و نحوه ارتباط مسایل زمان­بندی	5
شکل3-1- کدگذاری ترتیبی	39
شکل3-2- کدگذاری ارزشی	40
شکل3-3- کدگذاری درختی	40
شکل3-4- فضای کدگذاری و فضای جواب	41
شکل3-5- موجه­بودن و قانون­مندی کروموزوم­ها	42
شکل3-6- تقاطع تک نقطه­ای	46
شکل3-7- تقاطع دو نقطه­ای	46
شکل3-8- ساختار کلی الگوریتم ژنتیک	48
شکل3-9- نمایش کروموزوم	49
شکل3-10- انتخاب دو کروموزوم والد	51
شکل3-11- مرحله دوم عملگر تقاطع برای ایجاد توالی	51
شکل3-12- مرحله سوم عملگر تقاطع برای ایجاد توالی	52
شکل3-13- مرحله چهارم عملگر تقاطع برای ایجاد توالی	52
شکل3-14- عملگر تقاطع برای ایجاد بخش دوم کروموزوم	53
شکل3-15- عملگر جهش برای بخش اول کروموزوم	53
شکل3-16- عملگر جهش برای بخش دوم کروموزوم	54
شکل3-17- شبه­کد الگوریتم شبیه­سازی تبرید	56
شکل3-18- عملگرهای تغییر توالی در الگوریتم شبیه­سازی تبرید پیشنهادی	60
شکل4-1- میانگین نسبت S/N در الگوریتم ژنتیک	69
شکل4-2- پاسخ میانگین در الگوریتم ژنتیک	70
شکل4-3- میانگین نسبت S/N در الگوریتم ژنتیک برای مسایل در اندازه­های متوسط	71
شکل4-4- پاسخ میانگین­ها در الگوریتم ژنتیک برای مسایل در اندازه­های متوسط	72
شکل4-5- میانگین نسبت S/N در الگوریتم شبیه­سازی تبرید	76
شکل4-6- پاسخ میانگین­ها در الگوریتم شبیه­سازی تبرید	76
شکل4-7- میانگین نسبت S/N در الگوریتم شبیه­سازی تبرید برای مسایل در اندازه­های متوسط	78
شکل4-8- پاسخ میانگین­ها در الگوریتم شبیه­سازی تبرید برای مسایل در اندازه­های متوسط	78
شکل4-9- زمان محاسباتی روش شاخه و کران	80
شکل4-10- نمودار LSD در سطح اطمینان 95% برای مقادیر RPD	85

فصل اول

کلیات تحقیق

1-1- مقدمه