A Dual-Phase Hybrid Method for Curriculum-Based Academic Scheduling Utilizing Backtracking and Genetic Algorithms

Abstract

The generation of academic timetables represents a complex combinatorial optimization challenge that entails the allocation of lectures, practical sessions, instructors, and resources while adhering to various institutional constraints. In programs based on curricula, practical sessions introduce further complications due to laboratory capacity restrictions, necessitating the division of students into batches that must be coordinated within the same academic year. Traditional single-stage methods utilizing Genetic Algorithms often encounter heightened search space and computational complexity when attempting to manage both lecture and practical scheduling concurrently. To mitigate this challenge, this paper introduces a hybrid two-phase timetable generation framework that integrates deterministic backtracking with Genetic Algorithms. In the initial phase, practical sessions are organized using a backtracking algorithm to meet constraints related to laboratory capacity, faculty availability, and batch synchronization. After achieving a viable practical timetable, an occupancy matrix is created, and the remaining lecture sessions are optimized through a Genetic Algorithm that takes into account both hard and soft constraints. This proposed method simplifies the search process by distinguishing between highly constrained and less constrained scheduling elements. Experimental assessments conducted on a curriculum-based dataset comprising three academic years, 12 faculty members, 16 lecture subjects, and 12 practical subjects reveal that the proposed framework produces conflict-free timetables with efficient execution times. For a problem size of 85 events, a complete timetable was generated in under 4 seconds. The findings suggest that the proposed methodology offers a scalable and computationally efficient solution for medium-sized academic departments and serves as a practical alternative to traditional single-stage timetable generation techniques.