EXPLORING EVOLUTIONARY ALGORITHMS INCORPORATING TEACHER - STUDENT PREFERENCES FOR UNIVERSITY COURSE SCHEDULING

Abstract

Timetable scheduling problem deals with arranging a set of events (classes, exams, courses) into a defined number of timeslots making sure that the conflicts are avoided. In our work, we have proposed a new course scheduling based on mining for students’ preferences for Open Elective courses that makes use of optimization algorithms for automated timetable generation and optimization. The Open Elective courses currently running in an actual university system is used for the experiments. Hard and soft constraints are designed based on the timing and classroom constraints and minimization of clashes between teacher schedules. Two different optimization techniques of Genetic Algorithm (GA) and Simulated Annealing (SA) are utilized for our purpose. The generated timetables are analyzed with respect to the timing efficiency and cost function optimization. The results highlight the efficacy of our approach and the generated course schedules are found at par with the manually compiled timetable running in the university. We have also proposed a novel set of soft constraints for university course timetabling that in addition to conventional constraints incorporate teacher’s preferences and (iv) VI

student time management as well. Here, the hard constraints are those that need to be mandatorily satisfied. The soft constraints are the penalties that are sought to be minimized through every iteration of the optimization algorithm. The evolutionary algorithms- Genetic Algorithm, Particle Swarm Optimization, and the heuristic Simulated Annealing algorithm are used for the optimization task. The timetables generated based on actual university data are found to be more humanely optimized than the previous work of the authors due to the incorporation of human factor consideration both from the perspective of teachers and students. Finally, we have proposed a new memetic algorithm that hybridizes the global search strategies of Genetic Algorithm (GA) with the local search heuristics of Simulated Annealing (SA) and a greedy randomized local search mutation in GA. The basic framework of our memetic algorithm is that of GA. The population of chromosomes in every generation of GA is first refined by a local neighbourhood search for each chromosome as defined by the SA procedure, prior to the selection, crossover and mutation steps of GA. The mutation step in GA is randomized, with a greedy stochastic local search mutation being randomly selected over normal swap mutation of the fittest chromosome in each iteration of GA. The convergence of the fitness function and the stopping criterion are as determined by SA. As proved from the experimental results, this hybridization presents highly optimal solutions with fast convergence. Comparison to the state-of-the-art on a benchmark dataset for university course scheduling proves the efficacy of our approach.