Teoria dos grafos: uma abordagem para a programação de horários de exames finais em cursos universitários

Abstract

The increasing demand for higher education and professional qualification results in an increase in the number of courses and educational institutions to fulfill that demand, a fact that highlights an increasingly frequent problem in the educational environment, the Timetabling Problem. The process of preparing timetables for classes and exams is done every semester by most educational institutions and, when carried out manually, demand the commitment of many professionals who dedicate a long period of their functional activities for this. In this way, with the intention of contributing to the improvement of the elaboration of exam schedules in educational institutions, this work has the central objective to develop a solution model for the Examination Timetabling Problem that meets a set of constraints, making it possible a feasible final examination schedule for the true facts in the area concerned. For this purpose, real data were considered referring to the curricular components offered to the students of the Mathematics - Licenciatura course of the Federal University of Pampa, Campus Bagé. The approach proposed for this study, to solve the Examination Timetabling Problem, is based on the Graph Theory from the Graph Colouring developed through the adapted Welsh-Powell algorithm. These adaptations were made in order to serve specific restrictions set for this exam schedule. The algorithm developed in Fortran language for the construction of the adjacency matrix, necessary for the modeling of the problem as a graph, considerably optimized the process of obtaining the schedule of final exams. The results obtained in this research showed that Graph Colouring, set on Graph Theory, and performed using the adapted Welsh-Powell algorithm, allowed the elaboration of a viable final examination schedule for the Mathematics - Licenciatura course, considering all restrictions established.