Abstract
This paper examines the use of genetic algorithms (GAs) to solve the school timetabling problem. The school timetabling problem falls into the category of NP-hard problems. Instances of this problem vary drastically from school to school and country to country. Previous work in this area has used genetic algorithms to solve a particular school timetabling problem and has not evaluated the performance of a GA on different problems. Furthermore, GAs have not previously been applied to solving the South African primary or high school timetabling problem. The paper presents a two-phased genetic algorithm approach to solving the school timetabling problem and provides an analysis of the effect of different low-level construction heuristics, selection methods and genetic operators on the success of the GA approach in solving these problems with respect to feasibility and timetable quality. The GA approach is tested on a benchmark set of “hard” school timetabling problems, the Greek high school timetabling problem and a South African primary and high school timetabling problem. The performance of the GA approach was found to be comparable to other methods applied to the same problems. This study has also revealed that different combinations of low-level construction heuristics, selection methods and genetic operators are needed to produce feasible timetables of good quality for the different school timetabling problems. Future work will investigate methods for the automatic configuration of GA architectures of both phases.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Pillay, N., Banzhaf, W.: An Informed Genetic Algorithm for the Uncapacitated Examination Timetabling Problem. Applied Soft Computing 10, 45–67 (2010)
Larranaga, P., Kuijpers, C.M.H., Murga, R.H., Inza, I., Dizdarevic, S.: Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators. Artificial Intelligence Review 11(2), 129–170 (1999)
Ponce-Perez, A., Perez-Garcia, A., Ayala-Ramirez, V.: Bin-Packing Using Genetic Algorithms. In: Proceedings of CONIELECOMP 2005: 15th International Conference on Electronics, Communications and Computers, pp. 311–314. IEEE Press (2005)
Pillay, N.: A Survey of School Timetabling. Annals of Operations Research (February 2013), doi:10.1007/s10479-013-1321-8
Goldberg, D., Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co. (1989).
Beasley, D., Bull, D.R., Martin, R.R.: An Overview of Genetic Algorithms: Part 1 and Part 2, Research Topics. University Computing 15(4), 170–181 (1993)
Abramson, D., Abela, J.: A Parallel Genetic Algorithm for the Solving the School Timetabling Problem. In: Proceedings of the Fifteenth Australian Conference: Division of Information Technology, C.S.I.R.O. pp. 1–11 (1991)
Bedoya, C.F., Santos, M.: A Non-Standard Genetic Algorithm Approach to Solve Constrained School Timetabling Problems. Eurocast, 26–37 (2003)
Calderia, J.P., Ross, A.C.: School Timetabling Using Genetic Search. In: The Proceedings of the International Conference on the Practice and Theory of Automated Timetabling (PATAT 1997) pp. 115-122 (1997)
Colorni, A., Dorigo, M., Maniezzo, V.: Metaheuristics for High School Timetabling. In: Computational Optimization and Applications, vol. 9, pp. 275–298. Kluwer Academic Publishers (1998)
Filho, G.R., Lorena, L.A.N.: A Constructive Evolutionary Approach to School Timetabling. In: Boers, E.J.W., Gottlieb, J., Lanzi, P.L., Smith, R.E., Cagnoni, S., Hart, E., Raidl, G.R., Tijink, H. (eds.) EvoWorkshop 2001. LNCS, vol. 2037, pp. 130–139. Springer, Heidelberg (2001)
Wilke, P., Gröbner, M., Oster, N.: A Hybrid Genetic Algorithm for School Timetabling. In: McKay, B., Slaney, J.K. (eds.) AI 2002. LNCS (LNAI), vol. 2557, pp. 455–464. Springer, Heidelberg (2002)
Yigit, T.: Constraint-Based School Timetabling Using Hybrid Genetic Algorithms. In: Basili, R., Pazienza, M.T. (eds.) AI*IA 2007. LNCS (LNAI), vol. 4733, pp. 848–855. Springer, Heidelberg (2007)
Beligiannis, G.N., Moschopoulos, C.N., Likothanassis, S.D.: A Genetic Algorithm Approach to School Timetabling. Journal of the Operational Research Society 60(1), 23–42 (2009)
Srndic, N., Dervisevic, M., Pandzo, E., Konjicija, S.: The Application of a Parallel Genetic Algorithm to Timetabling of Elementary School Classes: A Coarse Grained Approach. In: Proceedings of ICAT 2009 -2009 22nd International Symposium on Information, Communication and Automation Technologies, pp. 1–5. IEEE (2009)
Nurmi, K., Kyngas, J.: A Framework for School Timetabling Problem. In: Proceedings of the 3rd Multidisciplinary International Scheduling Conference: Theory and Application (2007)
Zuters, J.: Neural Networks to Enrich Fitness Function in a GA-Based School Timetabling Model. Proceedings of WSEAS Transactions on Information Science and Application 4(2), 346–353 (2007)
Cedeira-Pena, A., Carpente, L., Farina, A., Seco, D.: New Approaches for the School Timetabling Problem. In: Proceedings of the 7th Mexican Conference on Artificial Intelligence (MICAI 2008), pp. 261–267 (2008)
Beasley, J.F.: OR Library, http://people.brunel.ac.uk/mastjjb/jeb/orlib/tableinfo.html (accessed May 25, 2011)
Valouxis, C., Housos, E.: Constraint Programming Approach for School Timetabling. Computers and Operations Research 30, 1555–1572 (2003)
Beligiannis, G.N., Moschopoulos, C.N., Kaperonis, G.P., Likothanassis, S.D.: Applying Evolutionary Computation to the School Timetabling Problem: The Greek Case. Computers and Operations Research 35, 1265–1280 (2008)
Abramson, D., Dang, H.: School Timetable: A Case Study in Simulated Annealing. In: Applied Simulated Annealing Lecture Notes in Economics and Mathematical Systems, ch. 5, pp. 103–124 (1993)
Randall, M.: A General Meta-Heuristic Based Solver for Combinatorial Optimization Problems. Computational Optimization and Applications 20(2), 185–210 (2000)
Smith, K.A., Abramson, D., Duke, D.: Hopfield Neural Networks for Timetabling: Formulations, Methods, and Comparative Results. Computers and Industrial Engineering 44, 285–305 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Raghavjee, R., Pillay, N. (2013). A Study of Genetic Algorithms to Solve the School Timetabling Problem. In: Castro, F., Gelbukh, A., González, M. (eds) Advances in Soft Computing and Its Applications. MICAI 2013. Lecture Notes in Computer Science(), vol 8266. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45111-9_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-45111-9_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45110-2
Online ISBN: 978-3-642-45111-9
eBook Packages: Computer ScienceComputer Science (R0)