Top

Published in:

2022 | OriginalPaper | Chapter

Developing an Online Examination Timetabling System Using Artificial Bee Colony Algorithm in Higher Education

Authors : Kaixiang Zhu, Lily D. Li, Michael Li

Published in: Broadband Communications, Networks, and Systems

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Educational timetabling is a fundamental problem impacting schools and universities’ effective operation in many aspects. Different priorities for constraints in different educational institutions result in the scarcity of universal approaches to the problems. Recently, COVID-19 crisis causes the transformation of traditional classroom teaching protocols, which challenge traditional educational timetabling. Especially for examination timetabling problems, as the major hard constraints change, such as unlimited room capacity, non-invigilator and diverse exam durations, the problem circumstance varies. Based on a scenario of a local university, this research proposes a conceptual model of the online examination timetabling problem and presents a conflict table for constraint handling. A modified Artificial Bee Colony algorithm is applied to the proposed model. The proposed approach is simulated with a real case containing 16,246 exam items covering 9,366 students and 209 courses. The experimental results indicate that the proposed approach can satisfy every hard constraint and minimise the soft constraint violation. Compared to the traditional constraint programming method, the proposed approach is more effective and can provide more balanced solutions for the online examination timetabling problems.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Efficient Privacy-Preserving User Matching with Intel SGX

next chapter A Topology-Aware Scheduling Strategy for Distributed Stream Computing System

Schaerf, A.: A survey of automated timetabling. Artif. Intell. Rev. 13(2), 87–127 (1999). https://doi.org/10.1023/A:1006576209967CrossRef

Wren, A.: Scheduling, timetabling and rostering—a special relationship? In: Burke, E., Ross, P. (eds.) Practice and Theory of Automated Timetabling. LNCS, vol. 1153, pp. 46–75. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-61794-9_51CrossRef

Babaei, H., Karimpour, J., Hadidi, A.: A survey of approaches for university course timetabling problem. Comput. Ind. Eng. 86, 43–59 (2015)CrossRef

Burke, E., Kendall, G., Newall, J., Hart, E., Ross, P., Schulenburg, S.: Hyper-heuristics: an emerging direction in modern search technology. In: Glover, F., Kochenberger, G.A. (eds.) Handbook of Metaheuristics. ISOR, vol. 57, pp. 457–474. Springer, Boston (2003). https://doi.org/10.1007/0-306-48056-5_16CrossRef

Zhu, K., Li, L., Li, M.: A survey of computational intelligence in educational timetabling. Int. J. Mach. Learn. Comput. 11(1), 40–47 (2021)MathSciNetCrossRef

Appleby, J., Blake, D., Newman, E.: Techniques for producing school timetables on a computer and their application to other scheduling problems. Comput. J. 3(4), 237–245 (1961)MathSciNetCrossRef

Song, T., Liu, S., Tang, X., Peng, X., Chen, M.: An iterated local search algorithm for the University Course Timetabling Problem. Appl. Soft Comput. 68, 597–608 (2018)CrossRef

Arbaoui, T., Boufflet, J., Moukrim, A.: Lower bounds and compact mathematical formulations for spacing soft constraints for university examination timetabling problems. Comput. Oper. Res. 106, 133–142 (2019)MathSciNetCrossRef

Kahar, M., Bakar, S., Shing, L., Mandal, A.: Solving kolej poly-tech mara examination timetabling problem. Adv. Sci. Lett. 24(10), 7577–7581 (2018)CrossRef

10.

Valouxis, C., Gogos, C., Alefragis, P., Housos E.: Decomposing the high school timetable problem. In: Practice and Theory of Automated Timetabling (PATAT 2012), Son, Norway (2012)

11.

Junn, K.Y., Obit, J.H., Alfred, R.: The study of genetic algorithm approach to solving university course timetabling problem. In: Alfred, R., Iida, H., Ag, A.A., Ibrahim, Y.L. (eds.) Computational Science and Technology. LNEE, vol. 488, pp. 454–463. Springer, Singapore (2018). https://doi.org/10.1007/978-981-10-8276-4_43CrossRef

12.

Jamili, A., Hamid, M., Gharoun, H., Khoshnoudi, R.: Developing a comprehensive and multi-objective mathematical model for university course timetabling problem: a real case study. In: Conference: Proceedings of the International Conference on Industrial Engineering and Operations Management, Paris, France (2018)

