بخشی از مقاله
چکیده: زمانبندی دروس دانشگاهی یک مساله در دسته مسائل پیچیده میباشد و بایستی برای هر نیم سال تحصیلی به طور مکرر انجام شود. تکنیک اصلی در رهیافت ارائه شده، بر تحلیل دادهها برای زودن ابهامات و عدم قطعیت از اولویتها و قیود استادان یک دپارتمان جهت دستیابی به یک رتبهبندی برای هر کدام از استادان بر اساس خواستههایشان در یک دپارتمان جهت افزایش رضایتمندی آنها و توسعه فرآیند زمانبندی استادان بر اساس به کارگیری الگوریتمهای خوشهبندی، خواهد بود. هدف این مقاله ابتدا، بهبود نزولی رضایتمندی استادان دپارتمان و سپس، بهبود رتبهبندی استادان دپارتمان بر مبنای وزنهای قیود نرم به صورت ارتقایی از رضایتمندی هر یک از استادان دپارتمان، بر روی اولویتها و خواستههایشان میباشد.
روش به کارگرفته شده در این مقاله، استفاده از یک الگوریتم دو مرحلهای شامل: گام1، ابتدا دپارتمان فرآیند زمانبندی را با به کارگیری رهیافت تصمیمگیری فازی - مقایسهی چند معیارهی فازی - برای اولویتدهی و رتبهبندی استادان با کمک الگوریتم جستجوی محلی با هفت ساختار همسایگی به همراه الگوریتم ژنتیک برای بهبود رتبههای استادان به همراه ارضاء کامل قیود سخت حاکم در دپارتمان به صورت محلی انجام میدهند و در گام2، نیز به ترتیب دو عامل خوشهبند و پیمایشگر که یکی برای خوشهبندی استادان دپارتمان و دیگری هم جهت یافتن منابع بلااستفاده موجود دپارتمان است، به کار میبندند.
پس از انجام فرآیند خوشهبندی و پیمایش، عمل نگاشت بر اساس قیود استادان در منابع صورت میگیرد، تا اهداف مقاله حاصل گردند. در این روش، لیست اولویتهای انتخابی مربوط به هر استاد به واسطهی به کارگیری روش تصمیمگیری فازی بر مبنای مقایسهی فازی برشهای زمانی روزانهی و هفتگی هر استاد مشترک رفع ابهام، اولویتدهی و رتبهبندی میشوند و سپس جدول زمانبندی شامل استادان دپارتمان به همراه تابع برازششان، به الگوریتم ترکیبی برای ارتقاء کیفیت تابع برازش هر استاد موجود در هر یک از جداول زمانبندی، داده میشوند تا خوشهبندی و نگاشت استادان بر اساس یک منطق مطلوب از تابع برازش هر استاد انجام شود. مجموعهی دادهای استفاده شده منطبق با ارضاء نیازمندیهای زمانبندی در دنیای واقعی دپارتمان مهندسی کامپیوتر دانشگاه آزاد واحد اهر خواهد بود.
مقدمه
یکی از مسائل مهم در محیط آموزشی دانشگاهها، مسالهی UCTTP - University Course Time tabling Problem - میباشد که بایستی برای هر نیمسال تحصیلی به طور مکرر انجام شود و این خود کاری طاقت فرسا و زمانبر است. از طرفی همچنین این مساله در دستهی مسائل با پیچیدگی زمانی غیر چند جملهای قرار دارد. پس جهت گریز از این فرآیند تکراری و زمانگیر باید به دنبال روشهای تسهیل کنندهی این مساله باشیم، که این خود انگیزهای را برای پژوهش در اذهان بسترسازی میکند.
همچنین UCTTP در دستهی مسائل بهینهسازی ترکیبی میباشد که آن مشکلاتی را برای حل بهینه و تحلیلی این مساله به وجود آورده است، یعنی غیر چند جملهای بودن پیچیدگی زمانی مسالهی UCTTP به علت افزایش اندازهی مساله با رشد تعداد دانشجویان میباشد که این نیازمند محاسباتی با پیچیدگی نمایی است.
مسالهی UCTTP، فرآیند تخصیص کلیهی رویدادها - دروس، استادان و دانشجویان - را به برشهای زمانی و کلاسهای درسی - اتاقها - در یک نیم سال تحصیلی انجام میدهد، به طوری که هیچ برخوردی در این تخصیصها به وجود نیاید. این مساله همچنین بایستی دو قید سخت و نرم را نیز ارضاء نماید تا جداول زمانی امکانپذیر بعد از ارضاء کامل کلیهی قیود سخت و جداول زمانی با درجهی کیفیت بالا هم پس از ارضاء حداکثری قیود نرم، تولید شوند و حتما لزومی ندارد که قیود نرم همانند قیود سخت به طور کامل ارضاء شوند. 1[و2و]3 اهداف ارائه شده جهت حل مسالهی UCTTP در این تحقیق شامل: - 1 رضایتمندی نزولی قیود و اولویتهای استادان دپارتمان است، به همراه -2 بهبود پیکربندی وزنهای قیود نرم با استفاده از مقادیر فازی و -3 افزایش رضایتمندی استادان با اجرای روش جستجوی محلی خواهند بود. این اهداف به وسیلهی مقایسه فازی ترکیبی و خوشهبندی استادان و گروهبندی منابع مازاد دپارتمان مورد سنجش و ارزیابی قرار میگیرند.
کارهای پیشین
در سال 2010 روش رنگ آمیزی لبههای گراف دو بخشی را ]4[ برای حل مسالهی UCTTP ارائه دادند که این روش بر روی مجموعهی دادهای سه ترم تحصیلی تست میشد و نتایج تحلیلها براساس مقایسهی کل تعداد پنالتیها در یک مجموعه-ی از پیش تعریف شدهی قیود نرم تخطی شده، صورت میپذیرفت و هدف این متد کاهش تعداد پنالتیها و ایجاد جداول زمانبندی با کیفیت نسبت به جداول زمانبندیی که به صورت دستی تولید میشدند، بود. در اینجا گراف دو بخشی عبارت است از یک گراف با رئوسی که میتواند به طور مجزا در دو مجموعهی X و Y باشد، و هر لبه در گراف یک نقطهی پایانی در مجموعهی دیگر را داشته باشد.
در سال 2008 الگوریتم بهینهسازی کلونی مورچهها را ]5[ برای مسالهی UCTTP پس از ثبتنام با استفاده از جدول زمانبندی مسابقات بینالمللی 2007 بکار بردند. مورچهها رویدادها را به اتاقها و برشهای زمانی مبتنی بر دو نوع مادهی فرومون Tijs و Tyjk تخصیص میدهند، این نوع از مادهی فرومون که احتمالاتی از تخصیص یک رویداد i در برش زمانی j و اتاق k را ارائه میدهد. این الگوریتم بر روی جدول زمانبندی خوب عمل کرده و در زمان اجرای طولانیتر، نتایج خوبی را تولید میکند.
در سال 2012 برای حل مسالهی UCTTP یک الگوریتم ژنتیک ترکیبی چند جمعیتی را ]6[ پیشنهاد دادند. چون الگوریتمهای ژنتیکی دارای خاصیت جستجوی چند جهته هستند پس به صورت یک روش کارآمد و پربازده برای حل این دسته از مسایل مفید و سودمند میباشند. در این مقاله سه نوع الگوریتم ژنتیکی FGARI، FGASA و FGATS پیشنهاد میشود. در الگوریتم ارائه شده، منطق فازی برای سنجش تعداد تخطی از قیود نرم در تابع برازش جهت سروکار داشتن با دادههای دنیای واقعی که به صورت مبهم و غیر واقعیاند، استفاده میشود. البته روشهای تصادفی، جستجوی محلی، شبیهسازی حرارتی و جستجوی ممنوعه نیز به همراه روش فازی جهت بهبود جستجوی استنتاجی برای ارضاء توانایی جستجو و نیز عدم به کارگیری مجزای الگوریتم ژنتیک جهت اجتناب از به دام افتادن در بهینگی محلی استفاده میشوند.
روش پیشنهادی
در الگوریتم پیشنهادی سه گام برای دستیابی به اهداف مقاله مشخص میشوند. گام اول: تولید جداول زمانبندی خالی و بررسی ارضاء قیود سخت با تولید راهحلهای اولیه، گام دوم: رتبهبندی و اولویتدهی استادان بر اساس قیود و خواستههای آنها به واسطهی به کارگیری الگوریتم تصمیم گیری چند معیارهی فازی، در راستای ارضای قیود نرم استادان و گام سوم: به کارگیری الگوریتم ترکیبی - جستجوی محلی و ژنتیک - برای بهبود و ارتقاء قیود نرم استادان حاضر در جداول زمانبندی موجود در گام دوم.
فاز اول روش پیشنهادی
الگوریتم پیشنهادی شامل سه گام: -1 تولید جداول زمانبندی امکانپذیر اولیه با ارضاء کامل قیود سخت مربوط به استادان و منابع در دسترس درون یک دپارتمان - واحد هماهنگ کننده - ، -2 رتبهبندی و اولویتدهی به قیود نرم مربوط به استادان و منابع در دسترس به واسطهی به کارگیری الگوریتم تصمیمگیری فازی - بخش اول واحد بهینهسازی - و -3 ارتقاء کیفیت جداول زمانبندی تولید شده در گام دوم به واسطهی استفادهی از یک الگوریتم ترکیبی - بخش دوم واحد بهینهسازی - ، میباشد که در شکل 1 نشان داده شدهاند. در این الگوریتم فرآیند زمانبندی استادان در منابع در دسترس یک دپارتمان به ترتیب در سه واحد به صورت زیر طراحی شده است:
واحد اول، واسط کاربری است که ارتباط کاربران را با پایگاه دادهی سرور و واحد هماهنگ کننده برقرار میکند.
واحد دوم، فرآیند تولید جداول زمانبندی اولیه را بر مبنای عدم تخطی از قیود سخت مربوط به استادان و منابع در دسترس یک دپارتمان انجام میدهد.
واحد سوم، شامل دو بخش میباشد که بخش اول به واسطهی به کارگیری الگوریتم تصمیمگیری چندمعیاره فازی بر روی قیود نرم، باعث اولویتدهی و رتبهبندی این قیود متناظر با استادان و منابع در دسترس درون یک دپارتمان میشود و بخش دوم نیز برای بهبود کیفیت قیود نرم موجود در جداول زمانبندی رتبهبندی شده از بخش اول، یک الگوریتم ترکیبی را جهت ارتقاء ارضای هر جدول زمانبندی استفاده میکند.
واحد اول الگوریتم پیشنهادی
واحد اول به واسطهی محاوره با کاربران سیستم، که شامل استادان، دانشجویان و کاربر آموزش هر دپارتمان میباشد، فرآیند زمانبندی، ارتباط و هماهنگیهای لازم مابین پایگاه دادهی سرور دپارتمان و واحد هماهنگ کننده را انجام میدهد. این واحد یک ارتباط دو سویه را مابین کاربران و سیستم برقرار میکند.
واحد دوم الگوریتم پیشنهادی
در واحد دوم - واحد هماهنگ کننده - ، قیود سخت مربوط به استادان و منابع در دسترس هر دپارتمان توسط واحد دوم ارضاء میشوند که شامل قیود:
-1 یک استاد در یک روز نمیتواند بیش از 6 ساعت تدریس کند،
-2 یک دانشجو یا یک گروه دانشجویی نمیتواند در بیش از یک کلاس درسی در یک برش زمانی یکسان، همزمان حضور داشته باشد،
-3 یک استاد همزمان نمیتواند در دو کلاس درسی در یک دپارتمان
