DEVELOPING A COURSE TIMETABLE SYSTEM FOR ACADEMIC DEPARTMENTS USING GENETIC ALGORITHM

(Received: 2016-06-13, Revised: 2016-11-10 , Accepted: 2017-01-15)

Authors Mohammad A. Al-Jarrah, Ahmad A. Al-Sawalqah, Sami F. Al-Hamdan,

Keywords #Courses timetable problem #Courses timetable generation #Genetic algorithm #Chromosome generation #Parents selection algorithm #Crossover #Mutation

Abstract Preparing course timetables for universities is a search problem with many constraints. Exhaustive search techniques in theory can be used to develop course timetables for academic departments, but unfortunately these techniques are computation intensive, since the search space is very large and therefore are impractical. In this paper, Genetic Algorithms (GA’s) are utilized to build an automated course timetable system. The system is designed for any academic department. The proposed timetabling system requires minimal effort from the administration staff to prepare the course timetable. Moreover, the prepared course timetable considers faculties’ desires, students' needs and available resources, such as classrooms and laboratories with optimal utilization. The proposed timetabling process was divided into three stages. The first stage is the data collection stage. In this stage, the administrative staff; usually the head of the department, is responsible for preparing the required data, such as the names of the faculty personnel and their desires of courses and laboratories ordered with some priority scheme. Number and type of theoretical and practical courses are also fed to the system based on some statistics about student numbers and previous course timetable history. The system is also fed with number of lecture rooms allocated for the department and number of labs with information about theoretical courses they are able to serve. In the second stage, the program generates an initial set of suggested schedules (chromosomes). Each chromosome represents a solution to the problem, but usually is not satisfactory. Finally, the proposed timetabling system starts the search for a good solution that satisfies best interests of the department according to a cost function. GA is applied in search for a satisfactory course timetable based on a pre-defined criterion. The system has been developed and tested utilizing benchmarked datasets developed by an international timetabling competition (ITC2007) and for the Computer Engineering Department at Yarmouk University. In both cases, the algorithm showed very satisfactory results.

References

[1] J. Nakasuwan, P. Srithip and S. O. Komolavanij, "Class Timetabling Optimization," Thammasat International Journal of Science and Technology, vol. 4, no. 2, pp. 88-98, 1999.

[2] P. Chang, S. Chen and K. Lin, "Two-Phase Sub-Population Genetic Algorithm for Parallel Machine-timetabling Problem," Expert Systems with Applications, vol. 29, no. 3, pp. 705-712, 2005.

[3] H. Babaei, J. Karimpour and A. Hadidi, "A Survey of Approaches for University Course Timetabling Problem," Journal of Computers & Industrial Engineering, vol. 86, pp. 43-59, 2015.

[4] P. Guo, J. Chen and L. Zhu, "The Design and Implementation of Timetable System Based on GA’s," IEEE International Conference on Mechatronics Science, Electric Engineering and Computer (MEC), pp. 1497-1500, 2011.

[5] A. George, T. Marwala and F. Nelwamondo, "Use of Data Mining in Scheduler Optimization," arXiv preprint arXiv:1011.1735, 2010.

[6] K. Deb, "Multi-objective Genetic Algorithms: Problem Difficulties and Construction of Test Problems," Evolutionary Computation, vol. 7, no. 3, pp. 205-230, 1999.

[7] C. Teoh, A. Wibowo and M. Ngadiman, "Review of State of the Art for Metaheuristic Techniques in Academic Timetabling Problems," Artificial Intelligence Review, vol. 44, no. 1, pp. 1-21, 2015.

[8] S. Mir Hassani and F. Habibi, "Solution Approaches to the Course Timetabling Problem," Artificial Intelligence Review, vol. 39, no. 2, pp. 133-149, 2015.

[9] M. El-Sherbiny, R. Zeineldin and A. El-Dhshan, "Genetic Algorithm for Solving Course Timetable Problems," International Journal of Computer Applications, vol. 124, no. 10, 2015.

[10]N. Sabar, M. Ayob, G. Kendall and R. Qu, "A Honey-bee Mating Optimization Algorithm for Educational Timetabling Problems," European Journal of Operational Research, vol. 216, no. 3, pp. 533-554, 2012.

[11] J. Obit, D. Ouelhadj, D. Landa-Silva and R. Alfred, "An Evolutionary Non-Linear Great Deluge Approach for Solving Course Timetabling Problems," IJCSI International Journal of Computer Science Issues, vol. 9, no. 4, pp. 1-13, 2012.

