Análise e aprimoramento do modelo matemático para o problema de alocação de salas no contexto dos cursos de tecnologia da UFC — campus Crateús

Abstract

The Classroom Assignment Problem (CAP) consists of constructing a timetable that consistently assigns classes, professors, time slots, and rooms while satisfying a set of institutional and operational constraints. Due to its combinatorial nature, the CAP can be addressed through mathematical optimization models. In this context, this work aims to analyze the mathematical model proposed by Sousa (2019) for the CAP in the scope of the Federal University of Ceará — Crateús Campus, as well as to propose improvements that ensure greater structural consistency and practical feasibility of the obtained solutions. A detailed analysis of the original model revealed an inconsistency that allows a single class to be simultaneously assigned to the same day and time slot in different rooms, leading to impractical solutions. To address this issue, a new constraint is introduced into the mathematical model, ensuring that, for each (day, time slot) pair, a class is associated with at most one room. Computational experiments were conducted using the SCIP solver through the OR-Tools framework, considering different groups of instances and model configurations. The results demonstrate that the proposed constraint is effective in eliminating the identified inconsistency, thereby enhancing the structural coherence of the model. However, its inclusion increases the strictness of the problem, resulting in higher computational effort. Additionally, a sensitivity analysis was performed with respect to the professors’ preferred teaching days parameter. The results indicate that relaxing this constraint significantly improves the model’s resolvability, enabling the solver to conclude a larger number of instances either by finding optimal solutions or by certifying infeasibility. Overall, the study highlights the importance of balancing structural consistency and computational performance, and points to future research directions focused on scalability and deeper investigation of problem parameters.