Joint Training Offer Selection and Course Timetabling Problems: Models and Algorithms
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%.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:70736", author = "Gianpaolo Ghiani and Emanuela Guerriero and Emanuele Manni and Alessandro Romano", title = "Joint Training Offer Selection and Course Timetabling Problems: Models and Algorithms", 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.", volume = "9", number = "7", pages = "1731-6", }