A hybrid metaheuristic approach to the university course timetabling problem

Salwani Abdullah, Hamza Turabieh, Barry McCollum, Paul McMullan

Research output: Contribution to journalArticlepeer-review

47 Citations (Scopus)
454 Downloads (Pure)

Abstract

This paper describes the development of a novel metaheuristic that combines an electromagnetic-like mechanism (EM) and the great deluge algorithm (GD) for the University course timetabling problem. This well-known timetabling problem assigns lectures to specific numbers of timeslots and rooms maximizing the overall quality of the timetable while taking various constraints into account. EM is a population-based stochastic global optimization algorithm that is based on the theory of physics, simulating attraction and repulsion of sample points in moving toward optimality. GD is a local search procedure that allows worse solutions to be accepted based on some given upper boundary or ‘level’. In this paper, the dynamic force calculated from the attraction-repulsion mechanism is used as a decreasing rate to update the ‘level’ within the search process. The proposed method has been applied to a range of benchmark university course timetabling test problems from the literature. Moreover, the viability of the method has been tested by comparing its results with other reported results from the literature, demonstrating that the method is able to produce improved solutions to those currently published. We believe this is due to the combination of both approaches and the ability of the resultant algorithm to converge all solutions at every search process.
Original languageEnglish
Pages (from-to)1-23
Number of pages23
JournalJournal of Heuristics
Volume18
Issue number1
DOIs
Publication statusPublished - Feb 2012

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Computer Networks and Communications
  • Information Systems
  • Control and Optimization
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'A hybrid metaheuristic approach to the university course timetabling problem'. Together they form a unique fingerprint.

Cite this