A New Heuristic Algorithm for Student-Project Allocation with Lecturer Preferences and Ties

The problem of The Student-Project Allocation problem with lecturer preferences over the Students containing Ties (SPA-ST) has attracted the attention of researchers because of its wide applications in allocating students to projects at many universities. So far, many methods have been proposed to solve the SPA-ST problem, such as the approximation algorithms, integer programming models, and local search. However, the problem of finding a stable matching of maximum size (MAX-SPA-ST) is NP-hard. These methods are yet to reach the optimal solution quality and the execution time is still a bottleneck for large-scale MAX-SPA-ST problems. In this paper, we propose a new algorithm for solving the MAX-SPA-ST problem. Our algorithm designs two heuristic functions to improve the solution quality and execution time. Experimental results on large randomly generated instances show that our algorithm is more efficient than the existing methods in terms of execution time and solution quality.