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

نظیف, حبیبه; قاضیانی, خدیجه

doi:10.22105/dmor.2021.245798.1209

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

نویسندگان

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

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

https://doi.org/10.22105/dmor.2021.245798.1209

چکیده

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

کلیدواژه‌ها

موضوعات

مدل‌های زمان‌بندی

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

Modified approach to optimize the University examination timetabling problem

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

Habibeh Nazif ¹
Khadijeh Ghaziani ²

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

² 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

تصمیم گیری و تحقیق در عملیات

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

مراجع

مراجع

دوره 6، شماره 1
1400
صفحه 132-145

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

مراجع

مراجع

دوره 6، شماره 1 1400صفحه 132-145

دوره 6، شماره 1
1400
صفحه 132-145