How to collect the information to create your timetable

Drawing up timetables is a task that involves a large number of people, from the head of studies to the heads of department and other teachers at the school. A variety of information has to be gathered: the subjects that each teacher will teach to each group of students, the times at which they can or prefer to teach their class units, or the classroom where they wish to teach.

In times of pandemic covid-19 online tools avoid face-to-face meetings, making it easier to organise them, as well as favouring social distancing and the prevention of infections. Therefore, finding a tool that allows online collection of all the information necessary to obtain valid and optimal schedules is essential. But what are the main functionalities that these tools should meet?

  • Allowing the division of work into departments. The insertion of this data should be possible online and in parallel, giving each department independence, and speeding up the compilation of all the information.
  • Defining the teacher who will teach each subject. Each educational institution has certain criteria for assigning teachers to each subject and course. The software chosen must allow each teacher to be associated with the class units he/she will teach in accordance with these criteria.
  • Recording the availability of each teacher’s timetable. A teacher may have a reduction in the number of hours worked, may teach in another school, or may prefer to have part of his or her timetable free. Collecting all these restrictions and preferences is crucial in order to obtain a good timetable.
  • Collecting other preferences about the teaching staff. Gathering the preferences of the teachers will allow us to know their needs, and thus obtain a good schedule that satisfies them. Knowing which teachers want to be tutors or do on-call hours will increase the satisfaction of the teaching staff with the timetable.
  • Specifying details about the class units. Doing this process online should not be a handicap to the quality of the process. Therefore, indicating the classroom where a class unit should or is preferred to be held, or suggesting the weekly distribution of class times for each subject is necessary during data entry.

The Peñalara collection of preferences tool not only covers all these functionalities, but goes further. If you wish, it allows each head of department to take charge of the creation of the class units of his/her department, in order to free the head of studies from this task, and to speed up and distribute the work among more people. In addition, this web application is fully integrated with GHC, both to publish the timetable so that the heads of department can work with it, and to collect the data that they have entered. Thanks to this, we can achieve better schedules and save time.

You can find information about it in these video tutorials, go to the Peñalara website for more information, or sign up for any of the weekly demos.

Pedagogical criteria in timetables

Each academic institution may establish guidelines to direct the implementation of its timetables. These are not always formally expressed, but there is often a document describing the directives to be followed, in accordance with the school’s objectives. In other cases, they may be established by the school management or the head of studies during their elaboration.

Some of these criteria for class units could be:

  • Avoiding overlapping all weekly class units of a particular subject:
    • Early in the morning, late in the afternoon or after the break.
    • On consecutive days.
    • At the same time of day.
  • Preventing classroom changes for students or teachers, or follow certain preferences for the allocation of classrooms, workshops, gymnasiums, etc.
  • Ensuring that certain subjects are taught at earlier times or, by contrast, that others are more appropriate to be taught at later times. In other words, establish which subjects will be taught in certain time slots.
  • Avoiding having a subject that finishes late one day and starts early the next day.

Other pedagogical criteria attributable to the teachers’ timetable would be:

  • Balancing the teaching load or daily workload.
  • Avoiding more than a certain number of class units in a row, attendance before or after break time, etc. in order to allow for rest intervals.
  • Ensuring that teachers’ timetables are compact, etc.

Whether or not these formalised directives exist, it is necessary to consider the need for them and the weight to be given to them in each particular educational institution. Once we know what we are looking for and to what extent, we should be able to find, in practice, a timetable that satisfies an optimal compromise, which, while meeting academic requirements, observes pedagogical criteria as far as possible.

The question therefore is, can the pedagogical criteria to be followed be shaped in order to optimally fit the required academic timetable, as far as possible?

The answer is yes. With GHC, each school will be able to model its own pedagogical criteria, giving them weight and adjusting flexible preferences on the different elements that make up the timetable. The solutions provided by the GHC engine will be an optimal solution according to the criteria and preferences established in each case.

In order to achieve the best results, it is necessary to provide enough flexibility in the possible solutions. If strict conditions are used, they may make it difficult to observe the criteria when optimising the outcome. For example, if a pedagogical criterion determines that certain groups of students should preferably be taught in P.E. late in the day, but on the other hand, either the gymnasium or the teachers who teach P.E. are forbidden to do so in the curriculum, the pedagogical criterion will be impossible to satisfy.

