Solving the problem of school timetabling

Educational administrators everywhere will attest to just how difficult it is to solve the perennial problem of school timetabling: How to ensure adequate teaching resources and teachers are available in the appropriate classrooms with the appropriate students. Indeed, mathematicians have proved the school timetabling problem to be "NP-hard," which means it is the kind of problem that ranks alongside the classic logistics problem known as the traveling salesman problem and the crystal packing problems (akin to the game Tetris). As there seems to be no shortcut or easy solution to NP-hard problems, finding a single, simple answer, even with a supercomputer, is probably impossible when the input instances are realistically large. Hence the educators' perennial headache.

Now, Arnaldo Vieira Moura and Rafael Augusto Scaraficci of the Institute of Computing, at the University of Campinas, in Brazil, have developed a GRASP (i.e., Greedy Randomized Adaptive Search Procedure) heuristic for the school timetabling problem. This approach, like any other heuristic method, is not guaranteed to find a best answer for each school timetable, but it does help solve the problem for Brazilian high school timetables efficiently and quickly, given their specific requirements.

Educational timetabling problems involve scheduling a number of "meetings" among different resources without them overlapping, so that a suitable teacher is available for a particular subject class at a given time. Until now, solving the school timetabling problem was done manually, or at best with the help of a spreadsheet program. Typically, a manual solution requires expert attention and can take many weeks for large educational establishments. Moreover, because of the problem complexity, planners are not always able to take the best decisions, building schedules that are inconsistent with teaching requirements and do not satisfy all teachers' needs.

"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," the researchers explain. The timetabling problem is defined in terms of a set of "m" disjoint classes of students, "n" teachers, "s" subjects and "p" weekly time periods. The latter are prefixed for each class. The tool must then find a slot for each teacher and ensure that all students receive the requisite lectures each week while simultaneously satisfying a complex set of constraints, like with teachers' preferences and availability, adequate daily balancing of class subjects and collective sport classes. Besides, time grids for different grades might also conflict.

Problems arise because teachers often teach several subjects to students in different classes, students must generally not receive more than 2 or 3 same subject lectures in the same day and they must be back to back, teachers must fulfill their workload requirements and waiting times between lectures must be minimized for both teacher and student. These and other criteria are assigned a degree of importance and the team applies their algorithm, embedded in computer software, by allowing it to pick a given lecture and seeing how well it fits with the "hard" criteria and endeavors to fit it to the "soft" criteria.

GRASP repeats a basic three-step cycle. First, it selects a random lecture and assigns it resources, then adds the next lecture and ranks the options and so on. The growing list of assigned lectures is sorted with those that score the highest in terms of the different criteria moving up the priority list, this is the "greedy" part. The addition of each subsequent lecture must then adapt to fit unless it scores more highly than the others in which case it moves up the list. The second phase improve the list using a "local search procedure" that compares neighboring lectures and re-ranks them in pairs. This phase continues until no further improvements are possible. Finally,a so-called "path-relinking strategy" is used to spot the almost optimum solutions, which are then used to guide the final solution. "The basic cycle is repeated a number of times and the overall champion solution is returned as the final answer of the algorithm," explains Moura.

The team successfully tested their GRASP algorithm on the timetabling problem at three Brazilian high schools. The same algorithm should be adaptable to other educational establishments and other timetabling problems.