13.

Skoullis, V., Tassopoulos, I., Beligiannis, G.: Solving the high school timetabling problem using a hybrid cat swarm optimization based algorithm. Appl. Soft Comput. 52, 277–289 (2017)CrossRef

14.

Dorneles, Á., de Araújo, O.C., Buriol, L.: A column generation approach to high school timetabling modeled as a multicommodity flow problem. Eur. J. Oper. Res. 256(3), 685–695 (2017)MathSciNetCrossRef

15.

Tassopoulos, I., Iliopoulou, C., Beligiannis, G.: Solving the Greek school timetabling problem by a mixed integer programming model. J. Oper. Res. Soc. 71(1), 117–132 (2020)CrossRef

16.

Leite, N., Melício, F., Rosa, A.: A fast simulated annealing algorithm for the examination timetabling problem. Expert Syst. Appl. 122, 137–151 (2019)CrossRef

17.

June, T.L., Obit, J.H., Leau, Y.B., Bolongkikit, J.: Implementation of constraint programming and simulated annealing for examination timetabling problem. In: Alfred, R., Lim, Y., Ibrahim, A., Anthony, P. (eds.) Computational Science and Technology. LNEE, vol. 481, pp. 175–184. Springer, Singapore (2019). https://doi.org/10.1007/978-981-13-2622-6_18CrossRef

18.

Güler, M., Geçici, E.: A spreadsheet-based decision support system for examination timetabling. Turk. J. Electr. Eng. Comput. Sci. 28(3), 1584–1598 (2020)CrossRef

19.

Aldeeb, B., Al-Betar, A., Abdelmajeed, A., Younes, M., AlKenani, M., Alomoush, W.: A comprehensive review of uncapacitated university examination timetabling problem. Int. J. Appl. Eng. Res. 14(24), 4524–4547 (2019)

20.

Kaur, M., Saini, S.: A review of metaheuristic techniques for solving university course timetabling problem. In: Goar, V., Kuri, M., Kumar, R., Senjyu, T. (eds.) Advances in Information Communication Technology and Computing. LNNS, vol. 135, pp. 19–25. Springer, Singapore (2021). https://doi.org/10.1007/978-981-15-5421-6_3CrossRef

21.

Tan, J., Goh, S., Kendall, G., Sabar, N.: A survey of the state-of-the-art of optimisation methodologies in school timetabling problems. Expert Syst. Appl. 165, 113943 (2021)CrossRef

22.

Memeti, S., Pllana, S., Binotto, A., Kołodziej, J., Brandic, I.: Using meta-heuristics and machine learning for software optimization of parallel computing systems: a systematic literature review. Computing 101(8), 893–936 (2018). https://doi.org/10.1007/s00607-018-0614-9MathSciNetCrossRef

23.

Salhi, S.: Heuristic Search: The Emerging Science of Problem Solving. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-49355-8CrossRef

24.

Gandomi, A., Yang, X., Talatahari, S., Alavi, A.: Metaheuristic algorithms in modeling and optimization. In: Metaheuristic Applications in Structures and Infrastructures, pp. 1–24 (2013)

25.

Kim, J., Yang, H.: Effects of heuristic type on purchase intention in mobile social commerce: focusing on the mediating effect of shopping value. J. Distrib. Sci. 17(10), 73–81 (2019)CrossRef

26.

Pillay, N., Rong, Q.: Hyper-Heuristics: Theory and Applications. Springer, Cham (2018)CrossRef

27.

Kouhbanani, S., Farid, D., Sadeghi, H.: Selection of optimal portfolio using expert system in mamdani fuzzy environment. Ind. Manag. Stud. 16(48), 131–151 (2018)

28.

Bělohlávek, R., Dauben, J., Klir, G.: Fuzzy Logic and Mathematics: A Historical Perspective. Oxford University Press, Oxford (2017)CrossRef

29.

Junn, K.Y., Obit, J.H., Alfred, R., Bolongkikit, J.: A formal model of multi-agent system for university course timetabling problems. In: Alfred, R., Lim, Y., Ibrahim, A., Anthony, P. (eds.) Computational Science and Technology. LNEE, vol. 481, pp. 215–225. Springer, Singapore (2019). https://doi.org/10.1007/978-981-13-2622-6_22CrossRef

30.