For this reason, it is essential to define the strict conditions to be imposed on the solutions in the beginning. As a premise, we can state that no more strict conditions should be imposed than those that are really justified, otherwise the necessary flexibility to observe the pedagogical criteria will be restricted. It is important to allow the optimisation process to achieve the best solution.

In summary, we can affirm that GHC will observe the pedagogical criteria that each educational institution weighs up and will do so in an optimal way, taking advantage of the flexibility that exists in the solutions. In order to find the best timetables, it is preferable to take advantage of this capacity, avoiding more strict conditions than those that are really necessary.

Integration with other applications

Exchanging data between different software applications may seem to be something fairly simple and straightforward, but this is generally not true. First of all, software applications use identifiers that are usually not compatible. For example, using the DNI as a key to identify people, we could establish a correspondence between their data in the different applications. But if the keys are not the same, for example, if each application creates its own codes, matching becomes impossible without hard and laborious manual work. Another obvious reason is that the relationships between the data and their internal structures are also application-specific.

Integrating data between different applications requires well-designed and documented interfaces through which data can be exposed and software can interact. There is no other way. But this condition, while necessary, is not enough. In addition to an interface, it must be possible to establish a correspondence between the codes used in the two applications to identify their data elements.

In the case of an application that makes a service request to another application, the first one must provide its keys so that it can interpret the result once it has been resolved. In other words, if an application requests a task to be solved, it must provide, through the common interface, in besides the information of the request itself, the necessary keys to understand the result it receives. Let us suppose an application that requests another application for a service to resolve an academic timetable. In this case, the resolved timetable should be expressed using keys so that the requesting application can recognise it. In this way it will be able to identify teachers, subjects, etc. in the solution. The agreement of formats and keys between the two applications must be precise for it to work and both parties must necessarily collaborate in this.

There are some applications that expose their own exchange interfaces without being fully operational, with design weaknesses that prevent the output from being received correctly. It is therefore necessary to implement well-defined and documented open interfaces for inter-application communication. In fact, there are standardisation organisms that establish them. Alternatively, open interfaces associated with consolidated products published for this purpose could be adopted as standards.

Peñalara Software has published the internal GHC storage format to be used as an exchange interface. The XML-GHC format is complete. Everything that is configured with the planner, as well as the results that GHC creates, can be expressed with this model.

In addition, along with the development of a new engine that we hope to offer soon as a remote service, we have open JSON interfaces that can be consulted through the public GitHub repository and are associated with development libraries also available, in this case, in Apache Maven. With this project we intend to offer services for the creation of timetables to the academic management application ecosystem, and thus ultimately facilitate the work of users.

Is it possible to identify the presence of conditions that prevent results?

Is it possible to identify the presence of conditions that prevent results? We can happily say that we have an engine capable of finding efficiently the most challenging timetables. However, as you know, in order to optimise the timetables, it is essential to find complete results in advance. Unfortunately, when working with the planner, you will have experienced that impossible conditions are introduced. Perhaps the most controversial issue in using the software is how to determine, before using the engine, whether there are impossible conditions. What conditions prevent full timetables?

The engine is the component that finally has to find the solution, so it is not always possible to know in advance whether there are conditions that cannot be fulfilled. Indeed, this is strictly true; there are impossible conditions that are very difficult to analyse. However, it is possible to identify many of the impossible conditions; most of them are introduced accidentally, preventing the full results.

The GHC engine fits results very quickly. This is a fact. If the engine cannot find results quickly and fails to fit any class unit in repeated attempts, most of the time it is because there are some conditions that prevent it and they must be debugged. Otherwise, the engine takes a little more time and effort to find a complete solution if they are more unusual. Should we wait? And if we suspect that there is some impossible condition, what is it?

We have two processes that can help us to check if there are conditions that are impossible to fulfil before using the engine: the validation of the planner’s configuration and the analysis of minimum sets that are impossible to fit.

