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.