1. MMC
  2. All Volumes and Issues
  3. Volume 12, Number 1, 2025
  4. Multi-neighborhood local search with room split balancer for exam timetabling: A case study

Multi-neighborhood local search with room split balancer for exam timetabling: A case study

MMC.
2025;
Volume 12, Number 1
: pp. 144–157
https://doi.org/10.23939/mmc2025.01.144
Received: October 15, 2024
Revised: February 10, 2025
Accepted: February 15, 2025

Siew E. S. K., Sze S. N., Goh S. L., Hossin M., Chiew K. L.  Multi-neighborhood local search with room split balancer for exam timetabling: A case study.  Mathematical Modeling and Computing. Vol. 12, No. 1, pp. 144–157 (2025)

Authors:
  1. E. S. K. Siew
  2. S. N. Sze
  3. S. L. Goh
  4. M. Hossin
  5. K. L. Chiew
1
Faculty of Computing and Software Engineering, i-CATS University College
2
Faculty of Computer Science & Information Technology, University Malaysia Sarawak
3
Optimisation and Visual Analytics Research Group, Faculty of Computing and Informatics
4
Faculty of Computer Science & Information Technology, University Malaysia Sarawak
5
Faculty of Computer Science & Information Technology, University Malaysia Sarawak

This study explicitly addresses the examination timetabling problem (ETP) at University Malaysia Sarawak (UNIMAS), which encompasses both online and physical exams treated within a unified framework of uncapacitated and capacitated formulations.  Currently, faculty exam timetabling managed by proprietary systems meets basic constraints but needs to incorporate faculty and stakeholder preferences into a mathematical formulation, making solution quality difficult to assess.  To address this issue, we propose a mathematical model that includes university-wide constraints and considers extended soft constraints that accommodate faculty and stakeholder preferences for room sharing and achieving balanced exam splits for shared and non-shared exam scenarios.  We introduce a two-stage multi-neighborhood local search method with a balancer to produce high-quality solutions that meet these constraints.  Our approach outperforms existing proprietary systems by meeting all standard constraints and achieving extended soft constraints, improving scheduling efficiency and stakeholder satisfaction, and offering a more optimal solution for real-world exam timetabling.

