Heuristic and genetic algorithm approaches to the real-world university examination timetabling problem

Article Sidebar

PDF
Published Apr 12, 2017
DOI https://doi.org/10.18844/gjbem.v7i1.1409

Main Article Content

İlker Küçükoğlu
Uludag University, Faculty of Engineering, Industrial Engineering Department, Bursa, 16059, Turkey * ADDRESS FOR CORRESPONDENCE: İlker Küçükoğlu, Uludag University, Faculty of Engineering, Industrial Engineering Department, Bursa, 16059, Turkey E-mail address: [email protected] / Tel.: +90-224-294-2091
Alkın Yurtkuran
Uludag University, Faculty of Engineering, Industrial Engineering Department, Bursa, 16059, Turkey

Abstract

Timetabling is one of the computationally difficult problems in scheduling and aims to find best time slots for a number of tasks which require limited resources. In this paper, we examine different solution approaches for the real-world examination timetabling problem (ETP) for university courses. The problem has unique hard and soft constraints, when compared to previous efforts, i.e. consecutive exams, sharing of rooms, room preferences, room capacity and number of empty slots. The aim of the problem is to achieve a timetable, which minimizes the total number of the examination slots without any conflicts. First, the real-world problem is formally defined and a mixed integer linear model is presented. Then, a constructive heuristic and a genetic algorithm based meta-heuristic are proposed in order to solve the ETP. Proposed approaches are tested on a problem set formed by using a real-life data. Results reveal that, proposed approaches are able to produce superior solutions in a limited time.

 

Keywords: Timetabling, constructive heuristic, genetic algorithm;

Downloads

Download data is not yet available.

Article Details

Issue
Vol 7 No 1 (2017): March
Section
Articles
Authors who publish with this journal agree to the following terms:

  1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).

References

Aldeeb, B. A., Norwawi, N. M., Al-Betar, M. A., & Jali, M. Z. B. (2014). Solving university examination timetabling problem using intelligent water drops algorithm. Swarm, Evolutionary, and Memetic Computing: Springer.
Arbaoui, T., Boufflet, J.-P., & Moukrim, A. (2015). Preprocessing and an improved MIP model for examination timetabling. Annals of Operations Research, 229(1), 19-40.
Burke, E. K., & Newall, J. P. (2002). Enhancing timetable solutions with local search methods. Practice and Theory of Automated Timetabling IV: Springer.
Burke, E. K., & Petrovic, S. (2002). Recent research directions in automated timetabling. European Journal of Operational Research, 140(2), 266-280.
Carter, M. W., Laporte, G., & Lee, S. Y. (1996). Examination timetabling: Algorithmic strategies and applications. Journal of the Operational Research Society, 47, 373-383.
Eley, M. (2006). Ant algorithms for the exam timetabling problem. Practice and Theory of Automated Timetabling VI: Springer.
Ersoy, E., Özcan, E., & Uyar, Ş. (2007). Memetic algorithms and hyperhill-climbers. Proceeding of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications, 28-31 August 2007, Paris, France.
Gogos, C., Alefragis, P., & Housos, E. (2012). An improved multi-staged algorithmic process for the solution of the examination timetabling problem. Annals of Operations Research, 194(1), 203-221.
Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Boston, USA: Addion-Wesley.
Holland, J. H. (1992). Genetic algorithms. Scientific American, 267(1), 66-72.
Kahar, M. N. M., & Kendall, G. (2010). The examination timetabling problem at Universiti Malaysia Pahang: Comparison of a constructive heuristic with an existing software solution. European Journal of Operational Research, 207(2), 557-565.
Kalayci, C. B., & Güngör, A. (2012). A genetic algorithm based examination timetabling model focusing on student success for the case of the college of engineering at Pamukkale University, Turkey. Gazi University Journal of Science, 25(1), 137-153.
McCollum, B., McMullan, P., Parkes, A. J., Burke, E. K., & Qu, R. (2012). A new model for automated examination timetabling. Annals of Operations Research, 194(1), 291-315.
Pillay, N., & Banzhaf, W. (2010). An informed genetic algorithm for the examination timetabling problem. Applied Soft Computing, 10(2), 457-467.
Qu, R., Burke, E. K., McCollum, B., Merlot, L. T. G., & Lee, S. Y. (2009). A survey of search methodologies and automated system development for examination timetabling. Journal of scheduling, 12(1), 55-89.
Sabar, N. R., Ayob, M., Kendall, G., & Qu, R. (2009). Roulette wheel graph colouring for solving examination timetabling problems. Combinatorial Optimization and Applications: Springer.
Sabar, N. R., Ayob, M., Kendall, G., & Qu, R. (2012). A honey-bee mating optimization algorithm for educational timetabling problems. European Journal of Operational Research, 216(3), 533-543.