A hybrid particle swarm optimization for a university course scheduling problem with flexible preferences

摘要

The timetabling problem at universities is an NP-hard problem concerned with instructor assignments and class scheduling under multiple constraints and limited resources. A novel meta-heuristic algorithm that is based on the principles of particle swarm optimization (PSO) is proposed for course scheduling problem. The algorithm includes some features: designing an ‘absolute position value’ representation for the particle; allowing instructors that they are willing to lecture based on flexible preferences, such as their preferred days and time periods, the maximum number of teaching-free time periods and the lecturing format (consecutive time periods or separated into different time periods); and employing a repair process for all infeasible timetables. Furthermore, in the original PSO algorithm, particles search solutions in a continuous solution space. Since the solution space of the course scheduling problem is discrete, a local search mechanism is incorporated into the proposed PSO in order to explore a better solution improvement. The algorithms were tested using the timetabling data from a typical university in Taiwan. The experimental results demonstrate that the proposed hybrid algorithm yields an efficient solution with an optimal satisfaction of course scheduling for instructors and class scheduling arrangements. This hybrid algorithm also outperforms the genetic algorithm proposed in the literature.