Multi-Neighbourhood Particle Collision Algorithm for solving course timetabling problems

• Main Authors: Abuhamdah, A., Ayob, M.
• Format: Conference Proceeding
• Language: English
• Subjects: Benchmark testing; Cooling; Course Timetabling Problem; Data mining; Genetic algorithms; Iterative algorithms; Meta-Heuristics; Particle Collision Algorithm; Particle collisions; Particle scattering; Principal component analysis; Simulated annealing; System testing
• ISSN: 2155-6938; 2155-6946
• DOI: 10.1109/DMO.2009.5341917

This work presents a particle collision algorithm (PCA) to solve university course timetabling problems. The aim is to produce an effective algorithm for assigning a set of courses, lecturers and students to a specific number of rooms and timeslots, subject to a set of constraints. PCA always accepts improved solution but adaptively accepts worse solutions based on the quality of the solution. PCA differs from simulated annealing and other meta-heuristic approaches in that is does not have cooling schedule and does not rely on user-defined parameters. The multi-neighbourhood collision algorithm (MPCA) enhances a PCA approach that was originally introduced by Sacco for policy optimization. The structure of PCA resembles the simulated annealing structure. It differs from basic PCA in terms of improvement phase (exploration phase). PCA perform local search in both construction solution phase and scattering phase, while MPCA perform local search (hill climbing based search) in the scattering phase only, which makes MPCA more capable than PCA of escaping from local optima. Also MPCA differs in terms of applying multi-neighbourhood structures. MPCA employ different neighbourhood in two stages (construction solution stage and improvement stage). We evaluate the effectiveness of MPCA on standard benchmark course timetabling datasets which were introduced by Socha. Results show that MPCA significantly outperformed other approaches in some instances and that MPCA is able to produce good quality solutions within a reasonable time.