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

هدف: در این مقاله یک روش دومرحله ای جدید برای حل مساله ی زمان بندی دروس دانشگاهی مبتنی بر برنامه ی درسی ارایه شده است. در هر دو مرحله، روش از رویکرد فراابتکاری جدید استفاده شده است. علاوه بر این، یک نمایش جواب جدید برای زمان بندی دروس دانشگاهی معرفی شده است و از برخی رویکردها نیز برای تشدید و تنوع استفاده می شود که کاملا مبتنی بر نمایش جواب جدید است.روش شناسی پژوهش: در مرحله ی اول روش جدید، یک جواب با کیفیت بالا قابل اجرا محاسبه می شود. برای این منظور، ابتدا محدودیت های سخت مربوط به دوره های زمانی در نظر گرفته شده و جوابی محاسبه می شود که این محدودیت های سخت را برآورده کند. در مرحله ی بعد روش جدیدی برای تخصیص اتاق ها به دروس معرفی می شود که پس از اعمال آن بر روی جوابی که محدودیت های سخت دوره ی زمانی را برآورده می کند، یک جواب شدنی محاسبه می شود. علاوه بر این، نتایج عددی نشان می دهد که جواب شدنی محاسبه شده کیفیت بالایی دارد. در مرحله ی دوم، ابتدا چندین تابع همسایگی جدید برای بهبود کیفیت جواب شدنی محاسبه شده به طور قابل توجهی مورد استفاده قرار می گیرد که برای کاهش جریمه جواب شدنی محاسبه شده مرحله ی اول طراحی شده است. در حالی که تابع تناسب مرحله ی اول مبتنی بر نقض محدودیت های سخت است، تابع تناسب مرحله ی دوم بر اساس جریمه ی جواب شدنی است. در بسیاری از الگوریتم های فراابتکاری که تاکنون ارایه شده اند، تلاش محاسباتی زیادی بر روی الگوریتم برای انتساب اتاق ها به دوره ها صرف می شود. ویژگی جدید الگوریتم ارا یه شده این است که از یک استراتژی برای تخصیص اتاق ها به دوره فقط یک بار و بدون استفاده از هیچ الگوریتم تطبیقی استفاده می شود. یافته‎ها: الگوریتم ارایه شده بر روی برخی از نمونه های استاندارد ادبیات اعمال شده و کارایی الگوریتم ارایه شده مورد تجزیه و تحلیل قرار گرفته است. نتایج عددی نشان می دهد که زمان محاسبات مورد نیاز با اندازه ی نمونه ها افزایش می یابد و الگوریتم بعد از چند دقیقه به سمت جواب بهینه همگرا می شود.اصالت/ارزش افزوده علمی: الگوریتم ارایه شده ما را قادر می سازد تا در عمل با مسایل بزرگ زمان بندی دروس دانشگاهی مواجه شویم. علاوه بر این، روشی کارآمد برای دستیابی به جواب های شدنی برای نمونه های دنیای واقعی و تلاش برای بهبود کیفیت آنها در اختیار ما قرار می دهد.

Keywords:

جدول زمانی دروس دانشگاهی , جستجوی محلی , جستجوی ممنوعه , روش ابتکاری , زمان بندی