Sorting Out Messy School Timetables

No wonder teachers have a hard time designing school timetables at the start of each year. The issue has been cataloged by scientists as an NP-hard problem, right next to other classic logistics puzzles, such as the traveling salesman, and the crystal packing problems. School management officials and teachers are not the ones to blame for their inability to form a cohesive school timetable. They fail where other great scientific minds failed before them as well. An optimum setup can never be achieved, some say. However, the next best thing can, but only after numerous and difficult calculations.

“An optimization tool could assist these planners in order to reduce the time they need to build the timetables and to improve the quality of the solutions,” Brazilian researchers from the University of Campinas Institute of Computing say. Scientists Arnaldo Vieira Moura and Rafael Augusto Scaraficci created a new instrument for assisting teachers, and others in their position, called Greedy Randomized Adaptive Search Procedure (GRASP). All the new heuristic program needs to function is the introduction of the specific requirements that each school has.

Still, the experts note, GRASP will most likely never yield the optimum solution to the problems. Rather, it will simply help planners move past the most severe problems easier. Some issues will, however, endure. For all intents and purposes, such a heuristic tool creates the best compromise possible, its developers note. Details of the tool appear in the latest issue of the respected International Journal Operational Research, in a paper entitled “A GRASP strategy for a more constrained School Timetabling Problem.” Thus far, the model has been successfully implemented in three Brazilian schools, and is scheduled to enter testing at other locations around the country as well.

Some of the most complex problems that the new algorithms need to compensate for include the fact that some teachers present several objects to different classes. During the same day, students must receive a maximum of two or three lectures on the same subject, and if they do, they must be back-to-back. Waiting times between lectures also need to be reduced, and all teachers must also fulfill their workload requirements. What GRASP does is take these data, and then attempt to match the “hard” and “soft” criteria as best as possible.