Solving University Course Timetabling Problems Using Constriction Particle Swarm Optimization with Local Search
Open Access
- 18 April 2013
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 6 (2), 227-244
- https://doi.org/10.3390/a6020227
Abstract
Course timetabling is a combinatorial optimization problem and has been confirmed to be an NP-complete problem. Course timetabling problems are different for different universities. The studied university course timetabling problem involves hard constraints such as classroom, class curriculum, and other variables. Concurrently, some soft constraints need also to be considered, including teacher’s preferred time, favorite class time etc. These preferences correspond to satisfaction values obtained via questionnaires. Particle swarm optimization (PSO) is a promising scheme for solving NP-complete problems due to its fast convergence, fewer parameter settings and ability to fit dynamic environmental characteristics. Therefore, PSO was applied towards solving course timetabling problems in this work. To reduce the computational complexity, a timeslot was designated in a particle’s encoding as the scheduling unit. Two types of PSO, the inertia weight version and constriction version, were evaluated. Moreover, an interchange heuristic was utilized to explore the neighboring solution space to improve solution quality. Additionally, schedule conflicts are handled after a solution has been generated. Experimental results demonstrate that the proposed scheme of constriction PSO with interchange heuristic is able to generate satisfactory course timetables that meet the requirements of teachers and classes according to the various applied constraints.Keywords
This publication has 22 references indexed in Scilit:
- A hybrid particle swarm optimization based algorithm for high school timetabling problemsApplied Soft Computing, 2012
- Solving the post enrolment course timetabling problem by ant colony optimizationAnnals of Operations Research, 2012
- A hybrid particle swarm optimization for a university course scheduling problem with flexible preferencesExpert Systems with Applications, 2011
- An improved multi-objective particle swarm optimizer for multi-objective problemsExpert Systems with Applications, 2010
- Local search and constraint programming for the post enrolment-based course timetabling problemAnnals of Operations Research, 2010
- Using novel particle swarm optimization scheme to solve resource-constrained scheduling problem in PSPLIBExpert Systems with Applications, 2010
- The particle swarm - explosion, stability, and convergence in a multidimensional complex spaceIEEE Transactions on Evolutionary Computation, 2002
- Restricted coloring models for timetablingDiscrete Mathematics, 1997
- Large-scale classroom schedulingIIE Transactions, 1996
- Tabu search for large scale timetabling problemsEuropean Journal of Operational Research, 1991