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

Uyen T. Nguyen (), Sang X. Tran () and Canh V. Pham
Additional contact information
Uyen T. Nguyen: Institute of Engineering and Technology, Vinh University, 182 Le Duan Street, Vinh City, Nghe An, Vietnam
Sang X. Tran: Cyber School, Vinh University, 182 Le Duan Street, Vinh City, Nghe An, Vietnam
Canh V. Pham: ORLab, Faculty of Computer Science, Phenikaa University, Hanoi, Vietnam

Asia-Pacific Journal of Operational Research (APJOR), 2025, vol. 42, issue 05, 1-27

Abstract: 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.

Keywords: Student-Project allocation problem; heuristic algorithm; blocking pairs; weakly stable matching; MAX-SPA-ST; large sizes (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595925500058
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:42:y:2025:i:05:n:s0217595925500058

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595925500058

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().