A local search algorithm based on chromatic classes for university course timetabling problem

This paper presents a study for a local search algorithm based on chromatic classes for the university course timetabling problem. Several models and approaches to resolving the problem are discussed. The main idea of the approach is through a heuristic algorithm to specify the chromatic classes of a graph in which the events of the timetable correspond to the graph vertices and the set of the edges represents the possible conflicts between events. Then the chromatic classes should be sorted according to specific sort criteria (a total weight or a total count of events in each class), and finally the local search algorithm starts. The aim of the experiments is to determine the best criterion to sort chromatic classes. The results showed that the algorithm generates better solutions when the chromatic classes are sorted in a total weight criterion.