[12] V. Sapru, K. Reddy and B. Sivaselvan, "Timetabling Using Genetic Algorithms Employing Guided Mutation," IEEE International Conference on Computational Intelligence and Computing Research (ICCIC), pp. 1-4, 2010.

[13] A. Page and J. Naughton, "Dynamic Task Timetabling Using Genetic Algorithms for Heterogeneous Distributed Computing," Proceedings of 19th IEEE International Symposium in Parallel and Distributed Processing, pp. 189a-189a, April 2005.

[14] S. Wu, H. Yu, S. Jin, K. Lin and G. Schiavone, "An Incremental Genetic Algorithm Approach to Multiprocessor Timetabling," IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 9, pp. 824-834, 2004.

[15] E. Vallada and R. Ruiz, "A Genetic Algorithm for the Unrelated Parallel Machine Timetabling Problem with Sequence-Dependent Setup Times," European Journal of Operational Research, vol. 3, pp. 612-622, 2011.

[16] T. Dereli and H. Filiz, "Allocating Optimal Index Positions on Tool Magazines Using Genetic Algorithms," Robotics and Autonomous Systems, vol. 33, no. 2, pp. 155-167, 2000.

[17] J. Chen, D. Goldberg, S. Ho and K. Sastry, "Fitness Inheritance in Multi-Objective Optimization," Proceedings of the Genetic and Evolutionary Computation Conference, pp. 319-326, 2002.

[18] F. Pezzella, G. Morganti and G. Ciaschetti, "A Genetic Algorithm for the Flexible Job-shop Timetabling Problem," Computers & Operations Research, vol. 35, no. 10, pp. 3202-3212, 2008.

[19] M. Carvalho, A. Laender, M. Gonçalves and A. Da Silva, "A Genetic Programming Approach to Record Deduplication," IEEE Transactions on Knowledge and Data Engineering, vol. 24, no. 3, pp. 399-412, 2012.

[20] G. Kim and C. Lee, "Genetic Reinforcement Learning Approach to the Machine Timetabling Problem," Proceedings of IEEE International Conference on Robotics and Automation, vol. 1, pp. 196-201, 1995.

[21] M. Ghaith and A. Masri, "Scatter Search for Solving the Course Timetabling Problem," 3rd IEEE Conference on Data Mining and Optimization (DMO), Selangor, Malaysia, 28-29 June 2011.

[22] A. Wren, "Scheduling, Timetabling and Rostering – A Special Relationship?," International Conference on the Practice and Theory of Automated Timetabling, pp. 46-75, 1996.

[23] A. Bettinelli, V. Cacchiani, R. Roberti and P. Toth, "An Overview of Curriculum-based Course Timetabling," TOP, vol. 23, no. 2, pp. 313-349, 2015.

[24] V. Cacchiani, A. Caprara, R. Roberti and P. Toth, "A New Lower Bound for Curriculum-based Course Timetabling," Computers & Operations Research, vol. 40, no. 10, pp. 2466-2477, 2013.

[25] E. Özcan, A. Parkes and A. Alkan, "The Interleaved Constructive Memetic Algorithm and Its Application to Timetabling," Computers & Operations Research, vol. 39, no. 10, pp. 2310-2322, 2012.

[26] H. Rudová, T. Müller and K. Murray, "Complex University Course Timetabling," Journal of Scheduling, vol. 14, no. 2, pp. 187-207, 2011.

[27] S. Jat and S. Yang, "A Hybrid Genetic Algorithm and Tabu Search Approach for Post Enrolment Course Timetabling," Journal of Scheduling, vol. 14, no. 6, pp. 617-637, 2011.

[28] Z. Lü and J. Hao, "Solving the Course Timetabling Problem with a Hybrid Heuristic Algorithm," International Conference on Artificial Intelligence: Methodology, Systems and Applications, pp. 262-273, 2008.

[29] A. Bonutti, F. De Cesco, L. Di Gaspero and A. Schaerf, "Benchmarking Curriculum-based Course Timetabling: Formulations, Data Formats, Instances, Validation, Visualization and Results," Annals of Operations Research, vol. 194, no. 1, pp. 59-70, 2012.

[30] T. Muller, ITC2007: Solver Description, Technical Report, Purdue University, 2008.

