Did you know that calculating university or college timetables is one of the most difficult problems to solve? In this post, we present the fundamental aspects of this problem and explain how we can improve the schedules of educational institutions.
The School Timetabling Problem (STP) consists of determining the scheduling of “academic activities” for a set of degree programmes over some time. The scheduling of activities must satisfy the established constraints of students, teachers and classrooms.
Bill Gates explains how ingenuity can be put at the service of different criteria and requirements. At the age of sixteen, he developed a programme to organise class timetables for his high school:
“Of course, a whole new dimension of relevance came when I was asked to do a computerized class schedule for the high school.
It was complex, but ultimately very rewarding. By the time I was done, I found that I had no classes at all on Fridays. And even better, there was a disproportionate number of interesting girls in all my classes.”
Such problems range from conventional lesson planning in schools and universities to the development of examination timetables.
STP problems are NP-Complete problems, which means that as the size of the problem grows, its complexity and solving time increase at a much faster rate. This makes it challenging to calculate schedules automatically.
In many schools and universities, planning the timetable of classes and exams is done manually, which requires a lot of effort and time. In addition, manual planning often leads to errors or not always being able to satisfy all the constraints of the problem.
Scheduling is typically done iteratively, beginning with a blank timetable in which the classes of the different groups are designed. This results in a heterogeneous quality of timetables for students in different groups (it is easier to attend well to the first ones, but becomes increasingly complicated as more groups are added). The same is true for teachers.
In general, a manual school timetable:
- It is a lengthy process and requires a lot of time and effort from the planning team.
- Due to the long design time of the calendar, it is not possible to test different configurations or improvements, which makes the planning inflexible.
- As a result, the quality of students’ timetables may be affected, even causing the student to miss some classes due to overlapping.
- The inflexibility of timetables can make them incompatible with the availability of teachers, which makes recruitment processes and conditions for teachers challenging.
So far, we have only talked about the complexity of finding a schedule that meets the restrictions of the problem since solving the problem alone depletes the planners’ time. However, if two different people were to develop the schedule for the same university, the result would not be the same. So what makes one schedule better than another? Or, put another way, what are the terms of the objective function of this problem?
If we were to ask Bill Gates, he would be clear. But students shouldn’t be the ones to decide how they want their timetable. Indeed, the objective function of a model that solves an STP should be multi-objective, to strike a balance between the preferences of students and teachers without neglecting how the school or university infrastructure is used. Examples of the terms of the objective function could be:
- The number of blank hours between classes of a student.
- The number of blank hours between a teacher’s classes.
- The number of days the student or teacher has to be in the classroom.
- The homogeneity of subject loads.
- Homogeneity of classroom occupancy throughout the day.
But if we have explained that these problems cannot be solved in a reasonable amount of time as the problem grows, what can large academic institutions do? Instead of obtaining the optimal solution to the problem, what is sought is to find the best possible solution in the time available to solve the problem. This is where operational research comes in to solve educational planning, using mathematical techniques such as heuristics, decompositions, exact models or hybrid models in such a way that institutions can obtain schedules that improve the quality of the timetable for both students and teachers or that satisfy the preferences of both in a balanced way.
Some studies have tried to define a common structure that characterises planning problems, but there is no general problem that fits all cases. Precisely because each institution has its particularities, the problem varies and the resolution technique has to be adapted to achieve better solutions and meet specific requirements. Among others, it is worth highlighting different techniques that can be found in the literature such as Graph Colouring Heuristics (Yanez and Ramirez, 1999), Tabu search (Azimi, 2005), Genetic Algorithms (Burke and Petrovic, 2002), and Mathematical Programming (Aizam and Liong, 2013) and (Daskalaki and Housos, 2004).
The use of these techniques combined with the experience of the academic institutions’ planners makes it possible to obtain better school plans with less effort and without errors. At baobab solutions we provide academic institutions with optimisation services designed to suit their operations in such a way as to enable planners to optimise their teaching plans:
- Evaluate more options in less time.
- Dedicate less effort to balancing planning and more to exploring alternative planning.
- Analyse policy changes and their impact on the planning outcome.
- Evaluate the impact of incorporating more students.
- Evaluate the impact of the implementation of new courses.
- Identify future resource needs.
Some tasks can only be done by one person: negotiating changes with a teacher, getting a budget for an extension of infrastructure, designing new curricula, and so on.
Therefore, it makes sense to have a good planning tool to free managers from the tedious task that a machine can do and allow them to focus on all the aspects that a person has to do.
