Project funded by the Escuela Politécnica Nacional de Quito (US$9,902), January
2013 – December 2013.
The timetabling problem consists in the allocation, subject to side constraints,
of a number of class sessions and associated resources (usually lecturers and
classrooms) to a limited number of periods, so that each session is taught by a lecturer in a suitable classroom and a given period within a planning horizon, which is usually a week. There are several ways to model this problem; solution
algorithms of both heuristic and exact type have been proposed [BP02, S99].
The assignment of class sessions is subject to hard and soft constraints.
Hard constraints are those that must be fulfilled by any feasible solution and soft
constraints are those that are desirable but not essential. The latter restrictions
allow us to evaluate the quality of the obtained solution.
The aim of this project is to formulate an integer linear programming model
for the timetabling problem taking into account the specific conditions present
at the Faculty of Sciences of the Escuela Politécnica Nacional (EPN) in Quito.
The academic planning at the Faculty of Sciences is carried out twice a year and
involves the following activities: courses to be offered in the following semester
are selected, lecturers are assigned to them, the expected number of enrolled
students is estimated for each course, and the type of classroom required (small
room, large room, computer lab, etc) is specified for each lecture. According to
the registration procedures established at EPN, students enroll in the courses only
after the timetable has been made available to the public. Moreover, students are
not allowed to register simultaneously in courses that have conflicting timetables.
Each course consists of a number of weekly sessions whose duration varies
between one and three periods of 60 minutes each. Lecturers are assigned to
the courses before planning the timetable, but, as explained above, information
about enrollment of students is not yet available at this point.
Our model addresses the task of assigning class sessions to available periods.
Besides of the usual restrictions, three main features of the problem that we have
- For each group of students pursuing the same degree, the courses they must
take during their career are organized in a curriculum. Among other things,
this curriculum specifies a level for each course (e.g. Calculus belongs to
level I, Multivariate Calculus belongs to level II) and a set of prerequisites,
which are a list of previous courses that a student must have approved in
order to be admitted in a course (e.g. Linear Algebra II has Linear Algebra
I as prerequisite). Clashes between courses of the same level is prohibited,
and clashes between courses of different levels is penalized according to a
distance criterion among levels.
- The Faculty of Sciences offers four careers: Physics, Mathematics, Mathematical
Engineering, and Economics. They share some courses located at different levels of the corresponding curricula, which have to be programmed
in such a way as to avoid conflicts in all careers.
- Lecturers indicate their schedule preference. For each available period, a
lecturer can specify three levels of preference regarding his availability to
give a lecture: “want”, “could”, “cannot”.
For the formulation of the model the following hard constraints are considered:
- No lecturer can teach more than one class session per period, and his
availability schedule must be taken into account.
- Clashes between course sessions belonging to the same level (in some curriculum)
are not allowed.
- Each session of a course must be scheduled in a classroom of the appropriate
type, taking into account room availability.
- For each course, no more than one session per day can be scheduled.
Moreover, the following weak constraints are included as an objective function
in our model:
- The preference schedule of all lecturers should be satisfied.
- Clashes between courses of different levels should be penalized, according
to the distance between these levels.
The model was implemented as a computational tool to support the timetabling
process at EPN. This tool comprehends a database system for data collection
and report making, and a computation module based on the C++ programming
language, which makes use of the SCIP solver libraries [A09]. The system is
accessed via a web interface and can be configured to execute the computations
remotely at MODEMAT’s HPC facilities.
Table 5 depicts some results obtained in computational experiments on twelve
problem instances. Instances 10 to 12 are real-world instances corresponding to
three academic semesters at EPN. The other instances were obtained by simplification
of the real instances in several ways. For example, the number of offered
careers or courses was reduced. Practical problem instances involve around 100,000 binary variables and between 1.5 and 2 million constraints. None of the
instances could be solved to optimality using SCIP in its standard configuration.
In fact, for two of the three real-world instances, SCIP was not able to compute
a feasible solution between the prescribed time timit of two hours. A sequential
insertion and a local improvement heuristic were devised to feed the solver with
an initial solution at the root of the branch-and-bound tree. However, in most
test instances, this initial solution could not be further improved by the solver
within a reasonable computing time horizon. The main difficulty to overcome is
the obtention of good lower bounds. Further results are reported in [HT14, H14].
- [A09] T. Achterberg. SCIP: Solving Constraint Integer Programs. Mathematical
Programming Computation, Vol. 1(1):1–41, 2009.
- [BP02] E. Burke and S. Petrovic. Recent Search Directions in Automated Timetabling. European Journal of Operational Research, Vol. 140(2):266–280, 2002.
- [H14] María Belén Heredia. Modelo de programación lineal entera para la generación
de horarios de clase en la universidad. Graduate Thesis in Mathematical
Engineering, Escuela Politécnica Nacional, 2014.
- [HT14] María Belén Heredia and Luis M. Torres. An Integer Programming
Model for Scheduling Classes at the Escuela Politécnica Nacional in Quito.
Proceedings of the VIII Workshop on Applied Combinatorial Optimization
ALIO/EURO 2014, Montevideo, Uruguay, 2014.
- [S99] A. Shaerf. A Survey of Automated Timetabling. Artificial Intelligence
Review, Vol. 13(2):87–127, 1999.