The validation process looks at some of the most common causes that may prevent full results. For example, that a group of students have been assigned more class units than the ones that fit into their time frame or that different class units have been set up at the same time with the same teacher.

On the other hand, the analyser tries to solve separately the timetables of each teacher, of each group of students, etc. Thus, if it cannot solve any of these subsets, it will reduce it to a minimum of class units that are impossible to fit in. If the analyser finds a minimum set of class units that do not fit, it will be easier to see what is happening, that is, what conditions overlap with each other within this reduced number of class units.

Even though it is not the most common, as we have already said, there may be timetables for which the engine does not find a solution that apparently does not involve conflicts. Indeed, there are timetables without validation errors and for which the analyser does not find conflicts, which nevertheless contain conditions that prevent solutions. In these cases we have a third tool that can help us considerably: the debugger. The debugger allows to launch the engine and also the analyser, without any of the strict conditions initially configured. The debugger is very useful to launch tests by relaxing the strict conditions and thus know which ones prevent the solutions.

There are other debugging strategies, such as trying to assign directly from the editor the class units that have not been able to fit in to see which messages appear or to check in the incomplete result where there are gaps in the group timetable, just in case the problem is a meeting or the presence of an excess of positions forbidden to teachers, coinciding at the same time.

We do not want to forget that the task of making academic timetables is complex enough so that, in addition to having the best tools, the expertise of those who use them is necessary. Be sure to ask us for all the help you need. In any case, the merit of making the best timetables will always be yours.

Is it possible to have the perfect timetable?

Fitting in the weekly timetables of a moderately big or complex school is not an easy task. This is well known to those who have faced sometimes this problem and, to a greater extent, to those who have the responsibility to make so every year; a real puzzle has to be solved. But if it is difficult to find a solution that meets the minimum requirements, finding the best solution seems like an impossible task. And this is precisely the question we ask: Is it possible to make perfect timetables?

Clearly, and unfortunately, we must say that the perfect timetable is impossible and there are several reasons to affirm it. The first and most obvious is that any model for expressing what is sought will have imperfections. Indeed, the mathematical model through which a weight function is calculated to obtain the optimum timetable and its application to the elements included in the timetable: students, teachers, class units, etc., will always be an approximation to reality which, at best, will be estimated precisely corresponding to what is sought.

The second reason, and this is not so obvious, is that the set of solutions is so high that exhaustive searching is impossible, even for the fastest computer in the world.

Do you remember the paradox of the legend of the inventor of chess?

According to legend, a Persian king, who liked the game of chess, commanded to call his inventor to reward him for his ingenuity. The king recklessly told him to ask for whatever he wanted and the inventor answered: I settle for 1 grain of wheat for the first square of the board, 2 for the second, 4 for the third, 8 for the fourth and so on up to the 64 square of the board. That is the sum of the series 1+2+4+8… until completing 64 terms in geometric progression. The king thought that what he was asking for was a trifle and ordered to prepare the prize requested but doing the calculations they realized that it was impossible to fulfill the order, because the sum of the grains of the 64 boxes was nothing less than the amount of 36,893,488,147,419,103,231 grains. If in each Kilogram of wheat approximately 25,000 grains fit, then the result would be about 1,475,739,525,896 tons. If the largest freighter could hold up to 186,000 net tons, it would take about 8 million huge freighters to transport all the wheat. More than 1000 times the annual world production of wheat.

Knights Templar playing chess

This paradox also occurs with the problem of making academic timetables; it seems that it would be relatively easy to try all possible solutions with a computer but, in fact, it is impossible. The point is that the number of combinations grows exponentially and it would take years of calculation, even with the most powerful computer, to go through them all. The processes that solve this puzzle are studied through a mathematical and computational discipline that tries to give the best possible solution, in reasonable times, to excessively complex problems.

The Peñalara GHC Timetable Generator for Educational Institutions uses a software capable of finding solutions and making them optimal in an extraordinarily effective way in short enough periods of time even in the most complicated cases. The good news is that this type of intractable problems through exhaustive search processes can be solved to a large extent using intelligent algorithms. Finally, we can state with great satisfaction and relief for those who have the responsibility of making the timetables each course, that the ‘perfect’ timetables, in practice, are possible.