A new hybrid algorithm for university course timetabling problem using events based on groupings of students

• Using events based on groupings of students, a new hybrid algorithm NHA is described.
• NHA produces feasible solution for every problem instance considered.
• NHA leads to optimal solution for all small problem instances within 0.6 s.
• NHA achieves better solution for medium04 and hard02 problem instances when compared with other algorithms.

In this paper, a new hybrid algorithm (NHA) combining genetic algorithm with local search and using events based on groupings of students is described to solve the university course timetabling problem. A list of events such as lectures, tutorials, laboratories and seminars are ordered and mutually disjoint groups of students taking them are formed in such a way that once a student is selected in any group, he is excluded from further selection in other groups. The union of all the events taken by all the students of each group is formed. The number of events in each group is termed as its group size whose upper bound is restricted by the total number of timeslots and can be reduced to the maximum number of events per student. The above process of forming groups is repeated till the size of each group is reduced within this bound by not choosing those events which are common for all the students in the group. Now, the genetic algorithm with local search (GALS) is applied on a number of benchmark problems. The experimental results show that our algorithm, NHA, is able to produce promising results when compared with the results obtained by using GALS and other existing algorithms.