کلیات تحقیق
۱-۱- مقدمه
مسئله های زمانبندی و برنامه ریزی، سازگارسازی و هماهنگ نمودن مجموعه ای از نهادها مانند رخدادها، فعالیتها، افراد، ابزار و دستگاهها، خودروها، مکانها و مانند اینها در یک الگوی مکان- زمان است. در این دسته از مسئله ها هدف این است که منابع در دسترس به بهترین روش ممکن مورد بهره برداری قرار گیرند و محدودیتها و شرایط موجود مورد توجه قرار گرفته و برآورده شوند (مسعودیان و استکی، ۱۳۸۸). مسائل زمانبندی ماهیتاً مسائل پویایی بوده و لحاظ نمودن انواع انعطاف پذیریها منجر به رفع مشکلات گلوگاهی، بهبود عملکرد سیستم و ایجاد مزیت رقابتی میشوند (نهاوندی و عباسیان، ۱۳۸۹). زمانبندی کلاسها در سطح دانشگاه بسیار پیچیده است، این بدان علت است که در زمانبندی کلاسهای دانشگاه، عاملهای زیادی اثرگذار هستند و شمار و انواع زیادی از محدودیتها نیز باید برآورده شوند (بابایی زاده، ۱۳۹۰).
در این مسئله ها سعی بر این است که مجموعه ای از منابع معین، متشکل از کلاسها، اساتید دروس تحت شرایط خاص به مجموعه ای از ساعتهای درسی اختصاص یابد. بنابرین، لزوم در نظر گرفتن متغیرهای متناظر با دروس، اساتید، کلاسها، روزهای هفته و ساعات قابل برنامه ریزی در روز سبب می شود که با یک مسئله برنامه ریزی ریاضی از نوع برنامه ریزی غیرخطی صفر و یک مواجه باشیم که حتی نرم افزارهای قوی نیز نمی توانند آن را در زمان کم حل کنند، بنابرین الگوریتمهای فراابتکاری مورد توجه قرار گرفته‌اند که بتوانند مسائل بهینه سازی با ابعاد بزرگ را با زمان اجرای مناسب تا حدودی حل کنند (خلیلی و منصورزاده، ۱۳۸۵).
از میان الگوریتمهای فراابتکاری الگوریتم ژنتیک یکی از قویترین و پرکاربردترین الگوریتمها در مسائل جستجو و بهینه سازی است. یکی از دلایل محبوبیت الگوریتمهای ژنتیکی عدم نیاز به مدل ریاضی سطح بالا و پیشرفته می‌باشد، این الگوریتمها از قانون تکامل پیروی می‌کنند. عمل تکامل توسط آمیزش کروموزومها و عمل جهش بر روی آنها انجام می شود و کروموزومهایی که دارای برازندگی بیشتری هستند شانس بیشتری برای انتقال به نسلهای بعد را دارند (مسعودیان و استکی، ۱۳۸۸).
۱-۲- بیان موضوع
با توجه به تعداد روزافزون دانشجویان، رشته های جدید، کمبود کلاسها، اتاقهای کنفرانس و آزمایشگاهها و تعداد رو به افزایش درسهای ارائه شده برای دانشجویان، برنامه ریزی با محدودیتهای بسیاری برای ساخت یک جدول مناسب مواجه خواهد بود (مسعودیان و استکی، ۱۳۸۸).
از این رو انتخاب این موضوع با توجه به محدودیتهای بسیار زیاد، به جهت استفاده صحیح از منابع مختلف موجود در دانشگاهها و مراکز آموزشی از اهمیت خاصی برخوردار است.
این پژوهش با توجه به موارد اشاره شده فوق و افزایش تعداد رشته ها و دانشجویان مقاطع کارشناسی ارشد پذیرفته شده در هر نیمسال تحصیلی در دانشگاه علم و هنر یزد، با ارائه یک مدل ریاضی و حل آن با بهره گرفتن از الگوریتم ژنتیک سعی در تحقق اهداف موجود در مسئله زمانبندی دارد.
مسئله برنامه ریزی دروس دانشگاهی از جمله مسائل NP-hard است که به لحاظ تاثیر عوامل بسیار و وجود محدودیتهای مختلف از مشهورترین مسائل بهینه سازی است (راستگارامینی، ۱۳۹۱). یکی از دستههای خاص مسائل زمان بندی را جدولبندی زمانی مینامند. جدولبندی زمانی، در واقع زمانبندی مجموعه ای از رویدادهای همپیوند، در کمترین بازه های زمانی است به گونه ای که منابع مورد نیاز، همزمان توسط بیش از یک رویداد استفاده نشوند (دتین و همکاران، ۲۰۰۹٫م).
در این مسئله سعی بر این است که مجموعه ای از منابع معین، متشکل از کلاسها، اساتید و دروس تحت شرایط خاص به مجموعه ای از ساعتهای درسی اختصاص یابد (خلیلی و منصورزاده، ۱۳۸۵). با توجه به توضیحات و پیچیدگی مسئله، روشهای مختلفی برای حل این مسئله در مقالات مختلف پیشنهاد شده است (غافری، ۱۳۸۷)، مانند برنامه ریزیهای خودکار (باشی زاده، ۱۳۹۱) و در نظرگیری معیارهای ارزیابی نظیر ترجیحات اساتید (اولویت زمانی و اولویت درسی) و رعایت محدودیتهایی مانند تعداد ظرفیت کلاسها می‌باشد (راستگارامینی، ۱۳۹۱).
در مسئله زمانبندی کلاسهای دانشگاه، این محدودیتها به دو دسته محدودیتهای سخت و محدودیتهای نرم گروه بندی میشوند. محدودیتهای سخت، محدودیتهایی هستند که در هر زمانبندی، باید رعایت شوند. اگر یک زمانبندی، این دسته از محدودیتها را نقض کند، آن زمانبندی پذیرفتنی نخواهد بود. هر چه این محدودیتها بیشتر برآورده شوند، زمانبندی به دست آمده از مطلوبیت بیشتری برخوردار خواهد بود (بابایی زاده، ۱۳۹۰).
الگوریتم ژنتیک یکی از قویترین و پرکاربردترین الگوریتمها در مسائل جستجو و بهینه سازی است. یکی از دلایل محبوبیت الگوریتمهای ژنتیکی عدم نیاز به مدل ریاضی سطح بالا و پیشرفته می‌باشد، این الگوریتمها از قانون تکامل پیروی می‌کنند. عمل تکامل توسط آمیزش کروموزومها و عمل جهش بر روی آن ها انجام می شود و کروموزومهایی که دارای برازندگی بیشتری هستند، شانس بیشتری برای انتقال به نسلهای بعد را دارند یکی از دلایل محبوبیت الگوریتمهای ژنتیکی عدم نیاز به مدل ریاضی سطح بالا و پیشرفته می‌باشد (مسعودیان و استکی، ۱۳۸۸). این الگوریتمها بر روی یک سری از جوابهای مسئله، به امید به دست آوردن جوابهای بهتر، قانون بقای بهترین را اعمال می کند. در هر نسل به کمک فرایند انتخابی متناسب با ارزش جوابها و تولید مثل جوابهای انتخاب شده به کمک عملگرهایی که از ژنتیک طبیعی تقلید شده‌اند، تقریباً جوابهای بهتری از جواب نهایی به دست می آید (باوی و صالحی، ۱۳۸۹).
۱-۳- اهمیت و ضرورت تحقیق
مسئله زمانبندی کلاسهای دانشگاه، چالشی جدی برای مدیران دانشگاهی در هر نیمسال تحصیلی است، زیرا در اینگونه مسائل با محدودیتهای فراوانی مواجه خواهیم بود، تمامی محققان در این زمینه اتفاق نظر دارند که مسئله جدولهای زمانی دارای فضای پاسخ نمایی بوده و مانند تمامی مسائل NP-hard نیاز به استفاده از الگوریتمهای هوشمند جهت حل آن اجتناب ناپذیر است (غافری، ۱۳۸۷).
دستیابی به یک برنامه زمانبندی پذیرفتنی که محدودیتهای سخت را برآورده نماید و بتواند محدودیتهای نرم را تا حد ممکن برآورده کند، کاری بس دشوار و بسیار زمانبر است (بابایی زاده، ۱۳۹۰). در مورد محدودیتهای سخت می‌توان به قوانین و مقررات آموزشی اشاره نمود که این گونه محدودیتها حتماً باید در نظر
گرفته شوند زیرا نشاندهنده اهمیت نحوه برنامه ریزی درسی می‌باشد (حاجی یخچالی، ۱۳۷۸)، و رعایت نکردن این قوانین و مقررات به عنوان محدودیتهای سخت نشاندهنده نامعتبر بودن برنامه درسی می‌باشد (دهقانی و ذاکر تولائی، ۱۳۸۵ ).
بنابرین با توجه به افزایش تعداد رشته ها و دانشجویان مقاطع کارشناسی ارشد پذیرفته شده در هر نیمسال تحصیلی در دانشگاه علم و هنر یزد به برنامهای جامع که علاوه بر رعایت کردن محدودیتهای سخت و نرم بتواند در زمان کم جوابهای بهینه را در بهترین شرایط ایجاد کند نیاز است.
