AccScience Publishing / IJOSI / Volume 6 / Issue 5 / DOI: 10.6977/IJoSI.202109_6(5).0001
Submit to IJOSI
Cite this article
3
Views
Related Info Links
Google Scholar
More by Authors Links
San Nah Sze
Journal Browser
Volume | Year
Issue
Search
News and Announcements
View All
ARTICLE

A Hybrid of Heuristic Orderings and Variable Neighbourhood Descent for a Real Life University Course Timetabling Problem

Mei Ching Chen1 ,  San Nah Sze1* ,  Say Leng Goh2 ,  Sei Ping Lau1
Show Less
1 Faculty of Computer Science & Information Technology, Universiti Malaysia Sarawak, Jalan Datuk Mohammad Musa, 94300 Kota Samarahan, Sarawak , Malaysia
2 Optimisation Research Group, Faculty of Computing & Informatics, Universiti Malaysia Sabah Kampus Antarabangsa Labuan, Jln Sungai Pagar, 87000 Labuan , Malaysia
IJOSI 2020, 6(5), 1–10; https://doi.org/10.6977/IJoSI.202109_6(5).0001
Received: 8 July 2021 | Revised: 22 July 2021 | Accepted: 7 September 2021 |
© Invalid date by the Author(s). This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution -Noncommercial 4.0 International License (CC-by the license) ( https://creativecommons.org/licenses/by-nc/4.0/ )
Download PDF
XML
Cite
Abstract

Academic institutions face timetabling problem every semester. Addressing timetabling problem at academic institutions is a challenging combinatorial optimisation task both in theory and practice. This is due to the size of the problem instances as well as the number of constraints that must be satisfied. Over the years, timetabling problem has attracted many researchers in proposing ways to find an optimal solution. In this paper, we investigate a hybrid of heuristic orderings and variable neighbourhood descent approach in tackling course timetabling problem at the Faculty of Computer Science and Information Technology (FCSIT), Universiti Malaysia Sarawak (UNIMAS). At FCSIT, some events of 4 lecture hours are not evenly spread over minimum working days and some events are conducted until 9 pm. The objectives of the study are to shorten the daily lecture hours and evenly distribute events' lecture. In stage 1, heuristic orderings are utilised to find a feasible solution. In stage 2, a hybrid of heuristic orderings and variable neighbourhood descent approach are utilised to improve the quality of the solution. The proposed algorithm is tested on real-world data instances (semesters 1 and 2 of 2019/2020) of FCSIT, UNIMAS. Results show that certain heuristic ordering (largest degree or the combination of largest degree and largest enrolment) are better than others in generating a feasible solution. In addition, the number of timeslots required by heuristic ordering are less compared to that required by the existing timetabling software. In stage 2, the proposed algorithm manages to achieve soft constraint violations of 0 and 1 for instances for semesters 1 and 2, respectively. However, all HO manage to achieve 0 violation for both instances when the proposed algorithm is executed 30 times. Each neighbourhood structures defined in this study contributes to lowering the soft constraint violations thus ensuring a high-quality timetable. Results show that the order of neighbourhood structures does impact the number of soft constraint (SC1) violations achieved.

Keywords
combinatorial optimisation
course timetabling problem
heuristic orderings
hybrid
variable neighbourhood descent
References
  1. 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
  2. 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
  3. Babaei, H., Karimpour, J., & Hadidi, A. (2015). A survey of approaches for university course timetabling problem. Computers and Industrial Engineering, 86, 43–59. https://doi.org/10.1016/j.cie.2014.11.010
  4. Borchani, R., Elloumi, A., & Masmoudi, M. (2017). Variable neighborhood descent search based algorithms for course timetabling problem: Application to a Tunisian University. Electronic Notes in Discrete Mathematics, 58, 119–126. https://doi.org/10.1016/j.endm.2017.03.016
  5. Burke, E., Curtois, T., Post, G., Qu, R., Veltman, B., Burke, C. E., Curtois, T., Post, G., Qu, R., & Veltman, B. (2005). University of Nottingham Jubilee Campus Computer Science Technical Report No. NOT-TCS-TR-2005-9 A Hybrid Heuristic Ordering and Variable Neighbourhood Search for the Nurse Rostering Problem A Hybrid Heuristic Ordering and Variable Neighbourhood Search for.
  6. Burke, E. K., & Petrovic, S. (2002). Recent research directions in automated timetabling. European Journal of Operational Research, 140(2), 266–280. https://doi.org/10.1016/S0377-2217(02)00069-3
  7. Erdeniz, S. P., & Felfernig, A. (2018). OCSH: Optimized Cluster Specific Heuristics for The University Course Timetabling Problem. 0–5.
  8. Goh, S. L., Graham, G., Sabar, N. R., & Abdullah, S. (2020). An effective hybrid local search approach for the post enrolment course timetabling problem. OPSEARCH. https://doi.org/10.1007/s12597-020-00444-x
  9. Goh, S. L., Kendall, G., & Sabar, N. R. (2017). Improved local search approaches to solve the post enrolment course timetabling problem. European Journal of Operational Research, 261(1), 17–29. https://doi.org/10.1016/j.ejor.2017.01.040
  10. 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
  11. Habashi, S. S., Yousef, A. H., Salama, C., & Fahmy, H. M. A. (2018). Adaptive Diversifying Hyper-Heuristic Based Approach for Timetabling Problems. 2018 IEEE 9th Annual Information Technology, Electronics and Mobile Communication Conference (IEMCON), 259–266.
  12. Hansen, P., & Mladenović, N. (2014). Variable neighborhood search. In Edmund K. Burke & G. Kendall (Eds.), Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques (pp. 313–338). Springer New York Heidelberg Dordrecht London. https://doi.org/10.1007/978-1-4614-6940-7_12
  13. Hansen, P., Mladenović, N., Brimberg, J., & Pérez, J. A. M. (2018). Variable Neighborhood Search. In International Series in Operations Research & Management Science (Vol. 272). Springer New York LLC. https://doi.org/10.1007/978-3-319-91086-4_3
  14. Matias, J. B., Fajardo, A. C., & Medina, R. P. (2019). A hybrid genetic algorithm for course scheduling and teaching workload management. 2018 IEEE 10th International Conference on Humanoid, Nanotechnology, Information Technology, Communication and Control, Environment and Management, HNICEM 2018, 1–6. https://doi.org/10.1109/HNICEM.2018.8666332
  15. Muklason, A., Irianti, R. G., & Marom, A. (2019). Automated course timetabling optimization using tabu-variable neighborhood search based hyper-heuristic algorithm. Procedia Computer Science, 161, 656–664. https://doi.org/10.1016/j.procs.2019.11.169
  16. Pillay, N., & Özcan, E. (2019). Automated generation of constructive ordering heuristics for educational timetabling. Annals of Operations Research, 275(1), 181–208. https://doi.org/10.1007/s10479-017-2625-x
  17. Schaerf, A. (1999). Survey of automated timetabling. Artificial Intelligence Review, 13(2), 87–127. https://doi.org/10.1023/A:1006576209967
  18. Tan, J. S., Leng, S., Kendall, G., & Sabar, N. R. (2021). A survey of the state-of-the-art of optimisation methodologies in school timetabling problems. Expert Systems With Applications, 165(May 2020), 113943. https://doi.org/10.1016/j.eswa.2020.113943
  19. Tan, J. S., Say, T., Goh, L., Sura, S., Kendall, G., & Sabar, N. R. (2020). Hybrid particle swarm optimization with particle elimination for the high school timetabling problem. Evolutionary Intelligence. https://doi.org/10.1007/s12065-020-00473-x
  20. Thepphakorn, T., & Pongcharoen, P. (2020). Performance Improvement Strategies on Cuckoo Search Algorithms for Solving the University Course Timetabling Problem. Expert Systems With Applications, 113732. https://doi.org/10.1016/j.eswa.2020.113732
  21. Vianna, D. S., Martins, C. B., Lima, T. J., Vianna, M. de F. D., & Meza, E. B. M. (2020). Hybrid VNS-TS heuristics for University Course Timetabling Problem. Brazilian Journal of Operations & Production Management, 17(1), 1–20. https://doi.org/10.14488/bjopm.2020.014
Previous article in this issue
Share
Back to top
International Journal of Systematic Innovation, Electronic ISSN: 2077-8767 Print ISSN: 2077-7973, Published by AccScience Publishing
We use cookies on our website to ensure you get the best experience.
Read more about our cookies here
Accept