exam timetabling
multi-neighborhood
local search
balance
timetabling; exam spreading
  1. Sze S. N., Phang M. H., Chiew K. L.  Real-Life Faculty Examination Timetabling to Utilise Room Used.  Journal of Telecommunication, Electronic and Computer Engineering (JTEC).  9 (3–11), 51–54 (2017).
  2. Burke E. K., Petrovic S.  Recent research directions in automated timetabling.  European Journal of Operational Research.  140 (2), 266–280 (2002).
  3. Qu R., Burke E. K., McCollum B., Merlot L. T. G., Lee S. Y.  A survey of search methodologies and automated system development for examination timetabling.  Journal of Scheduling.  12, 55–89 (2009).
  4. Siew E. S. K., Goh S. L., Kendall G., Sabar N. R., Abdullah S.  A Survey of Solution Methodologies for Exam Timetabling Problems.  IEEE Access.  12, 41479–41498 (2024).
  5. Ma Z., Wu G., Suganthan P. N., Song A., Luo Q.  Performance assessment and exhaustive listing of 500+ nature-inspired metaheuristic algorithms.  Swarm and Evolutionary Computation.  77, 101248 (2023).
  6. Swan J., Adriaensen S., Brownlee A. E. I., Hammond K., Johnson C. G., Kheiri A., Krawiec F., et al.  Metaheuristics "in the large".  European Journal of Operational Research.  297 (2), 393–406 (2022).
  7. Bianchi L., Dorigo M., Gambardella L. M., Gutjahr W. J.  A survey on metaheuristics for stochastic combinatorial optimization.  Natural Computing.  8, 239–287 (2009).
  8. Müller T.  Real-life examination timetabling.  Journal of Scheduling.  19, 257–270 (2016).
  9. Bykov Y., Petrovic S.  A step counting hill climbing algorithm applied to university examination timetabling.  Journal of Scheduling.  19, 479–492 (2016).
  10. Burke E. K., Bykov Y.  The late acceptance hill-climbing heuristic.  European Journal of Operational Research.  258 (1), 70–78 (2017).
  11. Bellio R., Ceschia S., Di Gaspero L., Schaerf A.  Two-stage multi-neighborhood simulated annealing for uncapacitated examination timetabling.  Computers & Operations Research.  132, 105300 (2021).
  12. Carter M. W., Laporte G., Lee S. Y.  Examination timetabling: Algorithmic strategies and applications.  Journal of the Operational Research Society.  47, 373–383 (1996).
  13. McCollum B., McMullan P., Burke E. K., Parkes A. J., Qu R.  The second international timetabling competition: Examination timetabling track. Technical Report QUB/IEEE/Tech/ITC2007/-Exam/v4.0/17, Queen's University, Belfast (2007).
  14. Van Bulck D., Goossens D., Schaerf A.  Multi-neighbourhood simulated annealing for the ITC-2007 capacitated examination timetabling problem.  Journal of Scheduling.  1–16 (2023).
  15. Alefragis P., Gogos C., Valouxis C., Housos E.  A multiple metaheuristic variable neighborhood search framework for the Uncapacitated Examination Timetabling Problem.  Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling-PATAT.  1, 159–171 (2021).
  16. Aldeeb B. A., Al-Betar M. A., Norwawi N. M., Alissa K. A., Alsmadi M. K., Hazaymeh A. A., Alzaqebah M.  Hybrid intelligent water Drops algorithm for examination timetabling problem.  Journal of King Saud University-Computer and Information Sciences.  34 (8), 4847–4859 (2022).
  17. Nand R., Reddy E., Chaudhary K., Sharma B.  Preference Based Stepping ahead Firefly Algorithm for solving Real-World uncapacitated Examination Timetabling Problem.  IEEE Access (2024).
  18. Mandal A. K., Kahar M. N. M., Kendall G.  Addressing examination timetabling problem using a partial exams approach in constructive and improvement.  Computation.  8 (2), 46 (2020).
  19. Leite N., Melício F., Rosa A. C.  A fast threshold acceptance algorithm for the examination timetabling problem.  Handbook of operations research and management science in higher education.  323–363 (2021).
  20. Kahar M. N. M., Kendall G.  The examination timetabling problem at Universiti Malaysia Pahang: Comparison of a constructive heuristic with an existing software solution.  European Journal of Operational Research.  207 (2), 557–565 (2010).
  21. Saat E. H. M., Ilham N. I., Othman N., Bakar Z. A., Yusof Y., Rahman N. H. A.  The examination timetabling problem based on expert system: a case study in Malaysia.  2019 IEEE 10th Control and System Graduate Research Colloquium (ICSGRC).  121–126 (2019).
  22. Müller T.  Real-life examination timetabling.  Journal of Scheduling.  19, 257–270 (2016).
  23. Woumans G., De Boeck L., Beliën J., Creemers S.  A column generation approach for solving the examination-timetabling problem.  European Journal of Operational Research.  253 (1), 178–194 (2016).
  24. Battistutta M., Ceschia S., De Cesco F., Di Gaspero L., Schaerf A., Topan E.  Local search and constraint programming for a real-world examination timetabling problem.  International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research.  69–81 (2020).
  25. Muklason A., Pratama E. J., Premananda I. G. A.  Generic University Examination Timetabling System with Steepest-Ascent Hill Climbing Hyper-heuristic Algorithm.  Procedia Computer Science.  234, 584–591 (2024).
  26. Merlot L. T. G., Boland N., Hughes B. D., Stuckey P. J.  A hybrid algorithm for the examination timetabling problem.  Practice and Theory of Automated Timetabling IV: 4th International Conference, PATAT 2002.  Selected Revised Papers.  207–231 (2002).
  27. McCollum B., McMullan P., Parkes A. J., Burke E. K., Qu R.  A new model for automated examination timetabling.  Annals of Operations Research.  194, 291–315 (2012).
  28. Dammak A., Elloumi A., Kamoun H.  Classroom assignment for exam timetabling.  Advances in Engineering Software.  37 (10), 659–666 (2006).
  29. Komijan A. R., Koupaei M. N.  A new binary model for university examination timetabling: a case study.  Journal of Industrial Engineering International.  8 (1), 28 (2012).
  30. Genc B., O'Sullivan B.  A two-phase constraint programming model for examination timetabling at university college cork.  Principles and Practice of Constraint Programming: 26th International Conference, CP 2020.  26, 724–742 (2020).
  31. Carlsson M., Ceschia S., Di Gaspero L., Mikkelsen R. Ø., Schaerf A., Stidsen T. J. R.  Exact and metaheuristic methods for a real-world examination timetabling problem.  Journal of Scheduling.  26 (4), 353–367 (2023).
  32. Laporte G., Desroches S.  Examination timetabling by computer.  Computers & Operations Research.  11 (4), 351–360 (1984).
  33. McCollum B., Schaerf A., Paechter B., McMullan P., Lewis R., Parkes A. J., Di Gaspero L., Qu R., Burke E. K.  Setting the research agenda in automated timetabling: The second international timetabling competition.  INFORMS Journal on Computing.  22 (1), 120–130 (2010).
  34. Ayob M., Abdullah S., Malik A. M. A.  A practical examination timetabling problem at the Universiti Kebangsaan Malaysia.  International Journal of Computer Science and Network Security.  7 (9), 198–204 (2007).
  35. Burke E. K., Kingston J., De Werra D.  Applications to timetabling.  Handbook of graph theory.  445, 4 (2004).
  36. Ding J., Shen L., Lü Z., Peng B.  Parallel machine scheduling with completion-time-based criteria and sequence-dependent deterioration.  Computers & Operations Research.  103, 35–45 (2019).
  37. Di Gaspero L.  Recolour, shake and kick: A recipe for the examination timetabling problem.  Proceedings of the fourth international conference on the practice and theory of automated timetabling.  404–407 (2002).
  38. Siew S. K. E., Nah Sze S., Goh K. L., Wong J. J.  Grouping and Heuristics for A Multi-stage Class Timetabling System.  2022 International Conference on Digital Transformation and Intelligence (ICDI).  111–116 (2022).
  39. Nurmi O., Soisalon-Soininen E., Wood D.  Concurrency control in database structures with relaxed balance.  Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems. 170 (1987).
  40. Jain R. K., Chiu D. M. W., Hawe W. R.  A quantitative measure of fairness and discrimination.  Eastern Research Laboratory, Digital Equipment Corporation, Hudson, MA.  21, 1 (1984).