Revisiting local search for Curriculum-Based Course Timetabling

Curriculum-Based Course Timetabling (CB-CTT) is a well-established benchmark problem in educational timetabling, with numerous real and synthetic datasets. Despite its long history of algorithmic developments, designing search methods that work effectively across diverse datasets under time limits remains challenging. In this paper, we focus on local search and, after a thorough analysis of all neighborhood structures reported in the literature, we propose an improved Simulated Annealing (SA) algorithm driven by an extended version of the classic LectureMove neighborhood, called LectureKick, that allows flexible lecture relocation while preserving feasibility. The neighborhood is further enriched with several sampling biases specifically designed to address the soft constraints of CB-CTT, while the overall behavior of the SA is regulated by a cut-off mechanism embedded in the cooling schedule. The method involves numerous parameters, both for the SA schedule and for the neighborhood biases, which are rigorously tuned on a large artificial dataset. The final algorithm is subsequently evaluated on the available benchmarks, including the "standard" ITC 2007 comp dataset, under the original competition timeout conditions. The results show that our approach clearly outperforms all previously proposed local search methods and is competitive with the best methods reported for CB-CTT overall, while improving upon them on several instances.