A Two-Phased Metaheuristic Method for Solving High School Course Timetabling

Subject Areas : Statistics

Mohammad Sadegh Shiri ¹ , seyed mostafa khorramizadeh ² , Pari Farokhi ³

1 - Department of Mathematics, Faculty of Science, Arsanjan Branch, Islamic Azad University of Arsanjan, Iran
2 - Shiraz University of Technology, Shiraz, Iran
3 - Shiraz University of Technology, Shiraz, Iran

Received: 2021-11-03 Accepted : 2022-01-31 Published : 2024-01-18

Keywords: مساله بهینه‌سازی ترکیبیاتی, مساله زمان‌بندی, محدودیت سخت و نرم, روش فراابتکاری,

Abstract :

In this paper, the high school timetabling problem is studied. Here, an efficient hybrid algorithm is presented for the resolution of the problem. The presented algorithm has two phases. In the first phase hard constraints are handled using an integer programming problem. Moreover, suitable decision variables and constraints are introduced to express the problem of the first phase as an integer programming problem. Many constraints are being considered in this paper for the first time and are specific to the high schools in Iran. The feasible solution obtained in the first phase is used as the input of the second phase. In the second phase an efficient hybrid metaheuristic algorithm is presented for improving the quality of the feasible solution of the first phase. The presented metaheuristic algorithm is a combination of the variable neighborhood search algorithm and Tabu search algorithm. The presented algorithm of the second phase, is applied on the solution obtained from the first phase to improve its quality. Finally, numerical results on real world instance are presented to justify the efficiency of the proposed algorithm. The test instances are taken from real world applications that corresponds to two high schools in Shiraz city. The numerical results show that our presented algorithm is able to compute high quality solutions for the real world instances that have been considered in this paper. It is also possible to apply the presented algorithm of the second phase only to improve the quality of existing timetabling provided by experience.

References:


[1] Werra D., “An introduction to timetabling”, European Journal of Operational Research, 19(2), 151-162 (1985).

[2] Schaerf A., “A survey of automated timetabling”, The Artificial Intelling Revolution, 13(2), 87-127 (1999).

[3] Carrasco M. P. and Pato M. V., “A comparison of discrete and continuous neural network approaches to solve the class/teacher timetabling problem”, European Journal of Operational Research, 153(2) 63-79 (2004).

[4] de Haan P., Landman R., Post G and Ruizenaar H., “A case study for timetabling in a Dutch secondary school”, Lecture Notes in Computer Science, Springer-Verlag, In Burke EK, Rudova H (Eds). Proceedings of PATAT , 3867, 267-279 (2006).

[5] L. Saviniec, M. O. Santos and A. M. Costa, Parallel local search algorithms for high school timetabling problems, European journal of Operations Research, 265(1), 81-98, 2018.

[6] Zhang D., Liu Y., M’Hallah R. and Leung S., “A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems”, European Journal of Operational Research, 203(3), 550-558 (2010).

[7] Pillay N., “A survey of school timetabling research”, Annals of Operations Research, ISSN 0254-5330 (2013).

[8] Tassopoulos I. X. and Beligiannis G. N., “A hybrid particle swarm optimization based algorithm for high school timetabling problems”, Applied Soft Computing, 3472-3489 (2012).

[9] Odeniyi O. A., Omidiora E. O., Olabiyisi S. O. and Aluko., “Development of a modified simulated annealing to school timetabling problem”, International Journal of Applied Information Systems, 8(2), 16-24 (2015).

[10] Ghazali Talbi E.L., “Metaheuristics from Design to Implementation”, Wiley, University of Lille-Cnrs-Inria, (2009).

[11] V. I. Skoullis, I. X. Tassopoulos and G. N. Beligiannis, Solving the high school timetabling problem using a hybrid cat swarm optimization based algorithm, Applied Soft Computing, 52, 277-289, 2017.

[12] L. Saviniec and A. A. Constantino, Effective local search algorithms for high school timetabling problems, Applied Soft Computing, 60, 363-373, 2017.