کلیات تحقیق

۱-۱- مقدمه

مسئله ­های زمان­بندی و برنامه­ ریزی، سازگارسازی و هماهنگ نمودن مجموعه ­ای از نهاد­ها مانند رخدادها، فعالیت­ها، افراد، ابزار و دستگاه­ها، خودروها، مکان­ها و مانند این­ها در یک الگوی مکان- زمان است. در این دسته از مسئله­ ها هدف این است که منابع در دسترس به بهترین روش ممکن مورد بهره ­برداری قرار گیرند و محدودیت­ها و شرایط موجود مورد توجه قرار گرفته و برآورده شوند (مسعودیان و استکی، ۱۳۸۸). مسائل زمان­بندی ماهیتاً مسائل پویایی بوده و لحاظ نمودن انواع انعطاف پذیری­ها منجر به رفع مشکلات گلوگاهی، بهبود عملکرد سیستم و ایجاد مزیت رقابتی می­شوند (نهاوندی و عباسیان، ۱۳۸۹). زمان­بندی کلاس­ها در سطح دانشگاه بسیار پیچیده است، این بدان علت است که در زمان­بندی کلاس_­های دانشگاه، عامل­های زیادی اثرگذار هستند و شمار و انواع زیادی از محدودیت­ها نیز باید برآورده شوند (بابایی زاده، ۱۳۹۰).

در این مسئله­ ها سعی بر این است که مجموعه ­ای از منابع معین، متشکل از کلاس­ها، اساتید دروس تحت شرایط خاص به مجموعه ­ای از ساعت­های درسی اختصاص یابد. ‌بنابرین‏، لزوم در نظر گرفتن متغیر­های متناظر با دروس، اساتید، کلاس­ها، روزهای هفته و ساعات قابل برنامه­ ریزی در روز سبب می­ شود که با یک مسئله برنامه­ ریزی ریاضی از نوع برنامه­ ریزی غیر­خطی صفر و یک مواجه باشیم که حتی نرم افزار­های قوی نیز نمی ­توانند آن را در زمان کم حل کنند، ‌بنابرین‏ الگوریتم­های فراابتکاری مورد توجه قرار ‌گرفته‌اند که بتوانند مسائل بهینه­ سازی با ابعاد بزرگ را با زمان اجرای مناسب تا حدودی حل کنند (خلیلی و منصورزاده، ۱۳۸۵).

از میان الگوریتم­های فرا­ابتکاری الگوریتم ژنتیک یکی از قوی­ترین و پرکاربرد­ترین الگوریتم­ها در مسائل جستجو و بهینه­ سازی است. یکی از دلایل محبوبیت الگوریتم­های ژنتیکی عدم نیاز به مدل ریاضی سطح بالا و پیشرفته ‌می‌باشد، این الگوریتم­ها از قانون تکامل پیروی ‌می‌کنند. عمل تکامل توسط آمیزش کروموزوم­ها و عمل جهش بر روی آن­ها انجام می­ شود و کروموزوم­هایی که دارای برازندگی بیشتری هستند شانس بیشتری برای انتقال به نسل­های بعد را دارند (مسعودیان و استکی، ۱۳۸۸).

۱-۲- بیان موضوع

با توجه به تعداد روزافزون دانشجویان، رشته­ های جدید، کمبود کلاس­ها، اتاق­های کنفرانس و آزمایشگاه­ها و تعداد رو به افزایش درس­های ارائه شده برای دانشجویان، برنامه­ ریزی با محدودیت­های بسیاری برای ساخت یک جدول مناسب مواجه خواهد بود (مسعودیان و استکی، ۱۳۸۸).

از این رو انتخاب این موضوع با توجه به محدودیت­های بسیار زیاد، به جهت استفاده صحیح از منابع مختلف موجود در دانشگاه­ها و مراکز آموزشی از اهمیت خاصی برخوردار است.

این پژوهش با توجه به موارد اشاره شده فوق و افزایش تعداد رشته­ ها و دانشجویان مقاطع کارشناسی ارشد پذیرفته شده در هر نیمسال تحصیلی در دانشگاه علم و هنر یزد، با ارائه یک مدل ریاضی و حل آن با بهره گرفتن از الگوریتم ژنتیک سعی در تحقق اهداف موجود در مسئله زمان­بندی دارد.

مسئله برنامه­ ریزی دروس دانشگاهی از جمله مسائل NP-hard است که به لحاظ تاثیر عوامل بسیار و وجود محدودیت­های مختلف از مشهورترین مسائل بهینه­ سازی است (راستگارامینی، ۱۳۹۱). یکی از دسته­های خاص مسائل زمان بندی را جدول­بندی زمانی می­نامند. جدول­بندی زمانی، در واقع زمان­بندی مجموعه ­ای از رویدادهای هم­پیوند، در کم­ترین بازه ­های زمانی است به گونه ­ای که منابع مورد نیاز، همزمان توسط بیش از یک رویداد استفاده نشوند (دتین و همکاران، ۲۰۰۹٫م).

