نوع مقاله : مقاله پژوهشی

نویسندگان

1 استادیار، گروه ریاضی، دانشگاه پیام نور، تهران، ایران

2 گروه آموزشی علوم پایه، موسسه آموزش عالی آیندگان، تنکابن، ایران.

10.22105/dmor.2021.245798.1209

چکیده

جدول زمانی، مسئله قرار دادن منابع خاص با توجه به محدودیتها در تعداد محدودی بازه‌ی زمانی و مکانی به منظور ارضا مجموعه‌ای از اهداف است که در مسائل متنوعی کاربرد دارد. از جمله این مسائل، می‌توان به مسئله جدول زمانی امتحانات دانشگاهی (UETP)‌ اشاره کرد که از اهمیت خاصی در مسائل آموزشی برخوردار است. مسئله جدول زمانی امتحانات دانشگاهی در واقع تخصیص مجموعه‌ای معین از امتحانات به تعداد ثابتی از بازه‌های زمانی و اتاق‌ها می‌باشد، به‌طوری‌که تمام محدودیتهای سخت را برآورده کند، هم‌چنین ‌محدودیتهای نرم نیز تا حد ممکن بهینه شوند. این تحقیق به ارائه و بررسی یک رویکرد اصلاحی برای بهینه‌سازی UETP بدون ظرفیت می‌پردازد. در این رویکرد یک الگوریتم ژنتیک(GA) پیشنهادی به‌وسیله عملگرهای جستجوی ‌محلی اصلاح می‌شود. این عملگر‌ها تغییراتی که مستلزم انتقال یا تعویض امتحانات زمانبندی شده است را در جدول زمانی ایجاد کرده و در نتیجه توانایی جستجوی الگوریتم را تا حد زیادی بهبود می‌‌بخشند. با استفاده از مجموعه مسائل نمونه کارتر، کارآیی و مؤثر بودن رویکرد پیشنهادی در مقایسه با دیگر روش‌های موجود بررسی می‌شود. نتایج محاسبات نشان می‌دهد که این رویکرد در بهبود جواب‌ها کاملاً مؤثر و رقابتی بوده و قادر است در بیشتر نمونه‌ها، جواب‌های بهتری در مقایسه با الگوریتم‌های دیگر تولید کند.

کلیدواژه‌ها

موضوعات

عنوان مقاله [English]

Modified approach to optimize the university examination timetabling problem

نویسندگان [English]

  • Habibeh Nazif 1
  • Khadijeh Ghaziani 2

1 Assistant Professor, Department of Mathematics. Payame Noor University Tehran, Iran

2 Department of Basic Sciences, Institute of Higher Education of the Future, Tonekabon, Iran.

چکیده [English]

The timetable is the problem of placing particular resources due to constraints in a limited number of timeslots and space, in order to satisfy a set of goals that is used to a variety of problems. Among these problems, one can point out the University Examination Timetabling Problem (UETP), which is of particular importance in educational problems. The university examination timetabling problem defined as the assignment of a certain set of exams to a fixed number of timeslots and rooms, so that it meets all the hard constraints, also soft constraints are optimized as much as possible. This research presents a modified approach to optimize the un-capacitated UETP. In this approach, a proposed Genetic Algorithm (GA) is modified by local search operators. These operators will make alterations to the timetable. This involves shifting or changing scheduled exams and thus greatly improve the ability of algorithm to search. The efficiency of the proposed approach is compared with other techniques from literature using the Carter’s benchmark. The computational results show that this approach is quite effective and competitive in improving the solutions and is able to produce better solutions in most of datasets compared with other algorithms.

کلیدواژه‌ها [English]

  • Timetabling
  • University Examination Timetabling Problem
  • Genetic Algorithm
  • Local Search