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

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.