Validação de Instâncias de Coloração de Vértices Aplicado à Alocação de Disciplinas

Abstract

This work presents the development of a validator for graph coloring instances that model the timetabling problem at FACOM, focused exclusively on the allocation of timeslots for classes, not on defining which professors teach each course. The instance is a translation of another approach already implemented at the institution that solves the problem with linear programming. Typical constraints of the process include scheduling conflicts between courses of the same program and semester or taught by the same professor.

Since this is an NP-hard problem, the implemented algorithm checks the consistency of a timetabling instance, seeking to identify a valid configuration that assists the automation already in place. Tests carried out with real instances showed that the approach is promising, albeit still incomplete. The validator proved competent in two of the three semesters analyzed, but faced difficulties with a more complex academic term.