Título: Metaheuristic Approaches for Solving the School Timetabling Problem
Autores: Thiago Eduardo dos Santos, Heber Fernandes Amaral & Antonio Rafael Santana
Resumo: This paper investigates the application of meta-heuristic techniques to solve the School Timetabling Problem (STP), a classic NP-hard combinatorial optimization challenge. Specifically, it addresses the scheduling needs of a Brazilian federal institution (IF Sudeste MG), whose timetable structure does not fully conform to standard STP formulations, thus requiring customized constraint modeling and algorithmic adjustments. The proposed approach integrates a Randomized Constructive Heuristic with local search-based metaheuristics: Iterated Local Search (ILS), Variable Neighborhood Search (VNS), and Iterated Tabu Search (ITS). The problem formulation considers both hard and soft constraints, which are incorporated into a penalized cost function. Experiments conducted on real-world instances from four academic terms show that all proposed metaheuristics generate feasible solutions. Among them, ITS achieved the best average performance, while ILS demonstrated superior efficiency in limited time scenarios. The results confirm the effectiveness of metaheuristic strategies in generating high-quality solutions for realistic and institution-specific timetabling problems.
Palavras-chave: Metaheuristics; Combinatorial Optimization; ILS; VNS; ITS; Timetabling.
Páginas: 7
Código DOI: 10.21528/CBIC2025-1191637
Artigo em PDF: CBIC_2025_paper1191637.pdf
Arquivo BibTeX:
CBIC_2025_1191637.bib