An Evolutionary Algorithm for Solving Academic Courses Timetable Scheduling Problem
Main Article Content
Abstract
Scheduling Timetables for courses in the big departments in the universities is a very hard problem and is often be solved by many previous works although results are partially optimal. This work implements the principle of an evolutionary algorithm by using genetic theories to solve the timetabling problem to get a random and full optimal timetable with the ability to generate a multi-solution timetable for each stage in the collage. The major idea is to generate course timetables automatically while discovering the area of constraints to get an optimal and flexible schedule with no redundancy through the change of a viable course timetable. The main contribution in this work is indicated by increasing the flexibility of generating optimal timetable schedules with different copies by increasing the probability of giving the best schedule for each stage in the campus with the ability to replace the timetable when needed. The Evolutionary Algorithm (EA) utilized in this paper is the Genetic Algorithm (GA) which is a common multi-solution metaheuristic search based on the evolutionary population that can be applied to solve complex combinatorial problems like timetabling problems. In this work, all inputs: courses, teachers, and time acted by one array to achieve local search and combined this acting of the timetable by using the heuristic crossover to ensure that the essential conditions are not broken. The result of this work is a flexible scheduling system, which shows the diversity of all possible timetables that can be created depending on user conditions and needs.
Received 2/6/2020
Accepted 14/2/2020
Published Online First 20/9/2021
Article Details
This work is licensed under a Creative Commons Attribution 4.0 International License.
How to Cite
References
Marczyk A. Genetic algorithms and evolutionary computation. The Talk Origins Archive: http://www. talkorigins/faqs/genalg/genalg. html. 2004 Apr.
Coello CA. An updated survey of GA-based multiobjective optimization techniques. ACM Computing Surveys (CSUR). 2000 Jun 1;32(2):109-43.
Bhattacharjya RK. Introduction to genetic algorithms. IIT Guwahati. 2012 Oct 19;12.
Hammood MM. Application of data mining algorithm with genetic algorithm. TJPS. 2008;13(3):9-16.
Affenzeller M, Wagner S, Winkler S, Beham A. Genetic algorithms and genetic programming: modern concepts and practical applications. Crc Press; 2009 Apr 9.
Willemen RJ. School timetable construction--Algorithms and complexity;(2002).
Sigl B, Golub M, Mornar V. Solving timetable scheduling problem using genetic algorithms. InProceedings of the 25th International Conference on Information Technology Interfaces, 2003. ITI 2003. 2003 Jun 19 (pp. 519-524). IEEE.
Bäck T, Fogel DB, Michalewicz Z, editors. Evolutionary computation 1: Basic algorithms and operators. CRC press; 2018 Oct 3.
Burke EK, Kendall G. Search methodologies. Springer Science+ Business Media, Incorporated; 2005.
Reeves C, Rowe JE. Genetic algorithms: principles and perspectives: a guide to GA theory. Springer Science & Business Media; 2002 Dec 31.
Koza JR, Keane MA, Streeter MJ, Mydlowec W, Yu J, Lanza G. Genetic programming IV: Routine human-competitive machine intelligence. Springer Science & Business Media; 2006 Mar 4.
Chambers LD, editor. Practical handbook of genetic algorithms: complex coding systems. CRC press; 2019 Jul 17.
Ansari A, Bojewar S. Genetic Algorithm to Generate the Automatic Time-Table–An Over View. IJRITCC. 2014;2(11):3480-3.
Timilsina S, Negi R, Khurana Y, Seth J. Genetically Evolved Solution to Timetable Scheduling Problem. Int J Comput Appl. 2015 Jan 1;114(18).
Abdelhalim EA, El Khayat GA. A utilization-based genetic algorithm for solving the university timetabling problem (uga). AEJ. 2016 Jun 1;55(2):1395-409..
Soyemi J, Akinode J, Oloruntoba S. Electronic Lecture Time-Table Scheduler Using Genetic Algorithm. In2017 IEEE 15th Intl Conf on Dependable, Autonomic and Secure Computing, 15th Intl Conf on Pervasive Intelligence and Computing, 3rd Intl Conf on Big Data Intelligence and Computing and Cyber Science and Technology Congress (DASC/PiCom/DataCom/CyberSciTech) 2017 Nov 6 (pp. 710-715). IEEE.
Syahputra MF, Apriani R, Abdullah D, Albra W, Heikal M, Abdurrahman A, et al Genetic algorithm to solve the problems of lectures and practicums scheduling. InIOP Conference Series: Materials Science and Engineering 2018 Feb (Vol. 308, No. 1, p. 012046). IOP Publishing..
Ahmad IR, Sufahani S, Ali M, Razali SN. A Heuristics Approach for Classroom Scheduling Using Genetic Algorithm Technique. In Journal of Physics (IOP Science): Conference Series 2018 Apr (Vol. 995, No. 1, p. 012050). IOP Publishing..
Deeba K, Kuntal B, Samriddho R. Solving Timetable Scheduling Problems Using Genetic Algorithm. International IJRTE. February 2019; 7(5C):168-170.
Mandal AK, Kahar MN, Kendall G. Addressing Examination Timetabling Problem Using a Partial Exams Approach in Constructive and Improvement. Computation. 2020 Jun;8(2):46.
Abayomi-Alli O, Abayomi-Alli A, Misra S, Damasevicius R, Maskeliunas R. Automatic examination timetable scheduling using particle swarm optimization and local search algorithm. In Data, Engineering and Applications 2019 (pp. 119-130). Springer, Singapore.
Tilahun SL. Prey-predator algorithm for discrete problems: a case for examination timetabling problem. Turk J Elec Eng Comp Sci. 2019 Mar 1;27(2):950-60.
Lei Y, Gong M, Jiao L, Shi J, Zhou Y. An adaptive coevolutionary memetic algorithm for examination timetabling problems. IJBIC. 2017;10(4):248-57.
Leite N, Fernandes CM, Melicio F, Rosa AC. A cellular memetic algorithm for the examination timetabling problem. COR. 2018 Jun 1;94:118-38.
Pillay N, Özcan E. Automated generation of constructive ordering heuristics for educational timetabling. Ann. Oper. Res. 2019 Apr 1;275(1):181-208.