Exam timetabling for the School of Computer Engineering using Artificial Intelligence techniques

Abstract

The aim of this research project is to analyze the real problem that the University of Oviedo Computer Engineering School has with the generation of exam schedules and whether or not a solution can be found. The actual way to solve the problem is studied and an analysis of the state of the art is carried out in order to see how similar problems are solved in the literature. As the core of the project, the problem is formalized and a solution is proposed by means of Genetic Algorithms and Greedy Algorithms. A Greedy Algorithm is proposed to find good local solutions, and it is complemented with a Genetic Algorithm which is in charge of leading the search towards better areas of the search space. A prototype application is developed to test the acceptability of the proposed solution. To do so, a set of experiments are carried out considering simulated real scenarios. An additional tool is implemented to generate similar problem instances to the real ones provided by the school. Such instances are used both to tune the algorithm parameters as well as to showcase its effectiveness. In the end, the results show that the proposed algorithm is efficient at solving the problem, and it simplifies considerably the complexity of the actual process.