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

نویسندگان

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

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

چکیده

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

کلیدواژه‌ها

موضوعات

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

Modified approach to optimize the University examination timetabling problem

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

  • Habibeh Nazif 1
  • Khadijeh Ghaziani 2

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

2 Department of Mathematics, Ayandegan Institute of Higher Education , Tonekabon, Iran.

چکیده [English]

The timetable is the problem of placing particular resources due to constraints in a limited number of times lots 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 the 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 time slots 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 incapacitated 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 the 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 the datasets compared with other algorithms.

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

  • Timetabling
  • University Examination Timetabling Problem
  • Genetic Algorithm
  • Local Search
Abdullah, S., & Burke, E. K. (2006, June). A multi-start very large neighbourhood search approach with local search methods for examination timetabling. ICAPS (pp. 334-337). https://www.aaai.org/Papers/ICAPS/2006/ICAPS06-034.pdf.
Abdul-Rahman, S., Burke, E. K., Bargiela, A., McCollum, B., & zcan, E. (2014). A constructive approach to examination timetabling based on adaptive decomposition and ordering. Annals of operations research, 218(1), 3–21.
Abounacer, R., Boukachour, J., Dkhissi, B., & Alaoui, A. E. H. (2010). A hybrid ant colony algorithm for the exam timetabling problem. Revue African research journal in computer science (ARIMA), 15–42. (In French). hal-01286691
Asmuni, H. (2008). Fuzzy methodologies for automated university timetabling solution construction and evaluation (Doctoral dissertation, University of Nottingham). Retrieved from https://ethos.bl.uk/OrderDetails.do?did=1&uin= uk.bl.ethos.514699
Asmuni, H., Burke, E. K., Garibaldi, J. M., & McCollum, B. (2004, August). Fuzzy multiple heuristic orderings for examination timetabling. International conference on the practice and theory of automated timetabling (PATAT) (pp. 334-353). Berlin, Heidelberg: Springer. https://link. springer.com/chapter/10.1007/11593577_19
Assi, M., Halawi, B., & Haraty, R. A. (2018). Genetic algorithm analysis using the graph coloring method for solving the university timetable problem. Procedia computer science, 126, 899-906. https://doi.org/10.1016/j.procs.2018.08.024
Bader-El-Den, M., & Fatima, S. (2010, April). Genetic programming for auction based scheduling. European conference on genetic programming (EuroGP) (pp. 256-267). Berlin, Heidelberg: Springer. https://link.springer.com/ chapter/10.1007/978-3-642-12148-7_22
Burke, E. K., McCollum, B., Meisels, A., Petrovic, S., & Qu, R. (2007). A graph-based hyper-heuristic for educational timetabling problems. European journal of operational research, 176(1), 177-192.
Burke, E., Elliman, D., Ford, P., & Weare, R. (1995a, August). Examination timetabling in British universities: A survey. International conference on the practice and theory of automated timetabling (PATAT) (pp. 76-90). Berlin, Heidelberg: Springer. https://link.springer.com/chapter/10.1007/3-540-61794-9_52
Burke, E. K., Newall, J. P., & Weare, R. F. (1995b, August). A memetic algorithm for university exam timetabling. International conference on the practice and theory of automated timetabling (PATAT) (pp. 241-250). Berlin, Heidelberg: Springer. https://link.springer.com/chapter/10.1007/3-540-61794-9_63
Caramia, M., Dell’Olmo, P., & Italiano, G. F. (2000, September). New algorithms for examination timetabling. International workshop on algorithm engineering (WAE) (pp. 230-241). Berlin, Heidelberg: Springer. https://link. springer.com/chapter/10.1007/3-540-44691-5_20
Carter, M. W., & Laporte, G. (1995, August). Recent developments in practical examination timetabling. International conference on the practice and theory of automated timetabling (PATAT) (pp. 1-21). Berlin, Heidelberg: Springer. https://link.springer.com/chapter/10.1007/3-540-61794-9_49
Carter, M. W., Laporte, G., & Lee, S. Y. (1996). Examination timetabling: algorithmic strategies and applications. Journal of the operational research society, 47(3), 373-383.
Casey, S., & Thompson, J. (2002, August). GRASPing the examination scheduling problem. International conference on the practice and theory of automated timetabling (PATAT) (pp. 232-244). Berlin, Heidelberg: Springer. https://link.springer.com/chapter/10.1007/978-3-540-45157-0_15
Chu, S. C., & Fang, H. L. (1999, December). Genetic algorithms vs. tabu search in timetable scheduling. 1999 third international conference on knowledge-based intelligent information engineering systems. Proceedings (Cat. No. 99TH8410) (pp. 492-495). Adelaide, SA, Australia, Australia: IEEE. https://ieeexplore.ieee.org/abstract/ document/820230
Ishak, S., Lee, L. S., & Ibragimov, G. (2016). Hybrid genetic algorithm for university examination timetabling problem. Malaysian journal of mathematical sciences, 10(2), 145-178.
Leite, N., Fernandes, C. M., Melicio, F., & Rosa, A. C. (2018). A cellular memetic algorithm for the examination timetabling problem. Computers and operations research, 94, 118-138. https://doi.org/10.1016/j.cor.2018.02.009
Leite, N., Melício, F., & Rosa, A. C. (2019). A fast simulated annealing algorithm for the examination timetabling problem. Expert systems with applications, 122, 137-151. https://doi.org/10.1016/j.eswa.2018.12.048
Muklason, A., Syahrani, G. B., & Marom, A. (2019). Great deluge based hyper-heuristics for solving real-world university examination timetabling problem: new data set and approach. Procedia computer science, 161, 647-655. https://doi.org/10.1016/j.procs.2019.11.168
Pillay, N. (2012). Evolving hyper-heuristics for the uncapacitated examination timetabling problem. Journal of the operational research society, 63(1), 47-58.
Pillay, N., & Banzhaf, W. (2010). An informed genetic algorithm for the examination timetabling problem. Applied soft computing, 10(2), 457-467.
Sabar, N. R., Ayob, M., & Kendall, G. (2009, August). Solving examination timetabling problems using honey-bee mating optimization (ETP-HBMO). Multidisciplinary international conference on scheduling: theory and applications (MISTA) (pp. 10-12). Ireland, Dublin. http://www.mistaconference.org/2009/papers/399-408-123-P.pdf