A Course Timetabling Formulation under Circumstances of Online Education

Öz

This study addresses the adaptation of the course timetabling problem to the online education system forced by the Covid-19 pandemic. The seating capacity constraint that shapes the timetabling decision in online education conditions loses its validity. It is replaced by a bandwidth constraint that restricts the number of instantaneous connections. Overlapping courses in the same time slot increase the number of instant connections and excessive connections cause technical problems. Bandwidth constraint requires the distribution of total connection in a day over all time slots. However, while this is achieved, the time slots should be allocated fairly to the departments. In this study, a multi-objective mathematical model is proposed that distributes the courses fairly on the day and time slot axis and distributes the total number of connections to time slots in each day as equally as possible. The model adopts the maximum difference minimizing approach and requires solving the objectives sequentially according to the order of them. The model was tested with the real data of the 2020-2021 fall semester of a 7 department faculty. The model has 12084 decision variables and 15567 constraints and an optimal solution gets in approximately 28 minutes. Results were compared with a decentralized and manually prepared timetable. The comparison shows that the model is superior to the manual timetable in the distribution of courses across the day and time slot. Also, the model can reduce the number of students in the peak time slot by 22% compared to manual scheduling.

Anahtar Kelimeler

• Course Timetable
• Online Education
• Multi-Objective Mathematical Model
• Minimax Approach
• Balanced Distribution

Kaynakça

1. Akı, O. (2020). University Course Timetabling Using Genetic Algorithms. UNITECH 2020 International Scientific Conference, 390–394. https://www.researchgate.net/publication/346969094
2. Akkan, C., & Gülcü, A. (2018). A bi-criteria hybrid Genetic Algorithm with robustness objective for the course timetabling problem. Computers and Operations Research, 90, 22–32. https://doi.org/10.1016/j.cor.2017.09.007
3. Alvarez-Valdes, R., Martin, G., & Tamarit, J. M. (1996). Constructing good solutions for the spanish school timetabling problem. Journal of the Operational Research Society, 47(10), 1203–1215. https://doi.org/10.1057/jors.1996.149
4. Alvarez-Valdes, Ramon, Crespo, E., & Tamarit, J. M. (2002). Design and implementation of a course scheduling system using Tabu Search. European Journal of Operational Research, 137(3), 512–523. https://doi.org/10.1016/S0377-2217(01)00091-1
5. Arratia-Martinez, N. M., Maya-Padron, C., & Avila-Torres, P. A. (2021). University Course Timetabling Problem with Professor Assignment. Mathematical Problems in Engineering, 2021. https://doi.org/10.1155/2021/6617177
6. Aubin, J., & Ferland, J. A. (1989). A large scale timetabling problem. Computers and Operations Research, 16(1), 67–77. https://doi.org/10.1016/0305-0548(89)90053-1
7. Babaei, H., Karimpour, J., & Hadidi, A. (2015). A survey of approaches for university course timetabling problem. Computers and Industrial Engineering. https://doi.org/10.1016/j.cie.2014.11.010
8. Birbas, T., Daskalaki, S., & Housos, E. (2009). School timetabling for quality student and teacher schedules. Journal of Scheduling, 12(2), 177–197. https://doi.org/10.1007/s10951-008-0088-2

9. Carter, M. W. (2001). A comprehensive course timetabling and student scheduling system at the University of Waterloo. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2079 LNCS, 64–82. https://doi.org/10.1007/3-540-44629-x_5
10. Carter, M. W., & Laporte, G. (1998). Recent developments in practical course timetabling (pp. 3–19). Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0055878
11. Colorni, A., Dorigo, M., & Maniezzo, V. (1998). Metaheuristics for high school timetabling. Computational Optimization and Applications, 9(3), 275–298. https://doi.org/10.1023/A:1018354324992
12. Council of Higher Education. (2020). YÖK Koronavirüs (Covid-19) Bilgilendirme Notu-1. https://www.yok.gov.tr/Sayfalar/Haberler/2020/coronavirus_bilgilendirme_1.aspx
13. Dandashi, A., & Al-Mouhamed, M. (2010). Graph coloring for class scheduling. 2010 ACS/IEEE International Conference on Computer Systems and Applications, AICCSA 2010. https://doi.org/10.1109/AICCSA.2010.5586963
14. Daskalaki, S., & Birbas, T. (2005). Efficient solutions for a university timetabling problem through integer programming. European Journal of Operational Research, 160(1), 106–120. https://doi.org/10.1016/J.EJOR.2003.06.023
15. Dimopoulou, M., & Miliotis, P. (2001). Implementation of a university course and examination timetabling system. European Journal of Operational Research, 130(1), 202–213. https://doi.org/10.1016/S0377-2217(00)00052-7
16. Dimopoulou, M., & Miliotis, P. (2004). An automated university course timetabling system developed in a distributed environment: A case study. European Journal of Operational Research, 153(1), 136–147. https://doi.org/10.1016/S0377-2217(03)00104-8
17. Goh, S. L., Kendall, G., & Sabar, N. R. (2019). Simulated annealing with improved reheating and learning for the post enrolment course timetabling problem. Journal of the Operational Research Society, 70(6), 873–888. https://doi.org/10.1080/01605682.2018.1468862
18. Hosny, M. (2019). Metaheuristic approaches for solving university timetabling problems: A review and case studies from middle eastern universities. Smart Innovation, Systems and Technologies, 111, 10–20. https://doi.org/10.1007/978-3-030-03577-8_2
19. Kaplan, A. M., & Haenlein, M. (2016). Higher education and the digital revolution: About MOOCs, SPOCs, social media, and the Cookie Monster. Business Horizons, 59(4), 441–450. https://doi.org/10.1016/j.bushor.2016.03.008
20. Matias, J. B., Fajardo, A. C., & Medina, R. M. (2018). A fair course timetabling using genetic algorithm with guided search technique. Proceedings of 2018 5th International Conference on Business and Industrial Research: Smart Technology for Next Generation of Information, Engineering, Business and Social Science, ICBIR 2018, 77–82. https://doi.org/10.1109/ICBIR.2018.8391170
21. Moodle. (2018). Moodle - Open-source learning platform | Moodle.org. Moodle.Org. https://moodle.org/ Mühlenthaler, M., & Wanka, R. (2016). Fairness in academic course timetabling. Annals of Operations Research, 239(1), 171–188. https://doi.org/10.1007/s10479-014-1553-2
22. Palma, C. D., & Bornhardt, P. (2020). Considering Section Balance in an Integer Optimization Model for the Curriculum-Based Course Timetabling Problem. Mathematics, 8(10), 1763. https://doi.org/10.3390/math8101763
23. Schaerf, A. (1999). Survey of automated timetabling. Artificial Intelligence Review, 13(2), 87–127. https://doi.org/10.1023/A:1006576209967
24. Thepphakorn, T., & Pongcharoen, P. (2019). Variants and parameters investigations of particle swarm optimisation for solving course timetabling problems. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 11655 LNCS, 177–187. https://doi.org/10.1007/978-3-030-26369-0_17
25. United Nations Educational, S. and C. O. (2020). School closures caused by Coronavirus (Covid-19). Unesco. https://en.unesco.org/covid19/educationresponse
26. Wright, M. (1996). School timetabling using heuristic search. Journal of the Operational Research Society, 47(3), 347–357. https://doi.org/10.1057/jors.1996.34
27. Yoshikawa, M., Kaneko, K., Yamanouchi, T., & Watanabe, M. (1996). Constraint-based high school scheduling system. IEEE Expert, 11(1), 63–72. https://doi.org/10.1109/64.482960