Abstract: Preparing course timetables for universities is a search problem with many constraints. Exhaustive search techniques in theory can be used to develop course timetables for academic departments, but unfortunately these techniques are computation intensive, since the search space is very large and therefore are impractical. In this paper, Genetic Algorithms (GA’s) are utilized to build an automated course timetable system. The system is designed for any academic department. The proposed timetabling system requires minimal effort from the administration staff to prepare the course timetable. Moreover, the prepared course timetable considers faculties’ desires, students' needs and available resources, such as classrooms and laboratories with optimal utilization. The proposed timetabling process was divided into three stages. The first stage is the data collection stage. In this stage, the administrative staff; usually the head of the department, is responsible for preparing the required data, such as the names of the faculty personnel and their desires of courses and laboratories ordered with some priority scheme. Number and type of theoretical and practical courses are also fed to the system based on some statistics about student numbers and previous course timetable history. The system is also fed with number of lecture rooms allocated for the department and number of labs with information about theoretical courses they are able to serve. In the second stage, the program generates an initial set of suggested schedules (chromosomes). Each chromosome represents a solution to the problem, but usually is not satisfactory. Finally, the proposed timetabling system starts the search for a good solution that satisfies best interests of the department according to a cost function. GA is applied in search for a satisfactory course timetable based on a pre-defined criterion. The system has been developed and tested utilizing benchmarked datasets developed by an international timetabling competition (ITC2007) and for the Computer Engineering Department at Yarmouk University. In both cases, the algorithm showed very satisfactory results.
URL: https://jjcit.org/paper/22

,abstract={Preparing course timetables for universities is a search problem with many constraints. Exhaustive search techniques in theory can be used to develop course timetables for academic departments, but unfortunately these techniques are computation intensive, since the search space is very large and therefore are impractical. In this paper, Genetic Algorithms (GA’s) are utilized to build an automated course timetable system. The system is designed for any academic department. The proposed timetabling system requires minimal effort from the administration staff to prepare the course timetable. Moreover, the prepared course timetable considers faculties’ desires, students' needs and available resources, such as classrooms and laboratories with optimal utilization. The proposed timetabling process was divided into three stages. The first stage is the data collection stage. In this stage, the administrative staff; usually the head of the department, is responsible for preparing the required data, such as the names of the faculty personnel and their desires of courses and laboratories ordered with some priority scheme. Number and type of theoretical and practical courses are also fed to the system based on some statistics about student numbers and previous course timetable history. The system is also fed with number of lecture rooms allocated for the department and number of labs with information about theoretical courses they are able to serve. In the second stage, the program generates an initial set of suggested schedules (chromosomes). Each chromosome represents a solution to the problem, but usually is not satisfactory. Finally, the proposed timetabling system starts the search for a good solution that satisfies best interests of the department according to a cost function. GA is applied in search for a satisfactory course timetable based on a pre-defined criterion. The system has been developed and tested utilizing benchmarked datasets developed by an international timetabling competition (ITC2007) and for the Computer Engineering Department at Yarmouk University. In both cases, the algorithm showed very satisfactory results.},
keywords={Courses timetable problem,Courses timetable generation,Genetic algorithm,Chromosome generation,Parents selection algorithm,Crossover,Mutation},
ISSN={2413-9351},
month={April}}

AB - Preparing course timetables for universities is a search problem with many constraints. Exhaustive search techniques in theory can be used to develop course timetables for academic departments, but unfortunately these techniques are computation intensive, since the search space is very large and therefore are impractical. In this paper, Genetic Algorithms (GA’s) are utilized to build an automated course timetable system. The system is designed for any academic department. The proposed timetabling system requires minimal effort from the administration staff to prepare the course timetable. Moreover, the prepared course timetable considers faculties’ desires, students' needs and available resources, such as classrooms and laboratories with optimal utilization. The proposed timetabling process was divided into three stages. The first stage is the data collection stage. In this stage, the administrative staff; usually the head of the department, is responsible for preparing the required data, such as the names of the faculty personnel and their desires of courses and laboratories ordered with some priority scheme. Number and type of theoretical and practical courses are also fed to the system based on some statistics about student numbers and previous course timetable history. The system is also fed with number of lecture rooms allocated for the department and number of labs with information about theoretical courses they are able to serve. In the second stage, the program generates an initial set of suggested schedules (chromosomes). Each chromosome represents a solution to the problem, but usually is not satisfactory. Finally, the proposed timetabling system starts the search for a good solution that satisfies best interests of the department according to a cost function. GA is applied in search for a satisfactory course timetable based on a pre-defined criterion. The system has been developed and tested utilizing benchmarked datasets developed by an international timetabling competition (ITC2007) and for the Computer Engineering Department at Yarmouk University. In both cases, the algorithm showed very satisfactory results.

Download Full Text