Multi-Neighbourhood Particle Collision Algorithm for solving course timetabling problems

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 accept...

Full description

Saved in:
Bibliographic Details
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
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2155-6938
2155-6946
DOI:10.1109/DMO.2009.5341917