Optimisation of University Examination Timetable Using Hybridised Genetic and Greedy Algorithms: A Case Study of Computer Science Department, University of Ibadan
Keywords:
Timetable, Examination, Greedy Algorithm, Genetic Algorithm and SchedulingAbstract
Timetable scheduling is an important aspect of decision-making in any organisation, particularly in academia. An examination timetable is expected to coordinate students, invigilators, courses, examination hall allocation, and time slots. However, the problem could be viewed as a Nondeterministic Polynomial (NP); NP-hard problem, scheduling problem has plagued humanity since its inception. Due to the complex structure of the problem in terms of hard and soft-constraints, most organisations schedule time inefficiently using manual approach. This study introduced an algorithms hybridisation method of genetic and greedy algorithms to automate the timetable scheduling process efficiently. A genetic algorithm is a heuristic search technique based on Charles Darwin's theory of natural evolution. The fitness of each course, venue, and faculty content is determined by the probabilistic optimisation which is the solution candidate in the initial population of all the objects. Subsequently, the greedy algorithm's activities selector selects the best solution. The output demonstrates that the method effectively handled all the constraints associated with timetable scheduling. Hybridising the two algorithms to build a scheduling system, such as the examination timetable. Therefore, it is a viable option to combine genetic and greedy algorithms to have an optimised examination timetable that is flexible to any situation.
References
. Alves, S. S., Oliveira, S. A., & Neto, A. R. R. (2015, October). A novel educational timetabling solution through recursive genetic algorithms. In 2015 Latin America Congress on Computational Intelligence (LA-CCI) (pp. 1-6). IEEE.
. Bagga, S., Gupta, S., & Sharma, D. K. (2019). Computer-assisted anthropology. In Internet of Things in Biomedical Engineering (pp. 21-47). Academic Press.
. Burke E., Elliman D., and Weare R., "A University Timetabling System Based on Graph Coloring and Constraint Manipulation," Journal of Research on Computing in Education, vol. 27, no. 1, pp. 1-18, 1994.
. Burke E., Elliman D., and Weare R., "Automated Scheduling of University Exams," Department of Computer Science, University of Nottingham, 1993.
. Burke E.K, Eckersley B.J. McCollum, Petrovic S, and Qiu R., (2004). "Analysing Similarity in Examination Timetabling". 5th International Conference on the Practice and Theory of Automated Timetabling. Pittsburgh, PA USA.
. Burke, E. K., & Newall, J. P. (1999). A multistage evolutionary algorithm for the timetable problem. IEEE transactions on evolutionary computation, 3(1), 63-74.
. Burke, E. K., Newall, J. P., &Weare, R. F. (1996). A memetic algorithm for university exam timetabling. In Practice and Theory of Automated Timetabling: First International Conference Edinburgh, UK, August 29–September 1, 1995 Selected Papers 1 (pp. 241-250). Springer Berlin Heidelberg.
. Ceka?a T., Z. Telec and B. Trawi?ski, "Truck loading schedule optimisation using genetic algorithm for yard management," in ACIIDS 2015: Intelligent Information and Database Systems, Bali, Indonesia, 2015.
. Cooper, T. B., Kingston, J. H. (1995). The Complexity of Timetable Construction Problems.http://www.cs.usyd.edu.au/~jeff/.
. East, A. R. (2019). Timetable Scheduling via Genetic Algorithm. National University of Ireland.
. Foy, M. D., Benekohal, R. F., & Goldberg, D. E. (1992). Signal timing determination using genetic algorithms. Transportation Research Record, (1365), 108.
. Gajski, D. D., Zhu, J., Dömer, R., Gerstlauer, A., & Zhao, S. (2012). SpecC: Specification language and methodology. Springer Science & Business Media.
. Ghasemi, O., Handley, S., & Howarth, S. (2022). Illusory intuitive inferences: Matching heuristics explain logical intuitions. Available at SSRN 4235957.
. Husseini, S., Malkawi, M., & Vairavan, K. (1992). Distributed Algorithms for Edge Coloring of Graphs. In the 5th ISMM International Conference on Parallel and Distributed Computing Systems.
. Jacobson L. and Kanber B.(2015). “Genetic Algorithms in Java Basics: Solve Classical Problems like The Travelling Salesman with GA.” (1st edition) ). [On-line]. pp. 139-151. Available: https://link.springer.com/book/10.1007/978-1-4842-0328-6 [May 31, 2024].
. Lange, R., Schaul, T., Chen, Y., Lu, C., Zahavy, T., Dalibard, V., & Flennerhag, S. (2023, July). “Discovering attention-based genetic algorithms via meta-black-box optimization.” In Proceedings of the Genetic and Evolutionary Computation Conference (pp. 929-937).
. Lukas, S., Aribowo, A., &Muchri, M. (2012). “Solving timetable problem by genetic algorithm and heuristic search case study: universitas pelitaharapan timetable.” Real-World Applications of Genetic Algorithms, 3(78), pp.303-316.
. Malkawi, M., Hassan, M. A. H., & Hassan, O. A. H. (2008). A New Exam Scheduling Algorithm Using Graph Coloring. International Arab Journal of Information Technology (IAJIT), 5(1).
. Margaret Rouse (2023), Information and Communication Technology (ICT), https://www.techopedia.com/definition/24152/information-and-communications-technology-ict Accessed 28 June, 2023.
. Nie S. Z.(2014), "A Java EE platform test system based on improved genetic algorithm," Applied Mechanics and Materials. 556(562), pp. 2581-2585.
. Podgorelec V. and P. Kokol(1997). “Genetic algorithm based system for patient scheduling in highly constrained situations.” Journal of Medical Systems. 21(6), pp. 417–427.
. Thanh, N.D (2007). "Solving Timetabling Problem Using Genetic and Heuristic Algorithms". Eighth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing. 33(10), pp. 472-477.
. Zeebaree, D. Q., Haron, H., Abdulazeez, A. M., &Zeebaree, S. R. (2017). “Combination of K-means clustering with Genetic Algorithm:” A review. International Journal of Applied Engineering Research. 12(24), pp.14238-14245.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Sunday J. Agbolade, Ayinla , Lateefat A. Odeniyi, Akinola S. O.
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Authors who submit papers with this journal agree to the following terms.
