Joint Training Offer Selection and Course Timetabling Problems: Models and Algorithms

Authors: Gianpaolo Ghiani, Emanuela Guerriero, Emanuele Manni, Alessandro Romano

Abstract:

In this article, we deal with a variant of the classical course timetabling problem that has a practical application in many areas of education. In particular, in this paper we are interested in high schools remedial courses. The purpose of such courses is to provide under-prepared students with the skills necessary to succeed in their studies. In particular, a student might be under prepared in an entire course, or only in a part of it. The limited availability of funds, as well as the limited amount of time and teachers at disposal, often requires schools to choose which courses and/or which teaching units to activate. Thus, schools need to model the training offer and the related timetabling, with the goal of ensuring the highest possible teaching quality, by meeting the above-mentioned financial, time and resources constraints. Moreover, there are some prerequisites between the teaching units that must be satisfied. We first present a Mixed-Integer Programming (MIP) model to solve this problem to optimality. However, the presence of many peculiar constraints contributes inevitably in increasing the complexity of the mathematical model. Thus, solving it through a general-purpose solver may be performed for small instances only, while solving real-life-sized instances of such model requires specific techniques or heuristic approaches. For this purpose, we also propose a heuristic approach, in which we make use of a fast constructive procedure to obtain a feasible solution. To assess our exact and heuristic approaches we perform extensive computational results on both real-life instances (obtained from a high school in Lecce, Italy) and randomly generated instances. Our tests show that the MIP model is never solved to optimality, with an average optimality gap of 57%. On the other hand, the heuristic algorithm is much faster (in about the 50% of the considered instances it converges in approximately half of the time limit) and in many cases allows achieving an improvement on the objective function value obtained by the MIP model. Such an improvement ranges between 18% and 66%.

Keywords: Heuristic, MIP model, Remedial course, School, Timetabling.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1108406

References:

[1] C. Gotlieb, The construction of class-teacher timetables, in: IFIP congress, Vol. 62, 1963, pp. 73–77.
[2] N. L. Lawrie, An integer linear programming model of a school timetabling problem, The Computer Journal 12 (4) (1969) 307–316.
[3] M. Sørensen, F. H. Dahms, A two-stage decomposition of high school timetabling applied to cases in denmark, Computers & Operations Research 43 (2014) 36–49.
[4] S. M. Al-Yakoob, H. D. Sherali, Mathematical models and algorithms for a high school timetabling problem, Computers & Operations Research 61 (2015) 56–68.
[5] R. Alvarez-Valdes, E. Crespo, J. M. Tamarit, Design and implementation of a course scheduling system using tabu search, European Journal of Operational Research 137 (3) (2002) 512–523.
[6] Z. L¨u, J.-K. Hao, Adaptive tabu search for course timetabling, European Journal of Operational Research 200 (1) (2010) 235–244.
[7] S. Abdullah, H. Turabieh, On the use of multi neighbourhood structures within a tabu-based memetic approach to university timetabling problems, information sciences 191 (2012) 146–168.
[8] A. Gunawan, K. M. Ng, K. L. Poh, A hybridized lagrangian relaxation and simulated annealing method for the course timetabling problem, Computers & Operations Research 39 (12) (2012) 3074–3088.
[9] S. S. Brito, G. H. Fonseca, T. A. Toffolo, H. G. Santos, M. J. Souza, A sa-vns approach for the high school timetabling problem, Electronic Notes in Discrete Mathematics 39 (2012) 169–176.
[10] P. Guo, J.-x. Chen, L. Zhu, The design and implementation of timetable system based on genetic algorithm, in: Mechatronic Science, Electric Engineering and Computer (MEC), 2011 International Conference on, IEEE, 2011, pp. 1497–1500.
[11] S. Yang, S. N. Jat, Genetic algorithms with guided and local search strategies for university course timetabling, Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on 41 (1) (2011) 93–106.
[12] C. Nothegger, A. Mayer, A. Chwatal, G. R. Raidl, Solving the post enrolment course timetabling problem by ant colony optimization, Annals of Operations Research 194 (1) (2012) 325–339.
[13] C. Valouxis, E. Housos, Constraint programming approach for school timetabling, Computers & Operations Research 30 (10) (2003) 1555–1572.