The objective of this project is the implementation of a software tool for the solution of the Timetable Problem (TTP), with applications to medium or large sized teaching institutions. From the point of view of algorithmic complexity the TTP is a NP-hard problem, so, from a practical point of view, heuristic techniques are of fundamental importance to obtain solutions. In recent years the search for heuristics for the TTP as received a great deal of attention from the Operational Research and Artificial Intelligence communities.
In this project we will use genetic search to obtain solutions for the TTP. Our intention is to exploit the robustness of this search method, its flexibility in obtaining new solutions when there is a change in the problem restrictions and the effective balance that it establishes between the search of new solutions and the preservation of the characteristics of those already found.
Beyond the obvious practical applications, this project has a strong basic research component in the Genetic Algorithms area, mainly in the following topics:
– Efficient coding of the search space.
– Advanced genetic operators that preserve the validity of solutions from one generation to another.
– Convergence behaviour of genetic algorithms.