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

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

new heuristic local search method for university coursetimetabling problem

purpose: in this paper a new two-phase method is presented for solving the curriculum based university course timetabling problem. in both phases of the new present method a new metaheuristic approach is used.methodology in the first phase of the new method, a feasible high quality solution is computed. to this end, at first the hard constraints relating to the time periods are considered and a solution is computed that satisfies these hard constraints. in the next step, a new method is introduced for the assignment of rooms to courses, after application of which on the solution that satisfies the time period hard constraints, a feasible solution is computed. in the second phase, at first several new neighborhood functions are used to improve the quality of computed feasible solution. while the fitness function of the first phase is based on the violation of hard constraints, the fitness function of the second phase is based on the penalty of the feasible solution.findings: the numerical results indicate that the required computing time increases with the size of instances and the algorithm tends to converge towards the optimal solution after a few minutes.originality/value: the presented algorithm enables us to deal with large university course timetabling problems in practice. moreover, it provides us with an efficient way to obtain feasible solutions to such real-world instances and try to improve their quality.