پایان نامه مقطع کارشناسی ارشد رشته صنایع
فهرست مطالب:
فصل اول: مقدمه وکلیات تحقیق…………………….. 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) استفاده شده است. همچنین در هر بخش با مقایسه عملکرد الگوریتمها، کارایی آنها ارزیابی شده است.