An Approach for Minimizing Time to Degree Based on University Course Timetabling Problem
Keywords:
Degree, Schedule, Student’s needs, University TimetablingAbstract
This paper addresses the solving of the University Course Timetabling problem (UCTTP), considering some of the needs of university students. The aim of this problem is to define the best schedule for offering each course subject in each period to allow the students completing the degree in less time. For this, the constraints of the course curriculum are considered, as well as the current academic background of each student, to avoid the student delaying subjects or taking them outside the regular period in which they are offered. The solution approach presented is a mathematical modeling of a Mixed Integer Linear Programming (MILP). For the computational implementation, real data from an undergraduate course at a public Brazilian university was used. The results obtained showed that the solutions served the intended purpose within a feasible computational time and, they also highlighted the main factors that cause students to delay the course degree.
Downloads
References
M. Veenstra and I. F. A. Vis, “School timetabling problem under disturbances,” Computers & Industrial Engineering, vol. 95, pp. 175–186, 2016.W.-K. Chen, Linear Networks and Systems. Belmont, CA, USA: Wadsworth, 1993, pp. 123–135.
E. Aycan e T. Ayav, “Solving the Course Scheduling Problem Using Simulated Annealing,” 2009 IEEE International Advance Computing Conference, pp. 462-466, 2009.
H. Babaei, J. Karimpour, A. Hadidi, “A survey of approaches for university course timetabling problem,” Computers & Industrial Engineering, vol. 86, pp 43-59, ISSN 0360-8352, 2015.
vol. 134, pp. A635–A646, Dec. 1965.
S. Abdullah, H. Turabieh, B. McCollum, “A hybrid metaheuristic approach to the university course timetabling problem,” J. Heuristics, vol. 18, pp. 1–23, 2012.
L. N. Ahmed, E. Ozcan and A. Kheiri, "Solving high school timetabling problems worldwide using selection hyper-heuristics," Expert Syst. Appl., vol. 42, no. 13, pp. 5463-5471, 2015.
M. W. S. Almeida, J. P. S. Medeiros and P. R. Oliveira, "Solving the Academic Timetable Problem Thinking on Student Needs," 2015 IEEE 14th International Conference on Machine Learning and Applications (ICMLA), pp. 673-676, 2015.
T. Müller, H. Rudová, and Z. Müllerová, “University course timetabling and international timetabling competition 2019,” Proceedings of the 12th International Conference on the Practice and Theory of Automated Timetabling (PATAT-2018), vol. 1, pp. 5–31, 2018.
M. A. Al-Betar, A.T. Khader, M. Zaman, “University Course Timetabling Using a Hybrid Harmony Search Metaheuristic Algorithm,” IEEE Lat. Am. Trans. vol. 42, no 5, pp. 664-681, 2012.
A. E. Phillips, C. G. Walker, M. Ehrgott, D. M. Ryan, “Integer programming for minimal perturbation problems in university course Timetabling,” Annals of Operations Research. pp. 1-22, 2016.
N. M. A. Martinez, C. M. Padron, P. A. A. Torres, "University Course Timetabling Problem with Professor Assignment," Mathematical Problems in Engineering, vol. 2021, pp. 1-9, 2021.
G. H. Fonseca, H. G. Santos, E. G. Carrano, T. J. Stidsen, “Integer programming techniques for educational timetabling,” European Journal of Operational Research, vol. 262, pp. 28–39, 2017.
T. Song, S. Liu, X. Tang, X. Peng, and M. Chen, “An iterated local search algorithm for the university course timetabling problem,” Applied Soft Computing, vol. 68, pp. 597–608, 2018.
C. Akkan, A. Gulcu, Z. Kus, “Minimum penalty perturbation heuristics for curriculum-based timetables subject to multiple disruptions”, Computers & Operations Research, vol. 132, ISSN 0305-0548, 2021.
A. Abuhamdah, M. Ayob, G. Kendall, and N. R. Sabar, “Population based local search for university course timetabling problems,” Applied Intelligence, vol. 40, vol. 1, pp. 44–53, 2014.
P. Avella, M. Boccia, S. Viglione, I. Vasilyev, “A Local Branching MIP Heuristic for a Real-World Curriculum-Based Course Timetabling Problem”, Mathematical Optimization Theory and Operations Research, vol. 1090, pp. 438-451, 2019.
G. Woumans, “A column generation approach for solving the examination timetabling problem,” European Journal of Operational Research, vol. 253, pp. 178-194, 2016.
S. L. Goh, G. Kendall, R. Nasser Sabar and S. Abdullah, "An effective hybrid local search approach for the post enrolment course timetabling problem," Opsearch, vol. 57, no. 4, pp. 1131-1163, 2020.
R. Bellio, S. Ceschia, L. Di Gaspero, A. Schaerf, T. Urli, “Feature-based tuning of simulated annealing applied to the curriculum-based course timetabling problem,” Computers & Operations Research, vol. 65, pp. 83-92, 2016.
D. S. Holm, R. O. Mikkelsen, M. Sorensen, “A graph-based MIP formulation of the International Timetabling Competition 2019,” J Sched, vol. 25, pp. 405–428, 2022.
N. Bagger, G. Desaulniers, J. Desrosiers, “Daily course pattern formulation and valid inequalities for the curriculum-based course timetabling problem,” Journal of Scheduling, vol. 22, pp. 155–172, 2019.
N Aizam, V. Uvaraja, “Generic model for timetabling problems by integer linear programmimg approach,” International Journal of Mathematical, Computational, Physical, Electrical and Computer Engineering, vol. 9, pp. 668–675, 2015.
M. Penn, C. N. Potts, P. R. Harper, P. R. “Multiple criteria mixed-integer programming for incorporating multiple factors into the development of master operating theatre timetables,” European Journal of Operational Research, vol. 262 pp. 194–206, 2017.
T. Müller, “Real-life examination timetabling.” Journal of Scheduling, vol. 19, pp. 257–270, 2016.
M. Mazlan, M. Makhtar, A. F. K. A. Khairi, M. A. Mohamed, “University course timetabling model using ant colony optimization algorithm approach,” Indonesian Journal of Electrical Engineering and Computer Science, vol. 13, pp. 72–76, 2019.
