Um estudo de estruturas de vizinhanças no GRASP aplicado ao problema de tabela-horário para universidades

Abstract

Educational timetabling is one of the most researched among timetabling problems. This problem consists of alocatting a set of lectures in a set of rooms for a time period considering some constraints. Educational timetabling can be divided in: exam timetabling, school timetabling and university timetabling. In the univertity timetabling, we can find many different formulations in the literature because the needs of each university varies. In this work, the formulation chosen is the one presented at the second international timetabling competition (ITC-2007). To solve this problem we implement a GRASP metaheuristic with the algorithms Steepest Descent, Hill Climbing and Simulated Annealing used as local search and many neighborhoods known in the literature. We provide a comparison of the results obtained with the GRASP algorithm and others results published in the literature. Besides solving this problem, we also present a detailed analysis of the neighborhoods.