An application of genetic algorithms to the school timetabling problem

ABSTRACT

There has been a large amount of research into the automatic generation of school timetables. Methodologies such as constraint programming, simulated annealing, Tabu search and genetic algorithms have been applied to the school timetabling problem. However, a majority of these studies focus on solving the problem for a particular school and there is very little research into the comparison of the performance of different techniques in solving the school timetabling problem.

The study presented in this paper evaluates genetic algorithms (GAs) for the purpose of inducing school timetables. For each problem, the GA implemented iteratively refines an initial population of school timetables using mutation to find a good quality feasible timetable. The performance of the GA on a set of five benchmark problems has been compared to the performance of neural networks, simulated annealing, Tabu search, and greedy search on the same set of problems. The results obtained by the GA were found to be comparable to and an improvement on those produced by the other methods.

REFERENCES

• 1: Abramson D., and Abela J. A Parallel Genetic Algorithm for Solving School Timetabling, Technical Report, Division of Information Technology, CSRIO, 1991.
• 2: Abramson D., and Dang H. School Timetables: A Case Study in Simulated Annealing. Lecture Notes in Economics and Mathematic Systems. Berlin: Springer-Verlag, 1993, 103--24.
• 3: Abramson D. Constructing School Timetables using Simulated Annealing: Sequential and Parallel Algorithms, Technical Report, Royal Melbourne Institute of Technology, 1991.
• 4: Beasley J. E. OR-Library, February 2008, http://people.brunel.ac.uk/~mastjjb/jeb/orlib/tableinfo.html
• 5: Grigorios N. Beligiannis , Charalampos N. Moschopoulos , Georgios P. Kaperonis , Spiridon D. Likothanassis, Applying evolutionary computation to the school timetabling problem: The Greek case, Computers and Operations Research, v.35 n.4, p.1265-1280, April, 2008 [doi>10.1016/j.cor.2006.08.010]
• 6: Caldeira J. P., and Rosa A. C. School Timetabling Using Genetic Search. In Practice and Theory of Automated Timetabling, 1997.
• 7: Alberto Colorni , Marco Dorigo , Vittorio Maniezzo, Metaheuristics for High School Timetabling, Computational Optimization and Applications, v.9 n.3, p.275-298, March 1, 1998 [doi>10.1023/A:1018354324992]
• 8: de Haan P., Landman R., and Post G. Four-Phase Approach to a Timetabling Problem in Secondary Schools. In Practice and Theory of Automated Timetabling (PATAT'06). 2006, 423--425.
• 9: Geraldo Ribeiro Filho , Luiz Antonio Nogueira Lorena, A Constructive Evolutionary Approach to School Timetabling, Proceedings of the EvoWorkshops on Applications of Evolutionary Computing, p.130-139, April 18-20, 2001
• 10: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 11: Jacobsen F., Bortfeldt A., and Gehring H. Timetabling at German Secondary Schools: Tabu Search vs. Constraint Programming. Practice and Theory of Automated Timetabling (PATAT'06). 2006, 439--442.
• 12: Kingston J. H. The KTS High School Timetabling System. Practice and Theory of Automated Timetabling (PATAT' 06), Lecture Notes in Computer Science, 3867. 2007, 308--323.
• 13: George F. Luger, Artificial Intelligence: Structures and Strategies for Complex Problem Solving, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 14: Randall M., Abramson D., and Wild C. A Meta-Heuristic Based Solver for Combinatorial Optimization Problems. Technical, Report, TR99-01, School of Information Technology, Bold University, Australia, 1999.
• 15: Schaerf A. Tabu search techniques for large high school timetabling problems. Technical Report, Monash University, 2000.
• 16: Kate A. Smith , David Abramson , David Duke, Hopfield neural networks for timetabling: formulations, methods, and comparative results, Computers and Industrial Engineering, v.44 n.2, p.283-305, February 2003 [doi>10.1016/S0360-8352(02)00180-8]
• 17: Peter Wilke , Matthias Gröbner , Norbert Oster, A Hybrid Genetic Algorithm for School Timetabling, Proceedings of the 15th Australian Joint Conference on Artificial Intelligence: Advances in Artificial Intelligence, p.455-464, December 02-06, 2002
• 18: School Timetabling Solutions Found by the GA, http://saturn.cs.unp.ac.za/~nelishiap/st/solutions.htm

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Keywords:
genetic algorithms, hard constraints, school timetabling problem, timetabling problems