Meta-Heuristic Solutions to a Student Grouping Optimization Problem faced in Higher Education Institutions

Main Article Content

Kenekayoro Patrick
Biralatei Fawei

Abstract

Combinatorial problems which have been proven to be NP-hard are faced in Higher Education Institutions and researches have extensively investigated some of the well-known combinatorial problems such as the timetabling and student project allocation problems. However, NP-hard problems faced in Higher Education Institutions are not only confined to these categories of combinatorial problems. The majority of NP-hard problems faced in institutions involve grouping students and/or resources, albeit with each problem having its own unique set of constraints. Thus, it can be argued that techniques to solve NP-hard problems in Higher Education Institutions can be transferred across the different problem categories. As no method is guaranteed to
outperform all others in all problems, it is necessary to investigate heuristic techniques for solving lesser-known problems in order to guide stakeholders or software developers to the most appropriate algorithm for each unique class of NP-hard problems faced in Higher Education Institutions. To this end, this study described an optimization problem faced in a real university that involved grouping students for the presentation of semester results. Ordering based heuristics, genetic algorithm and the ant colony optimization algorithm implemented in Python programming language were used to find feasible solutions to this problem, with the ant colony optimization algorithm performing better or equal in 75% of the test instances and the genetic algorithm producing better or equal results in 38% of the test instances.

Keywords:
Genetic algorithm, meta-heuristics, ant colony optimization, student grouping, combinatorial problem

Article Details

How to Cite
Patrick, K., & Fawei, B. (2020). Meta-Heuristic Solutions to a Student Grouping Optimization Problem faced in Higher Education Institutions. Journal of Advances in Mathematics and Computer Science, 35(7), 61-74. https://doi.org/10.9734/jamcs/2020/v35i730304
Section
Original Research Article

References

Salwani Abdullah, Hamza Turabieh. On the use of multi neighbourhood structures within a Tabu-based memetic approach to university timetabling problems. Information Sciences. 2012;191:146-168.

Zhipeng L¨u, Jin-Kao Hao, Zhipeng L. Adaptive Tabu Search for course timetabling. European Journal of Operational Research. 2010;200(1):235-244.

Salwani Abdullah, Khalid Shaker, Barry Mccollum, Paul Mcmullan. Dual sequence simulated annealing with round-robin approach for university course timetabling. Evolutionary Computation in Combinatorial Optimization. Springer-Verlag. 2010;1-10.

Patrick Kenekayoro, Godswill Zipamone. Greedy ants colony optimization strategy for solving the curriculum based university course timetabling problem. British Journal of Mathematics & Computer Science. 2016;14(2):1-10.

Hamed Babaei, Jaber Karimpour, Amin Hadidi. A survey of approaches for university course timetabling problem. Computers and Industrial Engineering. 2015;86:43-59.

David Manlove, Duncan Milne, Sofiat Olaosebikan. Student-project allocation with preferences over projects: Algorithmic and experimental results. Discrete Applied Mathematics; 2020.

Patrick Kenekayoro, Promise Mebine, Bodouowei Godswill Zipamone. Population based techniques for solving the student project allocation problem. International Journal of Applied Metaheuristic Computing (IJAMC). 2020;11(2):192-207.

Marco Chiarandini, Rolf Fagerberg, Stefano Gualandi. Handling preferences in student-project allocation. Annals of Operations Research. 2018;1-40.

Augustine Kwanashie, Robert W. Irving, David F. Manlove, Colin T. S. Sng. Profile-based optimal matchings in the student/project allocation problem. International Workshop on Combinatorial Algorithms. Springer, Cham. 2015;213-225.

Mohammed A. Awadallah, Ahamad Tajudin Khader, Mohammed Azmi Al-Betar, Asaju La’aro Bolaji. Global best Harmony Search with a new pitch adjustment designed for Nurse Rostering. Journal of King Saud University - Computer and Information Sciences. 2013;25(2):145-162.

Ghaith M. Jaradat, Anas Al-Badareen, Ayob M, Mutasem Al-Smadi, Ibrahim Al-Marashdeh, Mahmoud Ash-Shuqran, Eyas Al-Odat. Hybrid elitist-ant system for nurse-rostering problem. Journal of King Saud University - Computer and Information Sciences. 2019;31(3):378-384.

Jingpeng Li, Edmund K Burke, Rong Qu. A pattern recognition based intelligent search method and two assignment problem case studies. Applied Intelligence. 2010;36(2):442-453.

HY Al Tarawneh, Masri Ayob. Using Tabu search with multi-neighborhood structures to solve University Course Timetable UKM case study (faculty of engineering). Data Mining and Optimization (DMO). 2011;28-29.

Ayla G¨ulc¨u, Can Akkan. Robust university course timetabling problem subject to single and multiple disruptions. European Journal of Operational Research. 2020;283(2):630-646.

F´elix Antoine Fortin, Francois Michel De Rainville, Marc-Andr´e Gardner, Marc Parizeau, Christian Gagn´e. DEAP: Evolutionary algorithms made easy. Journal of Machine Learning Research. 2012;13:2171-2175.

Rong Qu, Edmund K. Burke, Barry McCollum. Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems. European Journal of Operational Research. 2009;198(2):392-404.

Edmund Burke, Barry MacCloumn, Amnon Meisels, Sanja Petrovic, Rong Qu. A graphbased hyper heuristic for timetabling problems. European Journal of Operational Research. 2010;176:177-192.

Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperating agents. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions. 1996;26(1):29-41.

Krzysztof Socha, Joshua Knowles, Michael Sampels. A MAX - MIN ant system for the university course timetabling problem. Lecture notes in computer science: Proceedings of the 3rd international workshop on ant algorithms. Springer Berlin. 2002;1-13.

Razamin Ramli. A hybrid ant colony optimization algorithm for solving a highly constrained nurse rostering problem. Journal of Information and Communication Technology. 2020;18(3):305-326.

Nico Ulder, Emile Aarts, Hans-J¨urgen Bandelt, Peter van Laarhoven, Erwin Pesch. Genetic local search algorithms for the traveling salesman problem parallel problem solving from nature. In Hans-Paul Schwefel, Reinhard M¨anner, Editors. International Conference on Parallel Problem Solving from Nature. Lecture Notes in Computer Science. Springer Berlin / Heidelberg. 1990;496;109-116.

Jorge Magalh~aes-Mendes. A comparative study of crossover operators for genetic algorithms to solve the job shop scheduling problem. WSEAS Transactions on Computers. 2013;12(4):164- 173.

Vladimi Filipovi´c. Fine-grained tournament selection operator in genetic algorithms. Computing and Informatics. 2012;22(2):143-161.

Noraini Mohd Razali, John Geraghty. Genetic algorithm performance with different selection strategies in solving TSP. In Proceedings of the World Congress on Engineering. 2011;2;1134-1139. London