Abstract
There are different types of educational timetabling problems which are computationally difficult to solve. In this study, we deal with the High School Timetabling Problem which requires assignment of events, such as courses, and resources, such as classrooms, to time-slots under a set of different types of constraints. We describe an approach that hybridises an Evolutionary Algorithm variant and Simulated Annealing methods to solve this problem. This approach is tested over a set of real world instances obtained across different countries. The empirical results demonstrate the viability of the hybrid approach when compared to the previously proposed techniques.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abramson, D.A., Dang, H., Krisnamoorthy, M.: Simulated annealing cooling schedules for the school timetabling problem. Asia-Pacific Journal of Operational Research 16(1), 1–22 (1999)
Al-Betar, M.A., Khader, A.T.: A harmony search algorithm for university course timetabling. Annals of Operations Research 194(1), 3–31 (2012)
Alia, O.M., Mandava, R.: The variants of the harmony search algorithm: an overview. Artificial Intelligence Review 36(1), 49–68 (2011)
Awadallah, M.A., Khader, A.T., Al-Betar, M.A., Bolaji, A.: Nurse rostering using modified harmony search algorithm. In: Panigrahi, B.K., Suganthan, P.N., Das, S., Satapathy, S.C. (eds.) SEMCCO 2011, Part II. LNCS, vol. 7077, pp. 27–37. Springer, Heidelberg (2011)
Birbas, T., Daskalaki, S., Housos, E.: School timetabling for quality student and teacher schedules. Journal of Scheduling 12(2), 177–197 (2009)
Domrös, J., Homberger, J.: An evolutionary algorithm for high school timetabling. In: Proceedings of the Ninth International Conference on the Practice and Theory of Automated Timetabling (PATAT 2012), pp. 485–488 (2012)
Even, S., Itai, A., Shamir, A.: On the Complexity of Timetable and Multicommodity Flow Problems. SIAM Journal on Computing 5(4), 691–703 (1976)
Fonseca, G.H.G., Brito, S.S., Santos, H.G.: A simulated annealing based approach to the high school timetabling problem. In: Yin, H., Costa, J.A.F., Barreto, G. (eds.) IDEAL 2012. LNCS, vol. 7435, pp. 540–549. Springer, Heidelberg (2012)
Geem, Z.W., Kim, J.H., Loganathan, G.V.: A new heuristic optimization algorithm: Harmony search. Simulation 76(2), 60–68 (2001)
Hoang, D.C., Yadav, P., Kumar, R., Panda, S.: A robust harmony search algorithm based clustering protocol for wireless sensor networks. In: 2010 IEEE International Conference on Communications Workshops (ICC), pp. 1–5 (2010)
Kheiri, A., Özcan, E., Parkes, A.J.: Hysst: Hyper-heuristic search strategies and timetabling. In: Proceedings of the Ninth International Conference on the Practice and Theory of Automated Timetabling (PATAT 2012), pp. 497–499 (2012)
Kingston, J.H.: A software library for high school timetabling (2009), http://sydney.edu.au/engineering/it/~jeff/khe/
Kingston, J.H.: A tiling algorithm for high school timetabling. In: Burke, E.K., Trick, M.A. (eds.) PATAT 2004. LNCS, vol. 3616, pp. 208–225. Springer, Heidelberg (2005)
Lara, C., Flores, J.J., Calderón, F.: Solving a school timetabling problem using a bee algorithm. In: Gelbukh, A., Morales, E.F. (eds.) MICAI 2008. LNCS (LNAI), vol. 5317, pp. 664–674. Springer, Heidelberg (2008)
Minh, K.N.T.T., Thanh, N.D.T., Trang, K.T., Hue, N.T.T.: Using tabu search for solving a high school timetabling problem. In: Nguyen, N.T., Katarzyniak, R., Chen, S.-M. (eds.) Advances in Intelligent Information and Database Systems. SCI, vol. 283, pp. 305–313. Springer, Heidelberg (2010)
Pillay, N.: A survey of school timetabling research. Annals of Operations Research, 1–33 (2013)
Post, G.: Benchmarking project for high school timetabling (2011), http://www.utwente.nl/ctit/hstt/
Post, G., Ahmadi, S., Daskalaki, S., Kingston, J.H., Kyngas, J., Nurmi, C., Ranson, D.: An xml format for benchmarks in high school timetabling. Annals of Operations Research 194(1), 385–397 (2012)
Post, G., Gaspero, L., Kingston, J.H., McCollum, B., Schaerf, A.: The third international timetabling competition. Annals of Operations Research, 1–7 (2013)
Sørensen, M., Kristiansen, S., Stidsen, T.R.: International timetabling competition 2011: an adaptive large neighborhood search algorithm. In: Proceedings of the Ninth International Conference on the Practice and Theory of Automated Timetabling (PATAT 2012). pp. 489–492 (2012)
Tassopoulos, I.X., Beligiannis, G.N.: A hybrid particle swarm optimization based algorithm for high school timetabling problems. Applied Soft Computing 12(11), 3472–3489 (2012)
Valouxis, C., Housos, E.: Constraint programming approach for school timetabling. Computers and Operations Research 30(10), 1555–1572 (2003)
Weyland, D.: A rigorous analysis of the harmony search algorithm: How the research community can be misled by a “novel” methodology. International Journal of Applied Metaheuristic Computing 1(2), 50–60 (2010)
Wilke, P., Killer, H.: Walk down jump up algorithm a new hybrid algorithm for timetabling problems. In: Proceedings of the 8th International Conference on the Practice and Theory of Automated Timetabling (PATAT 2010), pp. 440–446 (2010)
Yuan, Y., Xu, H., Yang, J.: A hybrid harmony search algorithm for the flexible job shop scheduling problem. Applied Soft Computing 13(7), 3259–3272 (2013)
Zou, D., Gao, L., Li, S., Wu, J., Wang, X.: A novel global harmony search algorithm for task assignment problem. Journal of Systems and Software 83(10), 1678–1688 (2010)
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
Shambour, M.K.Y., Khader, A.T., Kheiri, A., Özcan, E. (2013). A Two Stage Approach for High School Timetabling. In: Lee, M., Hirose, A., Hou, ZG., Kil, R.M. (eds) Neural Information Processing. ICONIP 2013. Lecture Notes in Computer Science, vol 8226. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-42054-2_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-42054-2_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-42053-5
Online ISBN: 978-3-642-42054-2
eBook Packages: Computer ScienceComputer Science (R0)