در این مسئله سعی بر این است که مجموعه ­ای از منابع معین، متشکل از کلاس­ها، اساتید و دروس تحت شرایط خاص به مجموعه ­ای از ساعت­های درسی اختصاص یابد (خلیلی و منصورزاده، ۱۳۸۵). با توجه به توضیحات و پیچیدگی مسئله، روش­های مختلفی برای حل این مسئله در مقالات مختلف پیشنهاد شده است (غافری، ۱۳۸۷)، مانند برنامه­ ریزی­های خودکار (باشی زاده، ۱۳۹۱) و در نظرگیری معیار­های ارزیابی نظیر ترجیحات اساتید ­(­اولویت زمانی و اولویت درسی­) و رعایت محدودیت­هایی مانند تعداد ظرفیت کلاس­ها ‌می‌باشد (راستگار­امینی، ۱۳۹۱).

در مسئله زمان­بندی کلاس­های دانشگاه، این محدودیت­ها به دو دسته محدودیت­های سخت و محدودیت­های نرم گروه بندی می­شوند. محدودیت­های سخت، محدودیت­هایی هستند که در هر زمان­بندی، باید رعایت شوند. اگر یک زمان­بندی، این دسته از محدودیت­ها را نقض کند، آن زمان­بندی پذیرفتنی نخواهد بود. هر چه این محدودیت­ها بیشتر برآورده شوند، زمان­بندی به دست آمده از مطلوبیت بیشتری برخوردار خواهد بود (بابایی زاده، ۱۳۹۰).

الگوریتم ژنتیک یکی از قوی­ترین و پرکاربردترین الگوریتم­ها در مسائل جستجو و بهینه­ سازی است. یکی از دلایل محبوبیت الگوریتم­های ژنتیکی عدم نیاز به مدل ریاضی سطح بالا و پیشرفته ‌می‌باشد، این الگوریتم­ها از قانون تکامل پیروی ‌می‌کنند. عمل تکامل توسط آمیزش کروموزوم­ها و عمل جهش بر روی آن ها انجام می­ شود و کروموزوم­هایی که دارای برازندگی بیشتری هستند، شانس بیشتری برای انتقال به نسل­های بعد را دارند یکی از دلایل محبوبیت الگوریتم­های ژنتیکی عدم نیاز به مدل ریاضی سطح بالا و پیشرفته ‌می‌باشد (مسعودیان و استکی، ۱۳۸۸). این الگوریتم­ها بر روی یک سری از جواب­های مسئله، به امید به دست آوردن جواب­های بهتر، قانون بقای بهترین را اعمال می­ کند. در هر نسل به کمک فرایند انتخابی متناسب با ارزش جواب­ها و تولید مثل جواب­های انتخاب شده به کمک عملگرهایی که از ژنتیک طبیعی تقلید ‌شده‌اند، تقریباً جواب­های بهتری از جواب نهایی به دست می ­آید (باوی و صالحی، ۱۳۸۹).

۱-۳- اهمیت و ضرورت تحقیق

مسئله زمان­بندی کلاس­های دانشگاه، چالشی جدی برای مدیران دانشگاهی در هر نیم­سال تحصیلی است، زیرا در این­گونه مسائل با محدودیت­های فراوانی مواجه خواهیم بود، تمامی محققان در این زمینه اتفاق نظر دارند که مسئله جدول­های زمانی دارای فضای پاسخ نمایی بوده و مانند تمامی مسائل NP-hard نیاز به استفاده از الگوریتم­های هوشمند جهت حل آن اجتناب ناپذیر است (غافری، ۱۳۸۷).

دستیابی به یک برنامه زمان­بندی پذیرفتنی که محدودیت­های سخت را برآورده نماید و بتواند محدودیت­های نرم را تا حد ممکن برآورده کند، کاری بس دشوار و بسیار زمان­بر است (بابایی زاده، ۱۳۹۰). ‌در مورد محدودیت­های سخت ‌می‌توان به قوانین و مقررات آموزشی اشاره نمود که این گونه محدودیت­ها حتماً باید در نظر

گرفته شوند زیرا نشان­دهنده اهمیت نحوه برنامه­ ریزی درسی ‌می‌باشد (حاجی یخچالی، ۱۳۷۸)، و رعایت نکردن این قوانین و مقررات به عنوان محدودیت­های سخت نشان­دهنده نامعتبر بودن برنامه درسی ‌می‌باشد (دهقانی و ذاکر تولائی، ۱۳۸۵ ).

‌بنابرین‏ با توجه به افزایش تعداد رشته­ ها و دانشجویان مقاطع کارشناسی ارشد پذیرفته شده در هر نیم­سال تحصیلی در دانشگاه علم و هنر یزد به برنامه­ای جامع که علاوه بر رعایت کردن محدودیت­های سخت و نرم بتواند در زمان کم جواب­های بهینه را در بهترین شرایط ایجاد کند نیاز است.