Hybrid Meta-Heuristic for Efficient Course Timetabling

6 Conclusion and future research

We propose a hybrid meta-heuristic for generating feasible course timetables. It uses elements from ALNS, GLS, and VNS. Moreover, a new instance decomposition and increment procedure is also introduced. The methodology is tested in real-world instances and significantly outperforms the commercial software currently used by the university.

We propose a hybrid meta-heuristic for generating feasible course timetables. It uses elements from ALNS, GLS, and VNS. Moreover, a new instance decomposition and increment procedure is also introduced. The methodology is tested in real-world instances and significantly outperforms the commercial software currently used by the university.

Solving the decomposed problem promoted significant time reductions in both the original instance, 18%, and its randomly generated subdivisions, 27%. This methodology eases the identification of local optima by dealing with more optimised versions of the problem in each iteration. This allows faster diversification rates to be more efficient. Moreover, since our methodology focuses the search on the time slots with more constraint violations and attempts to determine which constraint groups are the hardest to reduce, having simpler problems facilitates these processes.

However, decomposing the instance poses the drawback that some of the work done to find feasible schedules is fruitless, as later increments might reveal that the previous set of assignments is infeasible. Nonetheless, this effect can be reduced by clustering curricula that share some traits between themselves, such as professors or lectures, making the increments more contained. In the computational experiments, using ordered increments promoted solution time reductions 18% greater than those obtained when incrementing the instances randomly.

Regarding future research, several aspects of this work can be further explored. The methodology was applied to find feasible timetables. Nonetheless, it would be interesting to extend it to problems with objectives to be optimised. Moreover, applying the decomposition and increment procedure with different meta-heuristics and other problems should also be an interesting pursuit. Finally, the ordering algorithm implemented was simple, and it still significantly improved solution times. However, machine-learning techniques [39, 40] could be applied to find the best clustering for the decomposition and increment procedure.

Acknowledgments. All the authors acknowledge the Portuguese national funds

through the FCT - Foundation for Science and Technology, I.P., under the project

UI/BD/154023/2022. Declarations of interest: none.

References

[1] Tan, J.S., Goh, S.L., Kendall, G., Sabar, N.R.: A survey of the state-of-the-art of optimisation methodologies in school timetabling problems. Expert Systems with Applications 165 (2021) https://doi.org/10.1016/j.eswa.2020.113943

[2] Leite, N., Mel´ıcio, F., C. Rosa, A.: A fast simulated annealing algorithm for the examination timetabling problem. Expert Systems with Applications 122, 137–151 (2019) https://doi.org/10.1016/j.eswa.2018.12.048

[3] Almeida, J., Santos, D., Figueira, J.R., Francisco, A.P.: A multi-objective mixed integer linear programming model for thesis defence scheduling. European Journal of Operational Research (2023) https://doi.org/10.1016/j.ejor.2023.06.031

[4] Babaei, H., Karimpour, J., Hadidi, A.: A survey of approaches for university course timetabling problem. Computers and Industrial Engineering 86, 43–59 (2015) https://doi.org/10.1016/j.cie.2014.11.010

[5] Thepphakorn, T., Pongcharoen, P.: Performance improvement strategies on cuckoo search algorithms for solving the university course timetabling problem. Expert Systems with Applications 161 (2020) https://doi.org/10.1016/j.eswa. 2020.113732

[6] Chen, M.C., Sze, S.N., Goh, S.L., Sabar, N.R., Kendall, G.: A survey of university course timetabling problem: Perspectives, trends and opportunities. IEEE Access 9, 106515–106529 (2021) https://doi.org/10.1109/ACCESS.2021.3100613

[7] Vermuyten, H., Lemmens, S., Marques, I., Beli¨en, J.: Developing compact course timetables with optimized student flows. European Journal of Operational Research 251(2), 651–661 (2016) https://doi.org/10.1016/j.ejor.2015.11.028

