A Multiobjective Programming Model for University Course Timetabling Problem

Document Type : Original Paper

Authors

Department of Mathematics, Faculty of Mathematic Science, Vali-e-Asr University of Rafsanjan, Iran

Abstract

The university timetabling problem is one of principal management problem in the beginning of each semester in the colleges. There are many limitations related to classes, teachers and students that increase computational complexity and put the problem in the field of ”NP-Hard” class. In this study we tried to solve this problem in terms of zero-one multiobjective programming and devise a mathematical model of the problem using a minimum number of variables. The proposed approach is based on activity in order to reduce the number of variables to modeling the problem in an acceptable level.

Keywords

Main Subjects


[1] Abuhamdah, A., Ayob, M., Kendall, G., and Sabar, N. R., Population based local search for universitycourse timetabling problems, Appl. Intell., 40 (2014), 44-53.
[2] Akkan, C. and Gülcü, A., A bi-criteria hybrid genetic algorithm with robustness objective for the
course timetabling problem, Comput. Oper. Res., 90 (2018), 22-32.
[3] Assi, M., Halawi, B., and Haraty, R. A., Genetic algorithm analysis using the graph coloring method
for solving the university timetable problem, Procedia. Comput. Sci., 126 (2018), 899-906.
[4] Aziz, N. L. A. and Aizam, N. A. H., A survey on the requirements of university course timetabling,World Acad. Sci. Eng. Technol. Int. J. Math. Comput. Phys. Electr. Comput. Eng., 10 (2016), 236-241.[5] Bagger, N. C. F., Desaulniers, G., and Desrosiers, J., Daily course pattern formulation and valid inequalitiesfor the curriculum-based course timetabling problem, J. Sched., 22 (2019), 155-172.[6] Budiono, T. A. and Wong, K. W., A pure graph coloring constructive heuristic in timetabling, in Proc.Int. Conf. Comput. Inf. Sci. (ICCIS), (2012), 307-312.
[7] Burke, E. K. and Petrovic, S., Recent research directions in automated timetabling, Eur. J. Oper. Res.,140 (2002), 266-280.[8] Burke, E. K., McCollum, B., Meisels, A., Petrovic, S., and Qu, R., A graph-based hyper-heuristic foreducational timetabling problems, Eur. J. Oper. Res., 176 (2007), 177-192.[9] Chen, R. M. and Shih, H. F., Solving university course timetabling problems using constriction particleswarm optimization with local search, Algorithms, 6 (2013), 227-244.
[10] Chen, M. C., Sze, S. N., Goh, S. L., Sabar, N. R. and Kendall, G., A survey of university course
timetabling problem: perspectives, trends and opportunities, IEEE. Access., 9 (2021), 106515-
106529.[11] Feng, X., Lee, Y., and Moon, I., An integer program and ahybrid genetic algorithm for the universitytimetabling problem, Optim. Methods. Softw., 32 (2017), 625-649.
[12] Goh, S. L., Kendall, G., and Sabar, N. R., Simulated annealing with improved reheating and learningfor the post enrolment course timetabling problem, J. Oper. Res. Soc., 70 (2019), 873-888.
[13] Goh, S. L., Kendall, G., Sabar, N. R., and Abdullah, S., An effective hybrid local search approach
for the post enrolment course timetabling problem, Opsearch., 57 (2020), 1131-1163.
[14] Gotlieb, C., The construction of class-teacher timetables, in Proc. IFIP Congress, 62 (1963), 73-77.[15] Gunawan, A., Ng, K. M., and Poh, K. L., A hybridized lagrangian relaxation and simulated annealingmethod for the course timetabling problem, Comput. Oper. Res., 39 (2012), 3074-3088.
[16] Habashi, S. S., Salama, C., Yousef, A. H., and Fahmy, H. M., Adaptive diversifying hyper-heuristicbased approach for timetabling problems, in Proc. IEEE 9th Annu. Inf. Technol., Electron. MobileCommun. Conf. (IEMCON), (2018), 259-266.
[17] Lindahl, M., Mason, A. J., Stidsen, T., and Sørensen, M., A strategic view of university timetabling,Eur. J. Oper. Res., 266 (2018), 35-45.
[18] Nagata,Y., Random partial neighborhood search for the post-enrollment course timetabling problem,Comput. Oper. Res., 90 (2018), 84-96.
[19] Nothegger, C., Mayer, A., Chwatal, A., and Raidl, G. R., Solving the post enrolment course
timetabling problem by ant colony optimization, Ann. Oper. Res., 194 (2012), 325-339.
[20] Oktavia, M., Aman, A., and Bakhtiar, T., Courses timetabling problem by minimizing the number ofless preferable time slots, IOP Conf. Ser.: Mater. Sci. Eng. 166 (2017), 012025.
[21] Sabar, N. R., Ayob, M., Kendall, G., and Qu, R., A honey-bee mating optimization algorithm for
educational timetabling problems, Eur. J. Oper. Res., 216 (2012), 533-543.
[22] Song, T., Liu, S., Tang, X., Peng, X., and Chen, M., An iterated local search algorithm for the
university course timetabling problem, Appl. Soft. Comput., 68 (2018), 597-608.
[23] Teoh, C. K., Wibowo, A., and Ngadiman, M. S., Review of state of the art for metaheuristic techniquesin academic scheduling problems, Artif. Intell. Rev., 44 (2015), 1-21.
[24] Turabieh, H., Abdullah, S., McCollum, B., and McMullan, P., Fish swarm intelligent algorithm forthe course timetabling problem, in Rough Set and Knowledge Technology, (2010), 588-595.
[25] Wang, B., Geng, Y., and Zhang, Z., Applying genetic algorithm to university classroom arrangementproblem, J. Phys. Conf. Ser., 1325 (2019), 012157.