Scientific Research and Essays

  • Abbreviation: Sci. Res. Essays
  • Language: English
  • ISSN: 1992-2248
  • DOI: 10.5897/SRE
  • Start Year: 2006
  • Published Articles: 2751

Full Length Research Paper

Performance evaluation of simulated annealing and genetic algorithm in solving examination timetabling problem

Oyeleye, C. Akinwale*, Olabiyisi, S. Olatunde, Omidiora, E. Olusayo and Oladosu, J. Babalola
Department of Computer Science and Engineering, Ladoke Akintola University of Technology, Ogbomoso, Oyo State, Nigeria.
Email: [email protected] or [email protected]

  •  Accepted: 23 April 2012
  •  Published: 09 May 2012

Abstract

 

This work details the performance evaluation of simulated annealing (SA) and genetic algorithm (GA) in terms of their software complexity measurement and simulation time in solving a typical University examination timetabling problem (ETP). Preparation of a timetable consists basically of allocating a number of events to a finite number of time periods (also called slots) in such a way that a certain set of constraints is satisfied. The developed software was used to schedule the first semester examination of Ladoke Akintola University of Technology, Ogbomoso Nigeria during the 2010/2011 session. A task involving 20,100 students, 652 courses, 52 examination venues for 17 days excluding Saturdays and Sundays. The use of the software resulted in significant time saving in the scheduling of the timetable, a shortening of the examination period and a well spread examination for the students. Also, none of the lecturers / examination invigilators was double booked or booked successively. It was clearly evident that simulated annealing performed better than genetic algorithm in most of the evaluated parameters.

 

Key words: Simulated annealing, genetic algorithm, examination timetabling, software complexity and simulation time.