[8] Boufflet, J.-P., Arbaoui, T., Moukrim, A.: The student scheduling problem at universit´e de technologie de compi`egne. Expert Systems with Applications 175 (2021) https://doi.org/10.1016/j.eswa.2021.114735

[9] Herres, B., Schmitz, H.: Decomposition of university course timetabling: A systematic study of

subproblems and their complexities. Annals of Operations Research 302(2), 405–423 (2021) https://doi.org/10.1007/s10479-019-03382-0

[10] Soria-Alcaraz, J.A., Ozcan, E., Swan, J., Kendall, G., Carpio, M.: Iterated local ¨ search using an add and delete hyper-heuristic for university course timetabling. Applied Soft Computing Journal 40, 581–593 (2016) https://doi.org/10.1016/j. asoc.2015.11.043

[11] Kiefer, A., Hartl, R.F., Schnell, A.: Adaptive large neighborhood search for the curriculum-based course timetabling problem. Annals of Operations Research 252(2), 255–282 (2017) https://doi.org/10.1007/s10479-016-2151-2

[12] Bagger, N.-C.F., Sørensen, M., Stidsen, T.R.: Dantzig–wolfe decomposition of the daily course pattern formulation for curriculum-based course timetabling. European Journal of Operational Research 272(2), 430–446 (2019) https://doi. org/10.1016/j.ejor.2018.06.042

[13] Bagger, N.-C.F., Kristiansen, S., Sørensen, M., Stidsen, T.R.: Flow formulations for curriculum-based course timetabling. Annals of Operations Research 280(1- 2), 121–150 (2019) https://doi.org/10.1007/s10479-018-3096-4

[14] Pillay, N., Ozcan, E.: Automated generation of constructive ordering heuristics for ¨

educational timetabling. Annals of Operations Research 275(1), 181–208 (2019)

https://doi.org/10.1007/s10479-017-2625-x

[15] Lindahl, M., Stidsen, T., Sørensen, M.: Quality recovering of university timetables. European

Journal of Operational Research 276(2), 422–435 (2019) https: //doi.org/10.1016/j.ejor.2019.01.026

[16] G¨ulc¨u, A., Akkan, C.: Robust university course timetabling problem subject to single and multiple disruptions. European Journal of Operational Research 283(2), 630–646 (2020) https://doi.org/10.1016/j.ejor.2019.11.024

[17] Akkan, C., G¨ulc¨u, A., Ku¸s, Z.: Minimum penalty perturbation heuristics for curriculum-based timetables subject to multiple disruptions. Computers and Operations Research 132 (2021) https://doi.org/10.1016/j.cor.2021.105306

[18] Rosa-Rivera, F., Nunez-Varela, J.I., Ortiz-Bayliss, J.C., Terashima-Mar´ın, H.: Algorithm selection for solving educational timetabling problems. Expert Systems with Applications 174 (2021) https://doi.org/10.1016/j.eswa.2021.114694

[19] Song, T., Chen, M., Xu, Y., Wang, D., Song, X., Tang, X.: Competition-guided multi-neighborhood local search algorithm for the university course timetabling problem. Applied Soft

Computing 110 (2021) https://doi.org/10.1016/j.asoc. 2021.107624

[20] Goh, S.L., Kendall, G., Sabar, N.R.: Improved local search approaches to solve the post enrolment course timetabling problem. European Journal of Operational Research 261(1), 17–29

(2017) https://doi.org/10.1016/j.ejor.2017.01.040

[21] Nagata, Y.: Random partial neighborhood search for the post-enrollment course timetabling problem. Computers and Operations Research 90, 84–96 (2018)

https://doi.org/10.1016/j.cor.2017.09.014

[22] Goh, S.L., Kendall, G., Sabar, N.R.: Simulated annealing with improved reheating and learning for the post enrolment course timetabling problem. Journal of the Operational Research Society 70(6), 873–888 (2019) https://doi.org/10.1080/ 01605682.2018.1468862

[23] Sylejmani, K., Gashi, E., Ymeri, A.: Simulated annealing with penalization for university course timetabling. Journal of Scheduling (2022) https://doi.org/10. 1007/s10951-022-00747-5

[24] Bettinelli, A., Cacchiani, V., Roberti, R., Toth, P.: An overview of curriculumbased course timetabling. TOP 23(2), 313–349 (2015) https://doi.org/10.1007/ s11750-015-0366-z

[25] Akkan, C., G¨ulc¨u, A.: A bi-criteria hybrid genetic algorithm with robustness objective for the course timetabling problem. Computers and Operations Research 90, 22–32 (2018) https://doi.org/10.1016/j.cor.2017.09.007

[26] Wu, C.-C.: Parallelizing a clips-based course timetabling expert system. Expert Systems with Applications 38(6), 7517–7525 (2011) https://doi.org/10.1016/j. eswa.2010.12.116

[27] Shiau, D.-F.: A hybrid particle swarm optimization for a university course scheduling problem with flexible preferences. Expert Systems with Applications 38(1), 235–248 (2011) https://doi.org/10.1016/j.eswa.2010.06.051

[28] Aladag, C.H., Hocaoglu, G., Basaran, M.A.: The effect of neighborhood structures on tabu search algorithm in solving course timetabling problem. Expert Systems with Applications 36(10), 12349–12356 (2009) https://doi.org/10.1016/ j.eswa.2009.04.051

[29] Bagger, N.-C.F., Sørensen, M., Stidsen, T.R.: Benders’ decomposition for curriculum-based course timetabling. Computers and Operations Research 91, 178–189 (2018) https://doi.org/10.1016/j.cor.2017.10.009

[30] Lindahl, M., Mason, A.J., Stidsen, T., Sørensen, M.: A strategic view of university timetabling. European Journal of Operational Research 266(1), 35–45 (2018) https://doi.org/10.1016/j.ejor.2017.09.022

[31] Dunke, F., Nickel, S.: A matheuristic for customized multi-level multi-criteria university timetabling. Annals of Operations Research 328(2), 1313–1348 (2023) https://doi.org/10.1007/s10479-023-05325-2

[32] Sousa, T., Morais, H., Castro, R., Vale, Z.: Evaluation of different initial solution algorithms to be used in the heuristics optimization to solve the energy resource scheduling in smart grids. Applied Soft Computing Journal 48, 491–506 (2016) https://doi.org/10.1016/j.asoc.2016.07.028

[33] Juman, Z.A.M.S., Hoque, M.A.: An efficient heuristic to obtain a better initial feasible solution to the transportation problem. Applied Soft Computing Journal 34, 813–826 (2015) https://doi.org/10.1016/j.asoc.2015.05.009

[34] Amaliah, B., Fatichah, C., Suryani, E.: A supply selection method for better feasible solution of balanced transportation problem. Expert Systems with Applications 203 (2022) https://doi.org/10.1016/j.eswa.2022.117399

[35] Viana, B.M.F., Pereira, L.T., Toledo, C.F.M., Santos, S.R., Maia, S.M.D.M.: Feasible–infeasible two-population genetic algorithm to evolve dungeon levels with dependencies in barrier mechanics. Applied Soft Computing 119 (2022) https://doi.org/10.1016/j.asoc.2022.108586

[36] Song, T., Liu, S., Tang, X., Peng, X., Chen, M.: An iterated local search algorithm for the university course timetabling problem. Applied Soft Computing Journal 68, 597–608 (2018) https://doi.org/10.1016/j.asoc.2018.04.034

[37] Pillay, N., Ozcan, E.: Automated generation of constructive ordering heuristics for ¨ educational timetabling. Annals of Operations Research 275(1), 181–208 (2019) https://doi.org/10.1007/s10479-017-2625-x

[38] Goh, S.L., Kendall, G., Sabar, N.R.: Monte carlo tree search in finding feasible solutions for course timetabling problem. International Journal on Advanced Science, Engineering and Information Technology 9(6), 1936–1943 (2019) https: //doi.org/10.18517/ijaseit.9.6.10224

[39] Zeitrag, Y., Figueira, J.R., Horta, N., Neves, R.: Surrogate-assisted automatic evolving of dispatching rules for multi-objective dynamic job shop scheduling using genetic programming. Expert Systems with Applications 209 (2022) https: //doi.org/10.1016/j.eswa.2022.118194

[40] Nagar, J., Chaturvedi, S.K., Soh, S., Singh, A.: A machine learning approach to predict the k coverage probability of wireless multihop networks considering boundary and shadowing effects. Expert Systems with Applications 226 (2023) https://doi.org/10.1016/j.eswa.2023.120160

Appendix A Increment algorithms

Appendix B Initial solutions

Appendix C Neighbourhood structures