The week's pick
Reseach Article
Genetic Algorithm for Solving Course Timetable Problems
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 124 - Number 10 |
| Year of Publication: 2015 |
| Authors: Mahmoud M. El-Sherbiny, Ramadan A. Zeineldin, Abdallah M. El-Dhshan |
10.5120/ijca2015905408
|
Mahmoud M. El-Sherbiny, Ramadan A. Zeineldin, Abdallah M. El-Dhshan . Genetic Algorithm for Solving Course Timetable Problems. International Journal of Computer Applications. 124, 10 ( August 2015), 1-7. DOI=10.5120/ijca2015905408
Abstract
Course Timetable Problem (CTTP) is considered as a multiassignments problem. This problem occurs during the assignment of a set of events (courses, subjects and teachers) to specific number of appointments (timeslots, days and rooms) under a set of hard and soft constraints. In this paper, the proposed algorithm is represented for solving the CTTP based on the combination of Genetic Algorithms (GA) and Hill Climbing Optimization (HCO). The proposed algorithm is tested over two stages. The first stage is used to discover the fittest mutation out of 16 mutation functions. So, the Relative Percentage Deviation (RPD) is described as a comparison method to discover the best mutation function for solving the CTTP. The second stage is considered to measure the effectiveness and efficiency of the proposed algorithm over 5 datasets namely hddt benchmark. The results show that the proposed algorithm is able to generate good and optimal solutions when compared against other approaches from literature.
References
- D Abramson and H Dang. School timetables: A case study in simulated annealing. In Applied simulated annealing, pages 103–124. Springer, 1993.
- Ammar M. Ammar, Adel S. Elmaghraby, Mervat H. Gheith, and Hesham A. Hassan. Multi-agent system for solving scheduling problem. Master’s thesis, Department of Computer Science and Information, Institute of Statistical Studies and Research, Cairo University, 2005.
- Rakesh P Badoni and DK Gupta. A hybrid algorithm for university course timetabling problem. Innovative Systems Design and Engineering, 6(2):60–66, 2015.
- Asaju Laaro Bolaji, Ahamad Tajudin Khader, Mohammed Azmi Al-Betar, and Mohammed A Awadallah.University course timetabling using hybridized artificial bee colony with hill climbing optimizer. Journal of Computational Science, 5(5):809–818, 2014.
- Marco P Carrasco and Margarida Vaz Pato. A comparison of discrete and continuous neural network approaches to solve the class/teacher timetabling problem. European Journal of Operational Research, 153(1):65–79, 2004.
- Ruey-Maw Chen and Hsiao-Fang Shih. Solving university course timetabling problems using constriction particle swarm optimization with local search. Algorithms, 6(2):227– 244, 2013.
- MDoulaty, MR Feizi Derakhshi, andMAbdi. Timetabling: A state-of-the-art evolutionary approach. International Journal of Machine Learning and Computing, 3(3):255–258, 2013.
- Mahmoud M El-Sherbiny and Yasser M Ibrahim. An artificial immune algorithm with alternative mutation methods: applied to the student project assignment problem. In International conference on innovation and information management (ICIIM2012), Chengdu, China, volume 36, pages 149–158, 2012.
- Mahmoud Moustafa El-Sherbiny. Alternate mutation based artificial immune algorithm for step fixed charge transportation problem. Egyptian Informatics Journal, 13(2):123–134, 2012.
- Cheng Weng Fong, Hishammuddin Asmuni, Barry McCollum, Paul McMullan, and Sigeru Omatu. A new hybrid imperialist swarm-based optimization algorithm for university timetabling problems. Information Sciences, 283:1–21, 2014.
- Michel Gendreau and Jean-Yves Potvin. Metaheuristics in combinatorial optimization. Annals of Operations Research, 140(1):189–213, 2005.
- Zhipeng L¨u and Jin-Kao Hao. Adaptive tabu search for course timetabling. European Journal of Operational Research, 200(1):235–244, 2010.
- Alade O Modupe, Omidiora E Olusayo, and Olabiyisi S Olatunde. Development of a university lecture timetable using modified genetic algorithms approach. International Journal, 4(9):163–168, 2014.
- Antony E Phillips, Hamish Waterer, Matthias Ehrgott, and David M Ryan. Integer programming methods for large-scale practical classroom assignment problems. Computers & Operations Research, 53:42–53, 2015.
- Michael Pimmer and G¨unther R Raidl. A timeslot-filling heuristic approach to construct high-school timetables. In Advances in Metaheuristics, pages 143–157. Springer, 2013.
- Rushil Raghavjee and Nelishia Pillay. A comparison of genetic algorithms and genetic programming in solving the school timetabling problem. In Nature and Biologically Inspired Computing (NaBIC), 2012 Fourth World Congress on, pages 98–103. IEEE, 2012.
- Marcus Randall and David Abramson. A general metaheuristic based solver for combinatorial optimisation problems. Computational optimization and applications, 20(2):185–210, 2001.
- Khalid Shaker and Salwani Abdullah. Incorporating great deluge approach with kempe chain neighbourhood structure for curriculum-based course timetabling problems. In Data Mining and Optimization, 2009. DMO’09. 2nd Conference on, pages 149–153. IEEE, 2009.
- Kate A Smith, David Abramson, and David Duke. Hopfield neural networks for timetabling: formulations, methods, and comparative results. Computers & industrial engineering, 44(2):283–305, 2003.
- Defu Zhang, Yongkai Liu, Rym MHallah, and Stephen CH Leung. A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems. European Journal of Operational Research, 203(3):550–558, 2010.
Index Terms
Keywords