پایان نامه ارشد رشته صنایع: زمانبندی دروس دانشگاهی تک هدفه و چند هدفه مبتنی بر … |
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) استفاده شده است. همچنین در هر بخش با مقایسه عملکرد الگوریتمها، کارایی آنها ارزیابی شده است.
فصل اول: مقدمه و کلیات تحقیق
1-1- مقدمه
امروزه زمانبندی جزء ضروریات اجتناب ناپذیر زندگی بشری است. در برنامههای کلان کشورهای توسعه یافته، یکی از بخشهایی که در نیل به تحقق برنامهها و اهدافشان نقش به سزا و مؤثری ایفا کرده، نظام آموزشی است. بنابراین با توجه به نقش کلیدی نظام آموزشی در هر جامعه، میتوان به اهمیت برنامهریزی درست و مناسب در این سیستم پی برد. به طوری که یک زمانبندی مناسب سبب ارتقای کیفیت آموزشی و رضایتمندی کارکنان میباشد. جدول زمانی نوع خاصی از مسأله زمانبندی است. مسأله زمانبندی در دانشگاهها به دو دسته جدول زمانی برای امتحانات و زمانبندی دروس تقسیم میشود. مقصود از زمانبندی در این تحقیق، دسته دوم است. در این تحقیق تلاش شده است که تا حد امکان از مقالات اخیر در حوزه جدول زمانی، بویژه جدول زمانی دروس دانشگاهی و همچنین مقالات مربوط به روشهای حل فراابتکاری استفاده شود تا بیان نوین و کارا با اثربخشی مناسب ایجاد گردد.
2-1- بیان مسأله
جدول زمانی نوع خاصی از مسأله زمانبندی است، در سال 1996، آقای رن[1] تهیه جدول زمانی را بعنوان مسئله قرار دادن منابع خاص، با توجه به محدودیتها، در تعداد محدودی بازه زمانی و مکان، با هدف ارضاء مجموعهای از اهداف تا حد ممکن توصیف کرد. این تعریف عمومی توصیفی از مسائل تهیه جدول زمانی است که به طور کلی پذیرفته شده است.
جدول زمانی در مسائلی با دامنههای وسیع و متنوع کاربرد دارد که از آن جمله میتوان مسائل آموزشی، مسابقات ورزشی، مسائل حملونقل، برنامهی کاری کارکنان، زمانبندی جلسات و زمانبندی فرآیندهای تولیدی نام برد.
جدول زمانی دروس دانشگاهی عبارت از تخصیص تعداد معینی از منابع مانند اساتید و دروس، به تعداد محدودی از دورههای زمانی و کلاس در یک دوره مشخص با توجه به مجموعهای از محدودیتها، جهت رسیدن به یکسری از اهداف مشخص است. معمولاً در این نوع مسائل محدودیتها به دو دسته سخت و نرم تقسیم میشوند. محدودیتهای سخت، محدودیتهایی هستند که حتماً باید برآورده شوند و شدنی بودن جواب را تضمین میکنند و محدودیتهای نرم بیان کننده مطلوبیت و ترجیحات مسأله هستند که برای کیفیت بهتر جدول زمانی در نظر گرفته میشوند و حتماً لزومی ندارد که همانند محدودیتهای سخت به طور کامل برآورده شوند. برای بدست آوردن یک جدول زمانی باکیفیت، باید مسأله شدنی و کمترین تعداد تجاوز را در محدودیتهای نرم داشته باشیم [4].
محدودیتهای نرم از طریق تابع پنالتی ارزیابی میشوند و تابع هدف این مسائل از مجموع وزن دهی شده توابع پنالتی محدودیتهای نرم تشکیل میشود.
محدودیتهای سخت عمومی به کار گرفته شده در این مسائل به صورت زیر هستند:
- یک منبع (درس، استاد، دانشجو) نمیتواند در آن واحد در چند جا (کلاس، پریود زمانی) استفاده شود.
- در هر دوره زمانی باید منابع در دسترس برای مواردی که زمانبندی شدهاند کافی باشد.
اما محدودیتهای نرم با توجه به نوع و ترجیحات، برای هر مسأله متفاوت است. ما در این تحقیق ترجیحات اساتید، دانشجویان و دانشگاه را مد نظر قرار دادهایم.
در حال حاضر در اغلب دانشگاهها زمانبندی دروس به صورت دستی و توسط افراد مجرب انجام میگیرد. در برنامهریزی دستی، با روشی تکراری دروس زمانبندی میشوند بدین صورت که در هر تکرار، یک درس انتخاب میشود و زمانبندی از دو درسی شروع میشود که تعداد دانشجوی بیشتری همزمان برای آن دو درس ثبت نام کرده باشند و بنابراین این دو درس نباید در یک زمان ارائه شوند و باید انتخاب استاد و بازه زمانی به گونهای صورت گیرد که محدودیتهای دیگر را نیز نقض نکند. این روند همچنان ادامه پیدا میکند تا تمامی دروس به استاد و زمانی تخصیص داده شوند.
از آنجا که زمانبندی دستی وقتگیر است و لزوماً تمام خواستههای اساتید و دانشجویان را به بهترین نحو برآورده نمیکند، استفاده از روش کامپیوتری که در زمانی بسیار کمتر، جواب خوبی را فراهم میآورد، مناسب به نظر میرسد.
تحقیق و جستجو درباره زمانبندی ماشینی دروس به دهه 60 میلادی برمیگردد. بیشتر این روشها، به نوعی شبیهسازی نحوه زمانبندی توسط نیروی انسانی است. در این روشها، ابتدا مفیدترین دروس زمانبندی میشوند. سپس دروس با اولویت کمتر، به طور متناوب به جدول زمانی ناتمام اضافه شده تا اینکه تمام دروس زمانبندی شوند. پس از آن محققان به بررسی روشهای عمومیتر پرداختند مانند روشهای برنامهریزی عدد صحیح، جریان شبکه، رنگ آمیزی گراف و …. در دو دهه آخر، تلاشها بر روی روشها ابتکاری و فراابتکاری متمرکز شده است [5].
البته این گونه مسائل زمانبندی نمیتواند به صورت کاملاً نرمافزاری انجام شود. زیرا معیارهای بهتر بودن نسبی زمانبندیها، لزوماً به آسانی به زبان نرم افزارهای کامپیوتری بیان نمیشوند. از طرفی، از آنجا که فضای جواب در این گونه مسائل بسیار بزرگ است، دخالت نیروی انسانی میتواند مسأله را در راستای جوابهای مناسبتر هدایت کند، در حالی که روشهای کامپیوتری به صورت کامل، قادر به یافتن این جوابهای مناسب نیستند. به همین دلیل، بیشتر سیستمهای حل، امکان تغییر و دستکاری در جواب را برای کاربر فراهم میسازند. که در این تحقیق از مدیر گروه دانشکده به عنوان تعدیل کننده نهایی خروجی برنامه (برای مدل تک هدفه) با کمک گرفتن از روش AHP استفاده شده است، که در فصل 3 به صورت کامل تشریح شده است.
فرم در حال بارگذاری ...
[چهارشنبه 1399-10-10] [ 06:05:00 ب.ظ ]
|