Optimization Approaches Applied to the Timetabling Problem of the Undergraduate Program of the ENCE

The timetabling problem in higher education institutions is widely studied in the literature and is classified as NP-hard, making it difficult to obtain globally optimal solutions within feasible computational time. In many institutions, this process is still carried out without the use of automatic systems based on optimization methods, as is the case in the undergraduate program of the Escola Nacional de Ciências Estatísticas (ENCE). In this study, two approaches are proposed for this problem: a heuristic based on Variable Neighborhood Search (VNS) and an exact backtracking algorithm, considering the main constraints of this program. The results show that both approaches generated globally optimal solutions, satisfying the constraints and contributing efficiently and effectively to the construction of the timetable.