Comparative Benchmarking of Constraint Satisfaction Heuristics and Genetic Algorithms for Multi-Criteria Timetable Optimization

Academic timetabling represents an NP-hard combinatorial search problem characterized by a highly constrained decision space. Satisfying strict hard constraints such as room capacity limitations, instructor overlap, and temporal conflicts—while simultaneously optimizing soft preference metrics—presents significant algorithmic challenges. This paper provides an empirical comparative benchmark evaluating systematic Constraint Satisfaction Problem (CSP) algorithms against local search and stochastic optimization paradigms. We benchmark systematic search strategies including Backtracking (BT), Forward Checking (FC), and Maintaining Arc Consistency (MAC), coupled with variable and value ordering heuristics: Minimum Remaining Values (MRV), Degree Heuristic, and Least Constraining Value (LCV). Furthermore, we analyze Local Search (Min-Conflicts) alongside a population-based Genetic Algorithm (GA) framework that aggregates hard-constraint satisfaction with soft student-preference criteria into a single weighted objective. Evaluating problem scales up to 50 courses, 40 rooms, and 50 time slots, as well as constraint tightness variations from 0.1 to 0.9, our results demonstrate that combining MRV and Degree heuristics reduces search backtracks to zero across medium-scale problem instances while decreasing constraint checks by 97%. Additionally, local search yields sub-0.1 second convergence times for solvable tight configurations, whereas genetic pipelines ensure stable solution quality across complex schedules under a weighted multi-criteria objective.