1

 

 

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

 

 

 

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- مقدمه

 

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