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 considered are:

• 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.

Current development:

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].

References

• [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.