Affiliations: [a] Faculty of Information Technology, Vinh University, Nghe An, Vietnam
| [b]
Institute of Information Technology, Vietnam Academy of Science and Technology, Hanoi, Vietnam
Correspondence:
[*]
Corresponding author. Hoang Huu Viet, Faculty of Information Technology, Vinh University, Nghe An, Vietnam. E-mail: [email protected].
Abstract: The Student-Project Allocation with preferences over Projects problem is a many-to-one stable matching problem that aims to assign students to projects in project-based courses so that students and lecturers meet their preference and capacity constraints. In this paper, we propose an efficient two-heuristic algorithm to solve this problem. Our algorithm starts from an empty matching and iteratively constructs a maximum stable matching of students to projects. At each iteration, our algorithm finds an unassigned student and assigns her/his most preferred project to her/him to form a student-project pair in the matching. If the project or the lecturer who offered the project is over-subscribed, our algorithm uses two heuristic functions, one for the over-subscribed project and the other for the over-subscribed lecturer, to remove a student-project pair in the matching. To reach a stable matching of a maximum size, our two heuristics are designed such that the removed student has the most opportunities to be assigned to some project in the next iterations. Experimental results show that our algorithm is efficient in execution time and solution quality for solving the problem.
Keywords: Approximation algorithm, heuristic search, matching problem, student-project allocation problem