Soria-Alcaraz, J.A., et al.: Effective learning hyper-heuristics for the course timetabling problem. Eur. J. Oper. Res. 238(1), 77–86 (2014)MathSciNetCrossRef

31.

Soria-Alcaraz, J., Ochoa, G., Swan, J., Carpio, M., Puga, H., Burke, E.: Iterated local search using an add and delete hyper-heuristic for university course timetabling. Appl. Soft Comput. 40, 581–593 (2016)CrossRef

32.

Kheiri, A., Keedwell, M.: A hidden Markov model approach to the problem of heuristic selection in hyper-heuristics with a case study in high school timetabling problems. Evol. Comput. 25(3), 473–501 (2017)CrossRef

33.

Kasm, O., Mohandes, B., Diabat, A., Khatib, S.: Exam timetabling with allowable conflicts within a time window. Comput. Ind. Eng. 127, 263–273 (2019)CrossRef

34.

Bolaji, A., Khader, A., Al-Betar, M., Awadallah, M.: University course timetabling using hybridized artificial bee colony with hill climbing optimizer. J. Comput. Sci. 5(5), 809–818 (2014)CrossRef

35.

Akkan, C., Gülcü, A.: A bi-criteria hybrid Genetic Algorithm with robustness objective for the course timetabling problem. Comput. Oper. Res. 90, 22–32 (2018)MathSciNetCrossRef

36.

Sutar, S., Bichkar, R.: High school timetabling using tabu search and partial feasibility preserving genetic algorithm. Int. J. Adv. Eng. Technol. 10(3), 421 (2017)

37.

Bolaji, A., Khader, A., Al-Betar, M., Awadallah, M.: A hybrid nature-inspired artificial bee colony algorithm for uncapacitated examination timetabling problems. J. Intell. Syst. 24(1), 37–54 (2015)CrossRef

38.

Fong, C., Asmuni, H., McCollum, B.: A hybrid swarm-based approach to university timetabling. IEEE Trans. Evol. Comput. 19(6), 870–884 (2015)CrossRef

39.

Pappis, C.P., Siettos, C.I.: Fuzzy reasoning. In: Burke, E.K., Kendall, G. (eds.) Search Methodologies, pp. 437–474. Springer, Boston (2005). https://doi.org/10.1007/0-387-28356-0_15CrossRef

40.

June, T.L., Obit, J.H., Leau, Y.-B., Bolongkikit, J., Alfred, R.: Sequential constructive algorithm incorporate with fuzzy logic for solving real world course timetabling problem. In: Alfred, R., Lim, Y., Haviluddin, H., On, C.K. (eds.) Computational Science and Technology. LNEE, vol. 603, pp. 257–267. Springer, Singapore (2020). https://doi.org/10.1007/978-981-15-0058-9_25CrossRef

41.

Babaei, H., Karimpour, J., Hadidi, A.: Generating an optimal timetabling for multi-departments common lecturers using hybrid fuzzy and clustering algorithms. Soft. Comput. 23(13), 4735–4747 (2018). https://doi.org/10.1007/s00500-018-3126-9CrossRef

42.

Cavdur, F., Kose, M.: A fuzzy logic and binary-goal programming-based approach for solving the exam timetabling problem to create a balanced-exam schedule. Int. J. Fuzzy Syst. 18(1), 119–129 (2015). https://doi.org/10.1007/s40815-015-0046-zCrossRef

43.

Tkaczyk, R., Ganzha, M., Paprzycki, M.: AgentPlanner-agent-based timetabling system. Informatica 40(1) (2016)

44.

Karaboga, D.: An idea based on honey bee swarm for numerical optimization. Technical report-TR06, Erciyes university, Engineering Faculty, Computer (2005)

45.

Bukchin, Y., Raviv, T.: Constraint programming for solving various assembly line balancing problems. Omega 78, 57–68 (2018)CrossRef

Title: Developing an Online Examination Timetabling System Using Artificial Bee Colony Algorithm in Higher Education
Authors: Kaixiang Zhu
Lily D. Li
Michael Li
Publisher: Springer International Publishing
Book: Broadband Communications, Networks, and Systems
Print ISBN: 978-3-030-93478-1

Electronic ISBN: 978-3-030-93479-8

Copyright Year: 2022
DOI: https://doi.org/10.1007/978-3-030-93479-8_7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner