Uma Abordagem Matheurística baseada em Large Neighborhood Search para o Problema da Distribuição de Disciplina

Abstract

The assignment of courses to instructors in higher education institutions is a recurring combinatorial problem, classified as NP-hard due to its relationship with the Generalized Assignment Problem. Its complexity increases with the number of instructors, courses, and operational constraints involved, making exact methods such as those based on Integer Linear Programming (ILP) potentially computationally impractical for larger instances, while purely heuristic approaches provide no quality guarantees. This work proposes, implements, and evaluates a matheuristic based on Large Neighborhood Search with ILP reoptimization, following a fix-and-optimize scheme and integrated as a primal heuristic into the SCIP solver, for the Course Distribution Problem. The problem is modeled as an ILP whose objective function maximizes assignment quality based on instructor preferences and area compatibility, subject to mandatory coverage constraints for all courses and minimum annual and maximum semester teaching loads per instructor.