Title: A GRASP strategy for a more constrained School Timetabling Problem

Authors: Arnaldo Vieira Moura, Rafael Augusto Scaraficci

Addresses: Institute of Computing, University of Campinas, PO Box 6176, 13083 852 Campinas, SP, Brazil. ' Institute of Computing, University of Campinas, PO Box 6176, 13083 852 Campinas, SP, Brazil

Abstract: 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.

Keywords: combinatorial optimisation; Greedy Randomized Adaptive Search Procedure; GRASP; local search; metaheuristics; path-relinking; school timetabling problem; STP; scheduling; Brazil.

DOI: 10.1504/IJOR.2010.030801

International Journal of Operational Research, 2010 Vol.7 No.2, pp.152 - 170

Published online: 06 Jan 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article