A Modified Event Grouping Based Algorithm for The University Course Timetabling Problem

This paper presents a study of a modified event grouping based algorithm (MEGB) for university course timetabling problem (UCTP). Multiple models to describe the problem and multiple approaches to solving it are pointed out. The main idea of the modification is that through reduction on the generated solutions the execution time of the standard event grouping based algorithm (EGB) will be reduced, too. Also, an implementation of the modified algorithm based on the described approach is presented. The methodology, conditions and the aims of the experiment are described. The experimental results are analyzed and conclusions are made. When increasing the number of the groups, the execution time of the MEGB algorithm increases and equates with the execution time of the EGB algorithm. The best results are obtained with the first 30% of the groups formed. In these groupings, the execution time of the MEGB algorithm is much less than the execution time of the EGB algorithm. This is because, in the EGB algorithm, every change in the event ordinance creates a new timetable, and all events are repositioned on it. This process is optimized by creating a partial timetable, whereby the ordinance of events in groups before the current does not change. In addition, a comparative analysis between the MEGB algorithm and two other algorithms for UCTP, respectively a genetic algorithm with the local search method (GALS) and a local search algorithm based on chromatic classes (CCLS) is made as well. The obtained results show that the MEGB algorithm and the CCLS algorithm generate better solutions for smaller input data sets, while the GALS algorithm generates better solutions for larger input data sets. However, in terms of the execution time, it was ascertained that the GALS algorithm runs slowest among the others.