A Utilization-based Genetic Algorithm for Solving the University Timetabling Problem (UGA)

AbstractBuilding university timetables is a complex process that considers varying types of constraints and objectives from one institution to another. The problem solved in this paper is a real one featuring a number of hard and soft constraints that are not very conventional. The pursued objective is also novel and considers maximizing resource utilization. This paper introduces a genetic algorithm that uses some heuristics to generate an initial population of feasible good quality timetables. The algorithm uses a simple weighted sum formula to respect professors’ preferences and handle conflicts. In order to reduce waste, a crossover type focusing on the utilization rates of learning spaces is introduced. A targeted mutation operator that uses a local search heuristic is also employed. The algorithm applies a composite fitness function that considers space utilization, gaps between events and a maximum number of lectures per day. A large dataset with real data from the Faculty of Commerce, Alexandria University in Egypt was used to test the contributed algorithm. The algorithm was also tested against two difficult benchmark problems from the literature. Testing proved that the developed algorithm is an effective tool for managing timetables and resources in universities. It performed remarkedly well on the large datasets of the two benchmark problems and it also respected more constraints than those stated in the initial problem statement of the two benchmark datasets