مسئلههای زمانبندی و برنامه ریزی، سازگارسازی و هماهنگ کردن مجموعه ای از نهادها مانند رخدادها، فعالیتها، افراد، ابزار و دستگاهها، خودروها، مکانها و مانند اینها در یک الگوی مکان- زمان است. در این دسته از مسئلهها هدف این است که منابع در دسترس به بهترین روش ممکن مورد بهره برداری قرار گیرند و محدودیتها و شرایط موجود مورد توجه قرار گرفته و برآورده شوند.
بنابراین، لزوم در نظر گرفتن متغیرهای متناظر با دروس، اساتید، کلاسها، روزهای هفته و ساعات قابل برنامه ریزی در روز سبب می شود که با یک مسئله برنامه ریزی ریاضی از نوع برنامه ریزی غیرخطی با اعداد صحیح و با ابعاد بزرگ مواجه باشیمکهحتی نرمافزارهای قوی نیز نمیتوانند آن را در زمان کم حل کنند، بنابراین الگوریتمهای فراابتکاری مورد توجه قرار گرفتهاند که بتوانند مسائل بهینهسازی با ابعاد بزرگ را با زمان اجرای مناسب تا حدودی حل کنند. مبنای اجرای تحقیق حاضر، حل مسئله زمانبندی با بهره گرفتن از تکنیک الگوریتم ژنتیک و استفاده از نرمافزار MATLAB قرار داده شده، به صورتی که با توجه به رعایت تمام محدودیتهای مدل طراحی شده، برای هر درس، رشتههایی حاوی بازههای زمانی، تولید شده و با جریمه هر سلول درصورتی که محدودیتها را رعایت نکنند، تابع برازندگی برای این کروموزومها محاسبه می شود، از مزیتهای این تکنیک روش آزمون و خطا برای تغییر عملگرهای ژنتیکی است که با جستجو در فضای حل وسیعتری به طور تصادفی با توجه به مقدار تابع برازنگی بهترین جوابها را در زمانی نسبتاً کوتاه تولید می کند. در نهایت برای چهار گروه مقطع کارشناسی ارشد دانشکده علومانسانی دانشگاه علم و هنر یزد، با فرض عدم محدودیت تعداد کلاسها، جداول زمانی دروس دانشگاهی به تفکیک آورده شده است.
کلمات کلیدی: مدل زمانبندی دروس دانشگاهی- ترجیحات اساتید- الگوریتم ژنتیک- محدودیت سخت- محدودیت نرم
فهرست مطالب
عنوان صفحه
فصل اول: کلیات………………………………………………………………………………………………………………………………. 1
1-1- مقدمه ……………………………………………………………………………………………………………………………… 2
1-2- بیان موضوع ……………………………………………………………………………………………………………………… 3
1-3- اهمیت و ضرورت تحقیق ……………………………………………………………………………………………………. 4
1-4- تعریف مسئله …………………………………………………………………………………………………………………… 5
1-5- اهداف تحقیق …………………………………………………………………………………………………………………… 6
1-6- سؤالات اساسی تحقیق ………………………………………………………………………………………………………. 6
1-7- قلمرو تحقیق ……………………………………………………………………………………………………………………. 6
1-8- روش انجام تحقیق …………………………………………………………………………………………………………….. 7
1-9- موارد کاربرد تحقیق …………………………………………………………………………………………………………… 9
1-10- شرح اصطلاحات و واژههای به کارگرفته در تحقیق …………………………………………………………….. 9
1-11- محدودیتهای تحقیق …………………………………………………………………………………………………… 10
1-12- خلاصه و جمعبندی ……………………………………………………………………………………………………… 10
فصل دوم: ادبیات تحقیق………………………………………………………………………………………………………………. 11
2-1- مقدمه…………………………………………………………………………………………………………………………… 12
2-2- تعاریف و مبانی نظری ……………………………………………………………………………………………………. 13
2-2-1- برنامه ریزی دروس دانشگاهی ………………………………………………………………………………… 13
2-2-2- مسائل NP-complete ……………………………………………………………………………………… 15
2-2-3- روشهای بهینهسازی…………………………………………………………………………………………… 17
2-2-3-1-روشهای ریاضی(دقیق) ………………………………………………………………………………… 17
2-2-3-2- روشهای تقریبی …………………………………………………………………………………………. 18
2-2-4- معرفی الگوریتم ژنتیک ………………………………………………………………………………………… 21
2-2-4-1- انواع الگوریتمهای ژنتیکی…………………………………………………………………………….. 30
2-2-4-2- مزایای الگوریتمهای ژنتیکی…………………………………………………………………………… 31
2-2-4-3- محدودیتهای الگوریتمهای ژنتیکی ………………………………………………………………. 32
2-2-4-4- استراتژی های برخورد با محدودیتهای ژنتیکی ………………………………………………… 33
2-2-4-5- بهبود الگوریتمهای ژنتیکی……………………………………………………………………………… 34
2-2-4-6- چند نمونه از کاربردهای الگوریتمهای ژنتیکی …………………………………………………. 34
2-3- پیشینه تحقیق ……………………………………………………………………………………………………………….. 35
2-3-1-مروری بر تاریخچه…………………………………………………………………………………………………… 35
2-3-2- مطالعات داخلی …………………………………………………………………………………………………….. 37
2-3-3- مطالعات خارجی …………………………………………………………………………………………………… 44
2-4- خلاصه و جمعبندی ………………………………………………………………………………………………………. 55
فصل سوم: روش تحقیق ………………………………………………………………………………………………………………. 56
3-1- مقدمه …………………………………………………………………………………………………………………………… 57
3-2-روش تحقیق ……………………………………………………………………………………………………………………. 57
3-3- نوآوریهای تحقیق…………………………………………………………………………………………………………… 58
3-4- جامعه و نمونه آماری……………………………………………………………………………………………………….. 58
3-5- اطلاعات کلی مورد نیاز در مسائل برنامه ریزی دروس دانشگاهی ………………………………………….. 59
3-6- معرفی محدودیتهای سخت و نرم در مسائل بهینهسازی…………………………………………………….. 60
3-7- مفروضات کلی مسائل برنامه ریزی دروس دانشگاهی …………………………………………………………… 61
3-8- تعریف کلی مسئله برنامه ریزی دروس دانشگاهی ……………………………………………………………….. 63
3-9- تعریف مدل پیشنهادی مسئله برنامه ریزی دروس دانشگاهی ………………………………………………. 65
3-10- روشهای حل مدل پیشنهادی مسئله برنامه ریزی دروس دانشگاهی …………………………………… 68
3-10-1- الگوریتمهای ژنتیک …………………………………………………………………………………………….. 68
3-10-2- شبه کد الگوریتم در مدل پیشنهادی …………………………………………………………………….. 69
3 -10-3- تابع برازندگی و عملگرهای ژنتیکی ………………………………………………………………………. 71
3-11- معرفی نرم افزار ……………………………………………………………………………………………………………. 72
3-12-خلاصه و جمعبندی………………………………………………………………………………………………………… 72
فصل چهارم: تجزیه و تحلیل داده ها …………………………………………………………………………………………….. 73
4-1- مقدمه…………………………………………………………………………………………………………………………….. 74
4-2- بیان مسئله…………………………………………………………………………………………………………………….. 74
4-3- نمایش ریاضی مدل پیشنهادی مسئله برنامه ریزی دروس دانشگاهی ……………………………………. 75
4-3-1-تابع هدف مدل اول …………………………………………………………………………………………………. 75
4-3-2- محدودیتهای مدل اول ……………………………………………………………………………………………. 77
4-3-3- مدل دوم …………………………………………………………………………………………………………………. 81
4-4- نتایج حل مدل پیشنهادی مسئله برنامه ریزی دروس دانشگاهی …………………………………………… 83
4-5- خلاصه و جمعبندی ……………………………………………………………………………………………………… 102
فصل پنجم: نتیجه گیری و پیشنهادها………………………………………………………………………………………… 103
5-1- مقدمه………………………………………………………………………………………………………………………….. 104
5-2- نتیجه گیری………………………………………………………………………………………………………………….. 104
5-3- پیشنهادها…………………………………………………………………………………………………………………….. 107
5 -3- 1- پیشنهادهای کاربردی……………………………………………………………………………………………. 107
5-3- 2- پیشنهادها برای تحقیقات آتی…………………………………………………………………………………. 108
پیوستها ……………………………………………………………………………………………………………………………………. 109
پیوست (الف)- جدول ترجیحات اساتید……………………………………………………………………………………. 110
پیوست (ب)- کد نوشته شده در نرمافزار، برای گروهی با همه محدودیتها………………………………….. 111
فهرست مراجع ………………………………………………………………………………………………………………………….. 117
مقدمه
مسئلههای زمانبندی و برنامه ریزی، سازگارسازی و هماهنگ نمودن مجموعه ای از نهادها مانند رخدادها، فعالیتها، افراد، ابزار و دستگاهها، خودروها، مکانها و مانند اینها در یک الگوی مکان- زمان است. در این دسته از مسئلهها هدف این است که منابع در دسترس به بهترین روش ممکن مورد بهره برداری قرار گیرند و محدودیتها و شرایط موجود مورد توجه قرار گرفته و برآورده شوند (مسعودیان و استکی، 1388). مسائل زمانبندی ماهیتاً مسائل پویایی بوده و لحاظ نمودن انواع انعطاف پذیریها منجر به رفع مشکلات گلوگاهی، بهبود عملکرد سیستم و ایجاد مزیت رقابتی میشوند (نهاوندی و عباسیان، 1389). زمانبندی کلاسها در سطح دانشگاه بسیار پیچیده است، این بدان علت است که در زمانبندی کلاسهای دانشگاه، عاملهای زیادی اثرگذار هستند و شمار و انواع زیادی از محدودیتها نیز باید برآورده شوند (بابایی زاده، 1390).
در این مسئلهها سعی بر این است که مجموعه ای از منابع معین، متشکل از کلاسها، اساتید دروس تحت شرایط خاص به مجموعه ای از ساعتهای درسی اختصاص یابد. بنابراین، لزوم در نظر گرفتن متغیرهای متناظر با دروس، اساتید، کلاسها، روزهای هفته و ساعات قابل برنامه ریزی در روز سبب می شود که با یک مسئله برنامه ریزی ریاضی از نوع برنامه ریزی غیرخطی صفر و یک مواجه باشیم که حتی نرم افزارهای قوی نیز نمیتوانند آن را در زمان کم حل کنند، بنابراین الگوریتمهای فراابتکاری مورد توجه قرار گرفتهاند که بتوانند مسائل بهینهسازی با ابعاد بزرگ را با زمان اجرای مناسب تا حدودی حل کنند (خلیلی و منصورزاده، 1385).
از میان الگوریتمهای فراابتکاری الگوریتم ژنتیک یکی از قویترین و پرکاربردترین الگوریتمها در مسائل جستجو و بهینهسازی است. یکی از دلایل محبوبیت الگوریتمهای ژنتیکی عدم نیاز به مدل ریاضی سطح بالا و پیشرفته میباشد، این الگوریتمها از قانون تکامل پیروی می کنند. عمل تکامل توسط آمیزش کروموزومها و عمل جهش بر روی آنها انجام می شود و کروموزومهایی که دارای برازندگی بیشتری هستند شانس بیشتری برای انتقال به نسلهای بعد را دارند (مسعودیان و استکی، 1388).
1-2- بیان موضوع
با توجه به تعداد روزافزون دانشجویان، رشتههای جدید، کمبود کلاسها، اتاقهای کنفرانس و آزمایشگاهها و تعداد رو به افزایش درسهای ارائه شده برای دانشجویان، برنامه ریزی با محدودیتهای بسیاری برای ساخت یک جدول مناسب مواجه خواهد بود (مسعودیان و استکی، 1388).
از این رو انتخاب این موضوع با توجه به محدودیتهای بسیار زیاد، به جهت استفاده صحیح از منابع مختلف موجود در دانشگاهها و مراکز آموزشی از اهمیت خاصی برخوردار است.
این پژوهش با توجه به موارد اشاره شده فوق و افزایش تعداد رشتهها و دانشجویان مقاطع کارشناسی ارشد پذیرفته شده در هر نیمسال تحصیلی در دانشگاه علم و هنر یزد، با ارائه یک مدل ریاضی و حل آن با بهره گرفتن از الگوریتم ژنتیک سعی در تحقق اهداف موجود در مسئله زمانبندی دارد.
مسئله برنامه ریزی دروس دانشگاهی از جمله مسائل NP-hard است که به لحاظ تاثیر عوامل بسیار و وجود محدودیتهای مختلف از مشهورترین مسائل بهینهسازی است (راستگارامینی، 1391). یکی از دستههای خاص مسائل زمان بندی را جدولبندی زمانی مینامند. جدولبندی زمانی، در واقع زمانبندی مجموعه ای از رویدادهای همپیوند، در کمترین بازههای زمانی است به گونه ای که منابع مورد نیاز، همزمان توسط بیش از یک رویداد استفاده نشوند (دتین و همکاران، 2009.م).
در این مسئله سعی بر این است که مجموعه ای از منابع معین، متشکل از کلاسها، اساتید و دروس تحت شرایط خاص به مجموعه ای از ساعتهای درسی اختصاص یابد (خلیلی و منصورزاده، 1385). با توجه به توضیحات و پیچیدگی مسئله، روشهای مختلفی برای حل این مسئله در مقالات مختلف پیشنهاد شده است (غافری، 1387)، مانند برنامه ریزیهای خودکار (باشی زاده، 1391) و در نظرگیری معیارهای ارزیابی نظیر ترجیحات اساتید (اولویت زمانی و اولویت درسی) و رعایت محدودیتهایی مانند تعداد ظرفیت کلاسها میباشد (راستگارامینی، 1391).
در مسئله زمانبندی کلاسهای دانشگاه، این محدودیتها به دو دسته محدودیتهای سخت و محدودیتهای نرم گروه بندی میشوند. محدودیتهای سخت، محدودیتهایی هستند که در هر زمانبندی، باید رعایت شوند. اگر یک زمانبندی، این دسته از محدودیتها را نقض کند، آن زمانبندی پذیرفتنی نخواهد بود. هر چه این محدودیتها بیشتر برآورده شوند، زمانبندی به دست آمده از مطلوبیت بیشتری برخوردار خواهد بود (بابایی زاده، 1390).
الگوریتم ژنتیک یکی از قویترین و پرکاربردترین الگوریتمها در مسائل جستجو و بهینهسازی است. یکی از دلایل محبوبیت الگوریتمهای ژنتیکی عدم نیاز به مدل ریاضی سطح بالا و پیشرفته میباشد، این الگوریتمها از قانون تکامل پیروی می کنند. عمل تکامل توسط آمیزش کروموزومها و عمل جهش بر روی آنها انجام می شود و کروموزومهایی که دارای برازندگی بیشتری هستند، شانس بیشتری برای انتقال به نسلهای بعد را دارند یکی از دلایل محبوبیت الگوریتمهای ژنتیکی عدم نیاز به مدل ریاضی سطح بالا و پیشرفته میباشد (مسعودیان و استکی، 1388). این الگوریتمها بر روی یک سری از جوابهای مسئله، به امید به دست آوردن جوابهای بهتر، قانون بقای بهترین را اعمال می کند. در هر نسل به کمک فرایند انتخابی متناسب با ارزش جوابها و تولید مثل جوابهای انتخاب شده به کمک عملگرهایی که از ژنتیک طبیعی تقلید شده اند، تقریباً جوابهای بهتری از جواب نهایی به دست می آید (باوی و صالحی، 1389).
1-3- اهمیت و ضرورت تحقیق
مسئله زمانبندی کلاسهای دانشگاه، چالشی جدی برای مدیران دانشگاهی در هر نیمسال تحصیلی است، زیرا در اینگونه مسائل با محدودیتهای فراوانی مواجه خواهیم بود، تمامی محققان در این زمینه اتفاق نظر دارند که مسئله جدولهای زمانی دارای فضای پاسخ نمایی بوده و مانند تمامی مسائل NP-hard نیاز به استفاده از الگوریتمهای هوشمند جهت حل آن اجتناب ناپذیر است (غافری، 1387).
دستیابی به یک برنامه زمانبندی پذیرفتنی که محدودیتهای سخت را برآورده نماید و بتواند محدودیتهای نرم را تا حد ممکن برآورده کند، کاری بس دشوار و بسیار زمانبر است (بابایی زاده، 1390). در مورد محدودیتهای سخت میتوان به قوانین و مقررات آموزشی اشاره نمود که این گونه محدودیتها حتماً باید در نظر
گرفته شوند زیرا نشاندهنده اهمیت نحوه برنامه ریزی درسی میباشد (حاجی یخچالی، 1378)، و رعایت نکردن این قوانین و مقررات به عنوان محدودیتهای سخت نشاندهنده نامعتبر بودن برنامه درسی میباشد (دهقانی و ذاکر تولائی، 1385 ).
بنابراین با توجه به افزایش تعداد رشتهها و دانشجویان مقاطع کارشناسی ارشد پذیرفته شده در هر نیمسال تحصیلی در دانشگاه علم و هنر یزد به برنامهای جامع که علاوه بر رعایت کردن محدودیتهای سخت و نرم بتواند در زمان کم جوابهای بهینه را در بهترین شرایط ایجاد کند نیاز است.
1-4-تعریف مسئله
با توجه به مواردی از قبیل ساختار دروس دانشگاهی، انواع دروس دانشگاهی، دسترسی به منابع و دوره های زمانی، مسئله زمانبندی دروس دانشگاهی با هدف معین و محدودیتهای سخت و نرم تعریف خواهد شد، هدف مسئله زمانبندی دروس، حداقل نمودن فاصله بین دو کلاس متوالی در برنامه نیمسال گروه دانشجویان است به صورتی که محدودیتهایی از قبیل تداخل برنامه اساتید، تداخل برنامه دانشجویان، تداخل برنامه کلاسها، ترجیحات اساتید، تعداد جلسات مورد نیاز هر درس در هفته، وسایل و تجهیزات مورد نیاز برگزاری هر درس، ظرفیت کلاسها، زمانهای استفاده از کلاسها، دروس از پیش زمانبندی شده و از این دست محدودیتها که در قوانین و مقررات آموزشی آورده شده و رعایت کردن آنها اجباری است نیز لحاظ گردند، بدین ترتیب مسئله زمانبندی این پژوهش با در نظر گرفتن هدف و محدودیتهای مسئله به صورت یک مدل برنامه ریزی غیرخطی صفر و یک (با توجه به تابع هدف و یافتن متغیرهای صفر و یکی) درآمد و برای حل این مسئله، روش ابتکاری کدنویسی در نرم افزار ریاضی MATLAB جهت رسیدن به جواب نهایی مطلوب به کار گرفته شد.
1-5-اهداف تحقیق
هدف اصلی از اجرای این پژوهش، دسترسی به یک برنامه درسی بهینه با رعایت کردن تمامی شرایط برای مقاطع کارشناسی ارشد در دانشکده فنی- مهندسی دانشگاه علم و هنر میباشد. اهداف فرعی که در طول اجرای پروژه محقق گردیده به شرح ذیل است:
- دستیابی به مدلی با در نظرگرفتن ترجیحات اساتید
- یافتن بازههای زمانی مناسب با رعایت کردن حداقل فاصله بین بازه ها برای دروس هر گروه
1-6-سوالات پژوهشی
در این پژوهش به سوالات زیر پاسخ داده می شود:
- با توجه به محدودیتهای مسئله زمانبندی دروس دانشگاهی چه مدلی مناسب است؟
- کدام بازههای زمانی به عنوان جواب نهایی مدل، به دست آمده و مطلوب می باشند؟
1-7-قلمرو تحقیق
قلمرو تحقیق در سه بعد موضوعی، مکانی و زمانی در این پژوهش به شرح زیر میباشد:
قلمرو موضوعی: قلمرو موضوعی این پژوهش بر اساس مسئله زمانبندی برای دروس دانشگاهی میباشد که این دسته مسائل جزء مسائل بسیار سخت و پیچیده شناخته شده اند و برای حل اینگونه مسائل نیاز به مدلسازیهای ریاضی میباشد که بتوان تمامی محدودیتهای نرم و سخت را در آن گنجاند و به دلیل زیاد بودن متغیرها نیاز به استفاده از الگوریتمهای هوشمند و فراابتکاری میباشد. در این پژوهش پس از نوشتن مدل از الگوریتم ژنتیک برای حل مدل استفاده شده است.
قلمرو مکانی: قلمرو مکانی این پژوهش دانشکده فنی- مهندسی دانشگاه علم و هنر یزد است، که با توجه به وجود مقاطع کارشناسی و کارشناسی ارشد این دانشکده، 4 گروه از مقاطع کارشناسی ارشد سال 1391 انتخاب
آخرین نظرات