A Genetic Algorithm Based Examination Timetabling Model Focusing on Student Success for the Case of the College of Engineering at Pamukkale University, Turkey

Year 2012, Volume: 25 Issue: 1, 137 - 153, 24.01.2012

Can Kalaycı , Askıner Gungor

Abstract

This study proposes a genetic algorithm (GA) based model to generate examination schedules such that they focus on students’ success in addition to satisfying the hard constraints required for feasibility. The model is based on the idea that the student success is positively related to the adequate preparation and resting time among exams. Therefore, the main objective of this study is to maximize time length among exams (i.e., paper spread) considering the difficulties of exams. Two different genetic algorithm models were developed to optimize paper spread. In the first genetic algorithm model, a high penalty approach was used to eliminate infeasible solutions throughout generations. The second genetic algorithm model controls whether or not each chromosome joining the population satisfies the hard constraints. To evaluate the models, a set of experiments have been designed and studied using the data collected from the College of Engineering in Pamukkale University.

Keywords

Genetic Algorithms, Examination Timetabling, Student Success

References

• Burke, E. K., McCollum, B., Meisels, A., Petrovic, S., & Qu, R. A graph-based hyper-heuristic for educational timetabling problems. European Journal of Operational Research, 176, 177-192 (2007)
• MirHassani, S. A. Improving paper spread in examination timetables using integer programming. Computation, 179, 702-706 (2006)
• Qu, R., Burke, E., McCollum, B., Merlot, L., & Lee, S. A survey of search methodologies and automated system development for examination timetabling. Journal of Scheduling, 12, 55-89 (2009)
• Carter, M. W., Laporte, G., Lee, S.Y. Examination timetabling: Algorithmic strategies and applications. The Journal of the Operational Research Society, 47, 373-383 (1996)
• Burke, E., Petrovic, S., & Qu, R. Case-based heuristic selection for timetabling problems. Journal of Scheduling, 9, 115-132.(2006)
• Abdullah, S., Ahmadi, S., Burke, E., & Dror, M. Investigating Ahuja–Orlin’s large neighbourhood search approach for examination timetabling. OR Spectrum, 29, 351-372 (2007)
• Petrovic, S., Yang, Y., & Dror, M. Case-based selection of initialisation heuristics for metaheuristic examination timetabling. Expert Systems with Applications, 33, 772-785 (2007)
• Asmuni, H., Burke, E. K., Garibaldi, J. M., McCollum, B., & Parkes, A. J. An investigation of fuzzy multiple heuristic orderings in the construction of university examination timetables. Computers & Operations Research, 36, 981-1001
• Pillay, N., & Banzhaf, W. A study of heuristic combinations for hyper-heuristic systems for the uncapacitated examination timetabling problem. European Journal of Operational Research, 197, 482-491 (2009)
• Qu, R., Burke, E. K., & McCollum, B. Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems. European Journal of Operational Research, 198, 392-404 (2009)
• Burke, E. K., Eckersley, A. J., McCollum, B., Petrovic, S., & Qu, R. Hybrid variable neighbourhood approaches to university exam timetabling. European Journal of Operational Research, 206, 46-53 (2010)
• Pillay, N., & Banzhaf, W. An informed genetic algorithm for the examination timetabling problem. Applied Soft Computing, 10, 457-467 (2010)
• Gogos, C., Alefragis, P., & Housos, E. An improved multi-staged algorithmic process for the solution of the examination timetabling problem. Annals of Operations Research (2010)
• Foulds, L. R., & Johnson, D. G. SlotManager: a microcomputer-based decision support system for university timetabling. Decision Support Systems, 27, 367-381 (2000)
• Dimopoulou, M., & Miliotis, P. Implementation of a university course and examination timetabling system. European Journal of Operational Research, 130, 202-213 (2001)
• Dimopoulou, M., & Miliotis, P. An automated university course timetabling system developed in a distributed environment: A case study. European Journal of Operational Research, 153, 136-147 (2004)
• Burke, E. K., & Petrovic, S. Recent research directions in automated timetabling. European Journal of Operational Research, 140, 266-280 (2002)
• Burke, E. K., & Newall, J. P. Solving Examination Timetabling Problems through Adaption of Heuristic Orderings. Annals of Operations Research, 129, 107-134 (2004)
• Daskalaki, S., Birbas, T., & Housos, E. An integer programming formulation for a case study in university timetabling. European Journal of Operational Research, 153, 117-135 (2004)
• Daskalaki, S., & Birbas, T. Efficient solutions for a university timetabling problem through integer programming. European Journal of Operational Research, 160, 106-120 (2005)
• Avella, P., & Vasil'Ev, I. A Computational Study of a Cutting Plane Algorithm for University Course Timetabling. Journal of Scheduling, 8, 497-514 (2005)
• MirHassani, S. A. A computational approach to enhancing course timetabling with integer programming. Computation, 175, 814-822 (2006)
• Al-Yakoob, S. M., & Sherali, H. D. A mixed- integer programming approach to a class timetabling problem: A case study with gender policies and traffic considerations. European Journal of Operational Research, 180, 1028-1044 (2007)
• Head, C., & Shaban, S. A heuristic approach to simultaneous course/student timetabling. Computers & Operations Research, 34, 919-933 (2007)
• Van den Broek, J., Hurkens, C., & Woeginger, G. Timetabling problems at the TU Eindhoven. European Journal of Operational Research, 196, 877-885 (2009)
• Birbas, T., Daskalaki, S., & Housos, E. School timetabling for quality student and teacher schedules. Journal of Scheduling, 12, 177-197 (2009)
• Kahar, M. N. M., & Kendall, G. The examination timetabling problem at Universiti Malaysia Pahang: Comparison of a constructive heuristic with an existing software solution. European Journal of Operational Research, In Press, Accepted Manuscript (2010)
• Sarin, S., Wang, Y., & Varadarajan, A. A university-timetabling problem and its solution using Benders’ partitioning—a case study. Journal of Scheduling, 13, 131-141 (2010)
• Rudová, H., Müller, T., & Murray, K. Complex university course timetabling. Journal of Scheduling (2010)
• Wang, S., Bussieck, M., Guignard, M., Meeraus, A., & O’Brien, F. Term-end exam scheduling at United States Military Academy/West Point. Journal of Scheduling, 13, 375-391 (2010)
• Smith, K. A., Abramson, D., & Duke, D. Hopfield neural networks for timetabling: formulations, methods, and comparative results. Computers & Industrial Engineering, 44, 283-305 (2003)
• Dave Corne, P. R., Hsiao-lan Fang. Evolutionary timetabling: Practice, prospects and work in progress. In P. Prosser (Ed.), Proceedings of the UK Planning and Scheduling SIG Workshop
• Naji Azimi, Z. Hybrid heuristics for Examination Timetabling problem. Applied Mathematics and Computation, 163, 705-733 (2005)
• Ross, P., Hart, E., & Corne, D. Some Observations about GA-Based Exam Timetabling. Lecture Notes in Computer Science, Vol. 1408 (pp. 115) (1998)
• Erben, W. A Grouping Genetic Algorithm for Graph Colouring and Exam Timetabling. Lecture Notes in Computer Science, Vol. 2079 (pp. 132- 156) (2001)
• Wong, T., Cote, P., & Gely, P. Final exam timetabling: a practical approach. In Electrical and Computer Engineering, 2002. IEEE CCECE 2002. Canadian Conference on (Vol. 2, pp. 726- 731 vol.722) (2002)
• Sheibani, K. An Evolutionary Approach For The Examination Timetabling Problems. D. C. E. K. Burke (Ed.), Proceedings of the 4th international conference on practice and theory of automated timetabling (Vol. 2740/2003, pp. 387–396). Gent, Belgium: Springer Berlin / Heidelberg (2002)
• Wong, T., Cote, P., & Sabourin, R. A hybrid MOEA for the capacitated exam proximity problem. In Evolutionary Computation, 2004. CEC2004. Congress on (Vol. 2, pp. 1495-1501 Vol.1492) (2004)
• Côté, P., Wong, T., & Sabourin, R. A Hybrid Multi-objective Evolutionary Algorithm for the Uncapacitated Exam Proximity Problem. Lecture Notes in Computer Science, Volume 3616 (pp. 294-312) (2005)
• Santiago-Mozos, R., Salcedo-Sanz, S., DePrado- Cumplido, M., & Bousoño-Calzón, C. A two- phase heuristic evolutionary algorithm for personalizing course timetables: a case study in a Spanish university. Computers & Operations Research, 32, 1761-1776 (2005)
• Chiarandini, M., Birattari, M., Socha, K., & Rossi- Doria, O. An effective hybrid algorithm for university course timetabling. Journal of Scheduling, 9, 403-432 (2006)
• Ülker, Ö., Özcan, E., & Korkmaz, E. Linear Linkage Encoding in Grouping Problems: Applications on Graph Coloring and Timetabling. PATAT'06 Proceedings of the 6th international conference on Practice and theory of automated timetabling VI Springer-Verlag Berlin, Heidelberg, (2007)
• Beligiannis, G. N., Moschopoulos, C. N., Kaperonis, G. P., & Likothanassis, S. D. Applying evolutionary computation to the school timetabling problem: The Greek case. Computers & Operations Research, 35, 1265-1280 (2008)
• Pongcharoen, P., Promtet, W., Yenradee, P., & Hicks, C. Stochastic Optimisation Timetabling Tool for university course scheduling. International Journal of Production Economics, 112, 903-918 (2008)
• Mumford, C. A multiobjective framework for heavily constrained examination timetabling problems. Annals of Operations Research (2008)
• Cheong, C., Tan, K., & Veeravalli, B. A multi- objective evolutionary algorithm for examination timetabling. Journal of Scheduling, 12, 121-146 (2009)
• De Causmaecker, P., Demeester, P., & Vanden Berghe, G. A decomposed metaheuristic approach for a real-world university timetabling problem. European Journal of Operational Research, 195, 307-318 (2009)
• Goldberg, D. E. Genetic Algorithms in Search, Optimisation and Machine Learning. Boston: Addison-Wesley Longman Publishing Co., Inc.(1989)
• Michalewicz, Z. Genetic algorithms + data structures = evolution programs (3rd ed.): Springer-Verlag (1996)
• Puente, J., Gómez, A., Fernández, I., & Priore, P. Medical doctor rostering problem in a hospital emergency department by means of genetic algorithms. Computers & Industrial Engineering, 56, 1232-1242 (2009)
• Terashima-Marin, H., Ross, P., & Valenzuela- Rendon, M. Clique-based crossover for solving the timetabling problem with GAs. In Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on (Vol. 2, pp. 1206 Vol. 1202) (1999)