زمانبندی کلاسهای دانشگاهی با استفاده از الگوریتم جهش قورباغه

محسن محجوب¹ کرم اله باقری فرد²

1) دانشگاه آزاد اسلامی ،آموزشکده فنی و حرفه ای سما ،واحد گچساران، گچساران، ایران
2) گروه مهندسی کامپیوتر، واحد یاسوج، دانشگاه آزاد اسلامی، یاسوج، ایران

محل انتشار : دومین کنفرانس بین المللی پژوهش در علوم و تکنولوژی(2rstconf.com)
چکیده :
زمان بندي دروس یکی از مسائل مهم و زمان بر در هر محیط آموزشی است. برنامه ریزي چیدمان دروس در جدول هفتگی، براساس معیارها و امکانات محیط، مشخصات دروس و ساعات حضور استادان صورت میگیرد. هدف زمان بندي دروس، ایجاد یک برنامۀ زمانی معتبر و قابل اجرا با حداقل تداخل می باشد. این مسأله از نظر پیچیدگی در دستۀ مسائل Np-hard قرار می گیرد و براي حل آن به جاي الگوریتم هاي کلاسیک، از الگوریتم ژنتیک، جستجوي ممنوع، شبیه سازي تبریدي و رنگ آمیزي گراف استفاده می شود. در این تحقیق ضمن بیان مراحل بکارگیري الگوریتم جهش قورباغه به منظور زمان بندي دروس، فنون مورد استفاده در رویکرد نوینِ این پژوهش ارائه می گردد. رویکرد مذکور شامل اصلاحاتی از قبیل تغییراتی در مدل اولیۀ مسأله در راستاي بهبود زمان اجرا و جلوگیري از پیمایش فضاي حالت ناممکن می باشد. در انتها، با اعمال 20 نمونه ورودي مختلف به الگوریتم پیشنهادی این پژوهش، تأثیر رویکرد نوین در مقایسه با روش استاندارد، و الگوریتم ژنتیک در رسیدن به جواب بهینه سنجیده می شود و نشان داده می شود که رویکرد نوین به طور متوسط در زمان کوتاهتر به جوابهاي بهینه تري می رسد.
کلمات کلیدی : الگوریتم جهش قورباغهSFLA زمانبندی دروس محدودیت نرم محدودیت سخت مسائل NP-hard