research-article

An application of genetic algorithms to the school timetabling problem

Authors:

Rushil Raghavjee,

Nelishia PillayAuthors Info & Claims

SAICSIT '08: Proceedings of the 2008 annual research conference of the South African Institute of Computer Scientists and Information Technologists on IT research in developing countries: riding the wave of technology

Pages 193 - 199

https://doi.org/10.1145/1456659.1456682

Published: 06 October 2008 Publication History

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]

Beligiannis G. N., Moschopoulos C. N., Kaperonis G. P., and Likothanassis S. D. Applying Evolutionary Computation to the School Timetabling Problem: The Greek Case. Computer and Operations Research, 35. (2008), 1265--1280

Digital Library

[6]

Caldeira J. P., and Rosa A. C. School Timetabling Using Genetic Search. In Practice and Theory of Automated Timetabling, 1997.

[7]

Colorni A., and Dorigo M. Metaheuristics for School Timetabling. Computational Optimization and Applications, 9. 1998, 275--298.

Digital Library

[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]

Filho G. R., and Lorena L. A. N. A Constructive Evolutionary Approach to School Timetabling. Applications of Evolutionary Computing, 2037. (2001), 130--139.

Digital Library

[10]

Holland J. Adaptation in Natural and Artificial Systems. The University of Michigan Press: Ann Arbor, Michigan, 1975.

Digital Library

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

Digital Library

[13]

Luger G. Artificial Intelligence, Structures and Strategies for complex Problem Solving. Fourth Edition, Addison Wesley, 2002

Digital Library

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

Digital Library

[16]

Smith K., Abramson D., and Duke D. Hopfield Neural Networks for Timetabling: Formulations, Methods and Comparative Timetabling. Computers and Industrial Engineering, 4(2). 2003, 283--305.

Digital Library

[17]

Wilke P., Grobner M., Oster N. A Hybrid Genetic Algorithm for School Timetabling. Advances in Artificial Intelligence, Lecture Notes in Computer Science, 2557. 2002, 455--464.

Digital Library

[18]

School Timetabling Solutions Found by the GA, http://saturn.cs.unp.ac.za/~nelishiap/st/solutions.htm

Cited By

Hoshino RFabris I(2020)Optimizing Student Course Preferences in School TimetablingIntegration of Constraint Programming, Artificial Intelligence, and Operations Research10.1007/978-3-030-58942-4_19(283-299)Online publication date: 19-Sep-2020
https://doi.org/10.1007/978-3-030-58942-4_19
Kheiri AKeedwell E(2017)A hidden markov model approach to the problem of heuristic selection in hyper-heuristics with a case study in high school timetabling problemsEvolutionary Computation10.1162/evco_a_0018625:3(473-501)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1162/evco_a_00186
Mockus JPupeikiene L(2016)Investigation of Data Regularization and Optimization of Timetables by Lithuanian High Schools ExampleAdvances in Stochastic and Deterministic Global Optimization10.1007/978-3-319-29975-4_9(167-180)Online publication date: 5-Nov-2016
https://doi.org/10.1007/978-3-319-29975-4_9
Show More Cited By

Index Terms

An application of genetic algorithms to the school timetabling problem
1. Computing methodologies
  1. Artificial intelligence
    1. Philosophical/theoretical foundations of artificial intelligence

Recommendations

The effect of construction heuristics on the performance of a genetic algorithm for the school timetabling problem
SAICSIT '11: Proceedings of the South African Institute of Computer Scientists and Information Technologists Conference on Knowledge, Innovation and Leadership in a Diverse, Multidisciplinary Environment

This paper examines the effect of using construction heuristics on the evolutionary process for the domain of school timetabling. The paper firstly presents a genetic algorithm to solve the school timetabling problem. the paper compares the performance ...
An informed genetic algorithm for the high school timetabling problem
SAICSIT '10: Proceedings of the 2010 Annual Research Conference of the South African Institute of Computer Scientists and Information Technologists

The high school timetabling problem differs drastically from one school to another and from country to country. The South African high school problem has not been researched. This paper presents a genetic algorithm (GA) to solve this problem for a ...
Using particle swarm optimization to solve effectively the school timetabling problem
Special Issue on Fuzzy Ontologies and Fuzzy Markup Language Applications

