An Enhanced Metaheuristic Framework for Timetable Generation Using Genetic Algorithm and Local Search

الملخص

Genetic Algorithm (GA), a class of evolutionary algorithms inspired by natural
selection, has been widely applied to complex optimization and search problems. The
University Course Timetabling Problem (UCTP) is a non-deterministic polynomial-time hard
problem that involves assigning lectures to classrooms and timeslots while satisfying numerous
hard and soft constraints. This study proposes an enhanced metaheuristic framework that
integrates a GA with sequential local search and a repair function to efficiently generate
feasible timetables. The GA initializes a population of candidate timetables, evaluates their
fitness, and iteratively evolves them through selection, crossover, and mutation operators. The
sequential local search refines candidate solutions by reducing soft constraint violations, such
as consecutive lectures or sessions scheduled during breaks, while the repair function
guarantees the satisfaction of hard constraints, including classroom capacity and instructor
availability. The proposed framework was implemented in Java IDE 8.1 and evaluated using
multiple benchmark datasets of varying sizes and complexities. Experimental results
demonstrate that the proposed method achieved an overall accuracy of 96.3% and improved
constraint violation reduction by 28.5% compared with existing methods. These findings
confirm the effectiveness of combining GA’s global search capability with local refinement
mechanisms, demonstrating its potential for real-world University scheduling scenarios.