A Novel Method for Solving the University Course Timetabling Problem Based on the Grey Wolf Optimizer Algorithm

Combinatorial optimization problems are ultimately NP-Hard problems. Save for some limited versions of these problems, treatable by exact methods, solving them requires turning to approximate methods capable of providing efficient approximate resolution for this class of problems within reasonable time. In this article, our aim is to create a new bio-inspired optimization method based on the Gray Wolf Optimizer and the graph colouring algorithm to solve the timetabling problem; or more specifically the University Course Timetabling Problem. Solving the timetabling problem consists of constructing a timetable that fulfils two types of constraints: hard and soft. The hard constraints must be fully satisfied in order for a solution to be valid; whereas soft constraints are more tolerable and the aim is usually to maximize their satisfaction. GWO is a metaheuristic based on the social behaviour of grey wolves in nature. It is a population-based method which means it requires a set of fully valid solutions at the very beginning of the optimization process. The graph colouring algorithm employed in this article allows us to randomly generate an initial set of low-quality solutions that satisfy all the hard constraints. This set will be the initial population on which the second phase of the heuristic will be applied in order to maximize the satisfaction of the soft constraints. For a case study, we have taken real data from our Information Technology Department of 20 August 1955 Skikda University. The obtained results reveal a satisfaction rate of 97-98% for a group of “very spoiled” teachers and students; otherwise, it would show a complete satisfaction.