A new hybrid adaptive algorithm based on particle swarm optimization (PSO) is designed, developed and applied to the high school timetabling problem. The proposed PSO algorithm is used to create feasible and efficient timetables for high schools in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

SAICSIT '08: Proceedings of the 2008 annual research conference of the South African Institute of Computer Scientists and Information Technologists on IT research in developing countries: riding the wave of technology

October 2008

304 pages

ISBN:9781605582863

DOI:10.1145/1456659

Program Chairs:
Reinhardt Botha
Nelson Mandela Metropolitan University, South Africa
,
Charmain Cilliers
Nelson Mandela Metropolitan University, South Africa

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Microsoft: Microsoft

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 October 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SAICSIT '08

Sponsor:

Microsoft

SAICSIT '08: 2008 Annual Conference of the South African Institute of Computer Scientists and Information Technologists

October 6 - 8, 2008

Wilderness, South Africa

Acceptance Rates

Overall Acceptance Rate 187 of 439 submissions, 43%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
819
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hoshino RFabris I(2020)Optimizing Student Course Preferences in School TimetablingIntegration of Constraint Programming, Artificial Intelligence, and Operations Research10.1007/978-3-030-58942-4_19(283-299)Online publication date: 19-Sep-2020
https://doi.org/10.1007/978-3-030-58942-4_19
Kheiri AKeedwell E(2017)A hidden markov model approach to the problem of heuristic selection in hyper-heuristics with a case study in high school timetabling problemsEvolutionary Computation10.1162/evco_a_0018625:3(473-501)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1162/evco_a_00186
Mockus JPupeikiene L(2016)Investigation of Data Regularization and Optimization of Timetables by Lithuanian High Schools ExampleAdvances in Stochastic and Deterministic Global Optimization10.1007/978-3-319-29975-4_9(167-180)Online publication date: 5-Nov-2016
https://doi.org/10.1007/978-3-319-29975-4_9
Kheiri AÖzcan EParkes A(2014)A stochastic local search algorithm with adaptive acceptance for high-school timetablingAnnals of Operations Research10.1007/s10479-014-1660-0239:1(135-151)Online publication date: 22-Jun-2014
https://doi.org/10.1007/s10479-014-1660-0
Nelson JCraddock IImamura K(2013)Academic course scheduling by simulated annealingJournal of Computing Sciences in Colleges10.5555/2527148.252718229:1(150-156)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.5555/2527148.2527182
Özcan EParkes AAlkan A(2012)The Interleaved Constructive Memetic Algorithm and its application to timetablingComputers and Operations Research10.1016/j.cor.2011.11.02039:10(2310-2322)Online publication date: 1-Oct-2012
https://dl.acm.org/doi/10.1016/j.cor.2011.11.020
OuYang YChen Y(2011)Design of automated Course Scheduling system based on hybrid genetic algorithm2011 6th International Conference on Computer Science & Education (ICCSE)10.1109/ICCSE.2011.6028629(256-259)Online publication date: Aug-2011
https://doi.org/10.1109/ICCSE.2011.6028629
Raghavjee RPillay NKotzé Pvan der Merwe AGerber A(2010)An informed genetic algorithm for the high school timetabling problemProceedings of the 2010 Annual Research Conference of the South African Institute of Computer Scientists and Information Technologists10.1145/1899503.1899555(408-412)Online publication date: 11-Oct-2010
https://dl.acm.org/doi/10.1145/1899503.1899555
Pillay NKotzé Pvan der Merwe AGerber A(2010)A study into the use of hyper-heuristics to solve the school timetabling problemProceedings of the 2010 Annual Research Conference of the South African Institute of Computer Scientists and Information Technologists10.1145/1899503.1899532(258-264)Online publication date: 11-Oct-2010
https://dl.acm.org/doi/10.1145/1899503.1899532
Raghavjee RPillay N(2010)Using genetic algorithms to solve the South African school timetabling problem2010 Second World Congress on Nature and Biologically Inspired Computing (NaBIC)10.1109/NABIC.2010.5716348(286-292)Online publication date: Dec-2010
https://doi.org/10.1109/NABIC.2010.5716348
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents