Elite-Refined Genetic Algorithm with Hill Climbing Local Search for University Course Scheduling - Heru Purnomo Kurniawan; Lia Farhatuaini; Nurul Bahiyah; Ardi Susanto; Muhammad Iszul Wilsa; Gina Khayatun Nufus (APIC, 2025)
Abstract— This paper proposes a hybrid optimization approach combining Genetic Algorithm (GA) and Hill Climbing (HC) to address the university course scheduling problem in the Informatics Study Program at Universitas Islam Negeri Siber Syekh Nurjati Cirebon. The hybrid GA-HC model integrates GA’s global exploration capability with HC's local refinement strategy to minimize hard and soft constraint violations while achieving balanced timetables. The dataset includes 56 course classes, 18 lecturers, and three rooms, with scheduling over five working days and 11 time slots per day. Experimental results demonstrate that GA-HC outperforms pure GA and pure HC in convergence speed, average fitness, and stability of feasible solutions. Parameter tuning analysis further shows that moderate mutation rates and limited HC iterations yield optimal trade-offs between runtime and solution quality. The proposed hybrid framework effectively enhances convergence, reduces conflicts, and improves overall timetable quality, confirming its robustness for large-scale academic scheduling problems.