A GRASP strategy for a more constrained School Timetabling Problem

This work treats a more constrained School Timetabling Problem (STP). It consists of scheduling a set of lectures and teachers in a prefixed period of time, satisfying a set of operational requirements. We applied a Greedy Randomized Adaptive Search Procedure (GRASP) heuristic, combined with a path-relinking improvement. During execution of the GRASP heuristic, the local search procedure interleaves two types of movements. In addition, the path-relinking strategy was itself enhanced by a local search procedure. The algorithms were tested with real instances and proved to be good approaches to solve this problem. Although some restrictions are specific to Brazilian educational institutions, the same ideas can inspire similar approaches for solving the STP in other situations.