پایان نامه مقطع کارشناسی ارشد رشته صنایع

فهرست مطالب:

فصل اول: مقدمه وکلیات تحقیق…………………….. 1

1-1-مقدمه……………………. 2

1-2- بیان مسأله……………………. 2

1-3- ضرورت تحقیق…………………….. 6

1-4- اهداف تحقیق…………………….. 6

1-5- سئوالات تحقیق…………………….. 7

1-6- جمع­بندی…………………….. 7

فصل دوم : ادبیات و پیشینه تحقیق……………………… 8

2-1-مقدمه……………………. 9

2-2- طبقه­ بندی مسائل جدول زمانی…………………….. 10

2-3- جدول زمانی دروس دانشگاهی…………………….. 11

2-3-1- محدودیت­های سخت جدول زمانی دروس دانشگاهی………. 12

2-3-2- محدودیت­های نرم جدول زمانی دروس دانشگاهی…………………….. 13

2-3-3- روش­های حل جدول زمانی دروس دانشگاهی…………………….. 17

2-4- انواع روش­های حل مسائل بهینه­ سازی…………………….. 23

2-4-1- روش­های بهینه سازی ترکیبی…………………….. 24

2-4-1-1- الگوریتم­های فراابتکاری……………………. 25

2-5- الگوریتم جستجوی ممنوعه (TS)…………………….

2-5-1- همسایگی…………………….. 29

2-5-2- لیست ممنوعه……………………. 29

2-5-3- معیار آرمانی…………………….. 30

2-5-4- استراتژی لیست کاندید…………………….. 31

2-5-5- استراتژی تقویت……………………… 32

2-5-6- استراتژی تنوع بخشی…………………….. 32

2-5-7- معیار توقف………………………. 33

2-6- الگوریتم جستجوی متغیر همسایگی (VNS)…………………….

2-6- 1- فرآیند ارتعاش………………………. 35

2-6- 2- فرآیند جستجوی محلی…………………….. 36

2-7- مدل­های بهینه سازی چند هدفه……………………. 37

2-7-1- مفهوم غلبه در مسائل بهینه سازی چندهدفه…………. 38

2-8- الگوریتم چند هدفه ژنتیک (NSGA II)…………………….

2-9- فرآیند تحلیل سلسه مراتبی (AHP)…………………….

2-9-1- درخت سلسه مراتبی…………………….. 42

2-9-2- انجام مقایسات زوجی…………………….. 43

2-9-3- محاسبه ضرایب اهمیت……………………… 44

2-9-4- تعیین امتیاز نهایی گزینه ­ها…………………… 45

2-9-5- بررسی سازگاری سیستم…………………….. 45

2-10- جمع­بندی…………………….. 48

فصل سوم: روش تحقیق……………………… 49

3-1- مقدمه……………………. 50

3-2- جدول زمانی دروس دانشگاهی مبتنی بر ترجیحات اساتید، دانشجویان و دانشگاه……. 50

3-2-1- مفروضات مسأله ارائه شده……………………. 51

3-2-2- مهمترین تصمیمات اتخاذ شده در مدل ارائه شده……………………. 52

3-3- روش جمع آوری اطلاعات……………………… 52

3-4- الگوریتم­های تکاملی مورد استفاده……………………. 52

3-5- مدل ریاضی…………………….. 53

3-5-1- محدودیت­های سخت……………………… 53

3-5-2- محدودیت­های نرم……………………. 54

3-5-3- پارامترها و مجموعه ­های مدل…………………….. 55

3-5-4- متغیر تصمیم…………………….. 56

3-6- مدل ریاضی تک هدفه……………………. 56

3-7- تشریح مدل ریاضی…………………….. 57

3-8- الگوریتم جستجوی ممنوعه (TS)…………………….

3-8- 1- نحوه نمایش جواب……………………… 58

3-8-2- تولید جواب اولیه……………………. 59

3-8-3- همسایگی…………………….. 59

3-8-4- لیست ممنوعه……………………. 59

3-8-5- معیار آرمانی…………………….. 60

3-8-6- استراتژی لیست کاندید…………………….. 60

3-8-7- استراتژی تقویت……………………… 61

3-8-8- استراتژی تنوع بخشی…………………….. 61

3-8-9- معیار توقف………………………. 62

3-9- الگوریتم جستجوی همسایگی متغیر در جستجوی ممنوعه (TS-VNS)…………………….

3-9-1- استراتژی­های ساختار همسایگی…………………….. 64

3-10- فرآیند تحلیل سلسه مراتبی (AHP)…………………….

