2020/10/01 by Patrick Kenekayoro, Kenekayoro, Patrick, Biralatei Fawei +1
Decision Sciences · Engineering · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Resource-Constrained Project Scheduling #Scheduling and Timetabling Solutions #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2010.00499
openalex publication_date 2020/10/01 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
Combinatorial problems which have been proven to be NP-hard are faced in\nHigher Education Institutions and researches have extensively investigated some\nof the well-known combinatorial problems such as the timetabling and student\nproject allocation problems. However, NP-hard problems faced in Higher\nEducation Institutions are not only confined to these categories of\ncombinatorial problems. The majority of NP-hard problems faced in institutions\ninvolve grouping students and/or resources, albeit with each problem having its\nown unique set of constraints. Thus, it can be argued that techniques to solve\nNP-hard problems in Higher Education Institutions can be transferred across the\ndifferent problem categories. As no method is guaranteed to outperform all\nothers in all problems, it is necessary to investigate heuristic techniques for\nsolving lesser-known problems in order to guide stakeholders or software\ndevelopers to the most appropriate algorithm for each unique class of NP-hard\nproblems faced in Higher Education Institutions. To this end, this study\ndescribed an optimization problem faced in a real university that involved\ngrouping students for the presentation of semester results. Ordering based\nheuristics, genetic algorithm and the ant colony optimization algorithm\nimplemented in Python programming language were used to find feasible solutions\nto this problem, with the ant colony optimization algorithm performing better\nor equal in 75% of the test instances and the genetic algorithm producing\nbetter or equal results in 38% of the test instances.\n