روش جستجوی محلی ابتکاری جدید برای جدول زمانی دروس دانشگاهی
آرشیو
چکیده
هدف: در این مقاله یک روش دومرحله ای جدید برای حل مساله ی زمان بندی دروس دانشگاهی مبتنی بر برنامه ی درسی ارایه شده است. در هر دو مرحله، روش از رویکرد فراابتکاری جدید استفاده شده است. علاوه بر این، یک نمایش جواب جدید برای زمان بندی دروس دانشگاهی معرفی شده است و از برخی رویکردها نیز برای تشدید و تنوع استفاده می شود که کاملاً مبتنی بر نمایش جواب جدید است. روش شناسی پژوهش: در مرحله ی اول روش جدید، یک جواب با کیفیت بالا قابل اجرا محاسبه می شود. برای این منظور، ابتدا محدودیت های سخت مربوط به دوره های زمانی در نظر گرفته شده و جوابی محاسبه می شود که این محدودیت های سخت را برآورده کند. در مرحله ی بعد روش جدیدی برای تخصیص اتاق ها به دروس معرفی می شود که پس از اعمال آن بر روی جوابی که محدودیت های سخت دوره ی زمانی را برآورده می کند، یک جواب شدنی محاسبه می شود. علاوه بر این، نتایج عددی نشان می دهد که جواب شدنی محاسبه شده کیفیت بالایی دارد. در مرحله ی دوم، ابتدا چندین تابع همسایگی جدید برای بهبود کیفیت جواب شدنی محاسبه شده به طور قابل توجهی مورد استفاده قرار می گیرد که برای کاهش جریمه جواب شدنی محاسبه شده مرحله ی اول طراحی شده است. در حالی که تابع تناسب مرحله ی اول مبتنی بر نقض محدودیت های سخت است، تابع تناسب مرحله ی دوم بر اساس جریمه ی جواب شدنی است. در بسیاری از الگوریتم های فراابتکاری که تاکنون ارایه شده اند، تلاش محاسباتی زیادی بر روی الگوریتم برای انتساب اتاق ها به دوره ها صرف می شود. ویژگی جدید الگوریتم ارا یه شده این است که از یک استراتژی برای تخصیص اتاق ها به دوره فقط یک بار و بدون استفاده از هیچ الگوریتم تطبیقی استفاده می شود. یافته ها: الگوریتم ارایه شده بر روی برخی از نمونه های استاندارد ادبیات اعمال شده و کارایی الگوریتم ارایه شده مورد تجزیه و تحلیل قرار گرفته است. نتایج عددی نشان می دهد که زمان محاسبات مورد نیاز با اندازه ی نمونه ها افزایش می یابد و الگوریتم بعد از چند دقیقه به سمت جواب بهینه همگرا می شود. اصالت/ارزش افزوده علمی: الگوریتم ارایه شده ما را قادر می سازد تا در عمل با مسایل بزرگ زمان بندی دروس دانشگاهی مواجه شویم. علاوه بر این، روشی کارآمد برای دستیابی به جواب های شدنی برای نمونه های دنیای واقعی و تلاش برای بهبود کیفیت آنها در اختیار ما قرار می دهد.New heuristic local search method for university course timetabling
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.
تبلیغات
