1403/09/01
پرهام مرادی دولت آبادی

پرهام مرادی دولت آبادی

مرتبه علمی: دانشیار
ارکید:
تحصیلات: دکترای تخصصی
اسکاپوس: 654
دانشکده: دانشکده مهندسی
نشانی: دانشگاه کردستان، دانشکده مهندسی، گروه مهندسی کامپیوتر
تلفن:

مشخصات پژوهش

عنوان
ارایه یک روش ابتکاری برای حل مساله ی جدول زمان بندی دروس دانشگاهی با استفاده از الگوریتم های مبتنی بر جمعیت
نوع پژوهش
پایان نامه
کلیدواژه‌ها
جدول زمان بندی، الگوریتم زنبور عسل، ساختار همسایگی، مجموعه داده ایی Socha، محدودیت های نرم، ساختار همسایگی، الگوریتم گروه بندی ژنتیکی
سال 1394
پژوهشگران الهام قاسمی(دانشجو)، پرهام مرادی دولت آبادی(استاد راهنما)، محمد فتحی(استاد مشاور)

چکیده

مساله ی جدول زمان بندی دروس یکی از موضوعات مهم پیش رو در دانشگاه ها و موسسات آموزش عالی سر تا سر جهان است. این مساله که از دسته ی مسائل NP-hard به شمار می رود، شامل برنامه ریزی تعداد مشخصی از درس ها در بازه های زمانی و کلاس های درسی است به نحوی که تداخلی میان آن ها پیش نیاید. روش ارایه شده در این رساله عبارت است از یک الگوریتم پیشنهادی مبتنی بر گروه بندی ژنتیک و الگوریتم زنبور عسل که ساختارهای همسایگی ابتکاری در آن تعبیه شده است. راه حل ارایه شده بر روی مجموعه داده ایی Socha آزمایش شده که یکی از استاندارد و معتبرترین مجموعه داده های موجود در مساله ی جدول زمان بندی است. این مجموعه شامل 5 نمونه کوچک، پنج نمونه متوسط و یک نمونه با اندازه بزرگ است. مساله ی جدول زمان بندی دروس دانشگاهی شامل 6 محدودیت است که نیمی از آن ها محدودیت های سخت و نیمی از آن محدودیت نرم است. مهم ترین محدودیت ها، محدودیت های سخت هستند که در صورت نقض هر کدام از آن ها، راه حل امکان پذیر به دست نمی آید. به عنوان مثال، یک دانشجو نمی تواند هم زمان در دو کلاس درسی شرکت کند. حذف محدودیت های نرم، اجباری نیست اما حذف هرچه بیشتر آن ها باعث ارتقای راه حل می شود. تا کنون هیچ یک از راه حل های ارایه شده در این حوزه نتوانسته است تعداد محدودیت های نرم بر روی نمونه های متوسط و بزرگ در این مجموعه داده ایی را به صفر برساند. در ساختار ابتکاری این رساله از یک رویکرد دو مرحله ایی برای حل مساله ی جدول زمان بندی استفاده شده است. در مرحله ی اول از یک الگوریتم پیشنهادی مبتنی بر گروه بندی ژنتیکی، برای به دست آوردن یک راه حل امکان پذیر استفاده شده است. در فاز دوم یک الگوریتم مبتنی بر ساختار زنبور عسل برای ارتقای کیفیت راه حل ها به کار برده شده است و در آن یک ساختار همسایگی تعبیه شده است که پاسخ های موثرتری را به وجود می آورد.