3-10-1- درخت سلسه مراتبی…………………….. 69

3-10-2- انجام مقایسات زوجی…………………….. 69

3-10-3- محاسبه ضرایب اهمیت……………………… 70

3-10-4- تعیین امتیاز نهایی گزینه ­ها…………………… 70

3-10-5- بررسی سازگاری سیستم…………………….. 70

3-11- مدل ریاضی چند هدفه……………………. 71

3-12- الگوریتم ژنتیک چند هدفه (NSGA II)…………………….

3-12-1- نحوه نمایش جواب و جمعیت اولیه……………… 73

3-12-2- انتخاب……………………… 74

3-12-3- تقاطع……………………. 74

3-12-4- جهش………………………. 77

3-12-5- معیار توقف………………………. 78

3-13- الگوریتم جستجوی ممنوعه چند هدفه (MOTS)………………..

3-14- جمع­بندی…………………….. 81

فصل چهارم: محاسبات و یافته­ های تحقیق……………………… 82

4-1- مقدمه……………………. 83

4-2- تنظیم پارامترهای الگوریتم­های فراابتکاری…………………….. 83

4-3- اجرای الگوریتم­ها…………………… 86

4-4- نتایج محاسباتی الگوریتم­های مدل تک هدفه و تجزیه و تحلیل آنها……. 86

4-4-1- تحلیل نتایج بهترین مقدار تابع هدف……………………… 87

4-4-2- تحلیل نتایج اولین زمان رسیدن به بهترین مقدار تابع هدف………….. 89

4-5- نتایج محاسباتی الگوریتم­های مدل چند هدفه و تجزیه و تحلیل آنها……. 91

4-5-1- تحلیل نتایج شاخص میانگین فاصله از نقطه ایده آل (MID)………………….

4-5-2- تحلیل نتایج شاخص تعداد جوابهای آرشیو پاراتو……………………. 95

4-5-3- تحلیل نتایج شاخص یکنواختی پاراتو……………………. 98

4-5-4- تحلیل نتایج شاخص پوشش مجموعه……………………. 100

4-5-5- تحلیل نتایج شاخص بیشترین گستردگی…………………….. 102

4-5-6- تحلیل نتایج زمان اجرای الگوریتمها ……………………104

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

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

5-1- نتیجه ­گیری…………………….. 109

5-2- پیشنهادها برای تحقیقات آتی…………………….. 110

5-2-1- تحقیقات مربوط به گسترش مدل مسأله……………………. 110

5-2-2- تحقیقات مربوط به رویکرد حل مسأله……………………. 111

مراجع…………………….. 112

چکیده:

در این پایان­نامه، یک مدل برای مسأله زمانبندی دروس دانشگاهی به دو صورت تک هدفه و دو هدفه ارائه شده است. هدف این مسأله تهیه جدول زمانی دروس دانشگاهی مناسب و قابل قبول، با در نظر گرفتن مجموعه­ای از محدودیت­ها و ترجیحات اساتید، دانشجویان و دانشگاه با توجه به فضای آموزشی در ایران است. در مسائل جدول زمانی محدودیت­ها به دو دسته سخت و نرم تقسیم می­شوند. محدودیت­های سخت باید برآورده شوند و شدنی بودن جواب را تضمین می­کنند و محدودیت­های نرم که بیان کننده مطلوبیت و ترجیحات مسأله هستند که برای کیفیت بهتر جدول زمانی در نظر گرفته    می­شوند. برای بدست آوردن یک جدول زمانی با کیفیت، باید مسأله شدنی و کمترین تعداد تجاوز را در محدودیت نرم داشته باشیم. با توجه به NP-Hard بودن مسأله، برای حل مدل­ها از الگوریتم­های فرا ابتکاری استفاده شده است. در مدل تک هدفه از الگوریتم جستجوی ممنوعه (TS) و الگوریتم جستجوی همسایگی متغیر در جستجوی ممنوعه (TS-VNS) برای حل مدل استفاده شده است. با استفاده از فرآیند تصمیم­گیری AHP، جدول­های زمانی بدست آمده از الگوریتم­های فراابتکاری، رتبه­بندی و گزینه برتر انتخاب می­شود. در مدل دو هدفه از الگوریتم ژنتیک چند هدفه (NSGA II) و الگوریتم جستجوی ممنوعه چند هدفه (MOTS) استفاده شده است. همچنین در هر بخش با مقایسه عملکرد الگوریتم­ها، کارایی آنها ارزیابی شده است.

برای دانلود متن کامل پایان نامه اینجا کلیک کنید.