A Heuristic Algorithm for Student-Project Allocation Problem
Authors: 
Nguyen Thi Uyen, Giang L. Nguyen, Canh V. Pham, Tran Xuan Sang, Hoang Huu VietAuthors Info & Claims
Pages 280 - 291
Abstract
The Student-Project Allocation problem with lecturer preferences over Students with Ties (SPA-ST) is to find a stable matching of students and projects to satisfy the constraints on student preferences over projects, lecturer preferences over students, and the maximum number of students given by each project and lecturer. This problem has attracted many researchers because of its wide applications in allocating students to projects at many universities worldwide. However, the main weakness of existing algorithms is their high computational cost. In this paper, we propose a heuristic algorithm to improve solution quality and execution time for solving the SPA-ST problem of large sizes. Experimental results on randomly generated datasets show that our algorithm outperforms the state-of-the-art algorithm regarding solution quality and execution time .
References
[1]
Abraham DJ, Irving RW, and Manlove DF Ibaraki T, Katoh N, and Ono H The student-project allocation problem Algorithms and Computation 2003 Heidelberg Springer 474-484
[2]
Abraham DJ, Irving RW, and Manlove DF Two algorithms for the student-project allocation problem J. Discrete Algorithms 2007 5 1 73-90
[3]
Aderanti, F.A., Amosa, R., Oluwatobiloba, A.: Development of student project allocation system using matching algorithm. In: International Conference Science Engineering Environmental Technology, vol. 1 (2016)
[4]
Binong J Bhattacharjee D, Kole DK, Dey N, Basu S, and Plewczynski D Solving student project allocation with preference through weights Proceedings of International Conference on Frontiers in Computing and Systems 2021 Singapore Springer 423-430
[5]
Calvo-Serrano R, Guillén-Gosálbez G, Kohn S, and Masters A Mathematical programming approach for optimally allocating students’ projects to academics in large cohorts Educ. Chem. Eng. 2017 20 11-21
[6]
Chiarandini M, Fagerberg R, and Gualandi S Handling preferences in student-project allocation Ann. Oper. Res. 2019 275 1 39-78
[7]
Cooper, F., Manlove, D.F.: A 3/2-approximation algorithm for the student-project allocation problem. In: 17th International Symposium on Experimental Algorithms, SEA 2018, 27–29 June 2018, L’Aquila, Italy, vol. 103, pp. 8:1–8:13 (2018).
[8]
Gani MA, Hamid RA, et al. Optimum allocation of graduation projects: Survey and proposed solution J. Al-Qadisiyah Comput. Sci. Math. 2021 13 1 58
[9]
Gent, I.P., Prosser, P.: An empirical study of the stable marriage problem with ties and incomplete lists. In: Proceedings of the 15th European Conference on Artificial Intelligence, pp. 141–145. Lyon, France (2002)
[10]
Harper PR, de Senna V, Vieira IT, and Shahani AK A genetic algorithm for the project assignment problem Comput. Oper. Res. 2005 32 5 1255-1265
[11]
Irving RW, Manlove DF, and Scott S The hospitals/residents problem with ties Algorithm Theory - SWAT 2000 2000 Heidelberg Springer 259-271
[12]
Iwama K, Miyazaki S, and Yanagisawa H Improved approximation bounds for the student-project allocation problem with preferences over projects J. Discrete Algorithms 2012 13 59-66
[13]
Király Z Linear time local approximation algorithm for maximum stable marriage Algorithms 2013 6 1 471-484
[14]
Kwanashie A, Irving RW, Manlove DF, and Sng CTS Kratochvíl J, Miller M, and Froncek D Profile-based optimal matchings in the student/project allocation problem Combinatorial Algorithms 2015 Cham Springer 213-225
[15]
Manlove, D., Milne, D., Olaosebikan, S.: An integer programming approach to the student-project allocation problem with preferences over projects. In: Proceedings of 5th International Symposium on Combinatorial Optimization, pp. 213–225. Mo-rocco (2018)
[16]
Manlove D, Milne D, and Olaosebikan S Lee J, Rinaldi G, and Mahjoub AR An integer programming approach to the student-project allocation problem with preferences over projects Combinatorial Optimization 2018 Cham Springer 313-325
[17]
Manlove, D.F.: Algorithmics of Matching Under Preferences, Series on Theoretical Computer Science, vol. 2 (2013).
[18]
Manlove DF and O’Malley G Student-project allocation with preferences over projects J. Discrete Algorithms 2008 6 4 553-560
[19]
Olaosebikan S and Manlove D Changat M and Das S An algorithm for strong stability in the student-project allocation problem with ties Algorithms and Discrete Applied Mathematics 2020 Cham Springer 384-399
[20]
Olaosebikan S and Manlove D Super-stability in the student-project allocation problem with ties J. Comb. Optim. 2020 43 1-37
[21]
Paunović V, Tomić S, Bosnić I, and Žagar M Fuzzy approach to student-project allocation (spa) problem IEEE Access 2019 7 136046-136061
[22]
Irving RW and Manlove DF Finding large stable matchings J. Exp. Algorithmics 2009 14 1 1-2
Index Terms
- A Heuristic Algorithm for Student-Project Allocation Problem
Index terms have been assigned to the content through auto-classification.
Recommendations
Exact Heuristic Algorithm for Traveling Salesman Problem
ICYCS '08: Proceedings of the 2008 The 9th International Conference for Young Computer ScientistsNatural properties of stochastic searching strategies and operations in metaheuristic algorithms have important influence on convergence performance of various metaheuristic algorithms. Through similarity analysis to two kinds of metaheuristic ...
A Heuristic Method for the Set Covering Problem
We present a Lagrangian-based heuristic for the well-known Set Covering Problem (SCP). The algorithm was initially designed for solving very large scale SCP instances, involving up to 5,000 rows and 1,000,000 columns, arising from crew scheduling in the ...
Scatter search for trainees to software project requirements stable allocation
In this paper, we study a centralized, stable matching scheme, which allocates trainees to software project requirements, to minimize retraining and relocation costs when the preference lists of the project requirements may contain ties of arbitrary ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Dec 2022
313 pages
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 05 December 2022
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 28 Feb 2025