Алгоритмы распределения студентов по учебным группам

Екатерина Валерьевна Глазунова

doi:10.17308/meps/2078-9017/2025/9/24-39

Екатерина Валерьевна Глазунова Санкт-Петербургский государственный экономический университет

DOI: https://doi.org/10.17308/meps/2078-9017/2025/9/24-39

Ключевые слова: задача о разбиении множества чисел, квазиклика, индекс Джини, смешанное программирование, жадный алгоритм

Аннотация

Предмет: методы формирования академических групп после процесса распределения студентов по учебным профилям с целью максимизации одного из четырех критериев оптимизации. Цель: разработка алгоритмов распределения студентов по учебным группам профиля с точки зрения четырех критериев оптимизации: максимизация схожести суммарного и среднего балла в учебных группах одного профиля, максимизация схожести успеваемости студентов внутри каждой учебной группы и максимизация схожести распределения по группам c предыдущим. Дизайн исследования: задачи формулируются как модификации задач о разбиении множества чисел, для оценки схожести успеваемости студентов внутри учебных групп используется индекс Джини, решается задача о разбиении графа на квази-клики с максимальной плотностью. Результаты: для каждой задачи сформулирована задача смешанного программирования, а также жадные алгоритмы. Математические модели и алгоритмы апробированы на данных СПбГЭУ при распределении студентов направления «Экономика».

Скачивания

Данные скачивания пока не доступны.

Биография автора

Екатерина Валерьевна Глазунова, Санкт-Петербургский государственный экономический университет

аналитик, ассистент

Литература

1. Васильев Ю.М., Глазунова Е.В. и Фридман Г.М. Умный университет: справедливое распределение студентов по учебным профилям // Вестник ВГУ. Серия: Экономика и управление, 2024, no. 5, с. 16-24.
2. Мину М. Математическое программирование. Теория и алгоритмы. Москва, Наука, 1990. 485 c.
3. Brimberg J., Janićijević S., Mladenović N. et al. Solving the clique partitioning problem as a maximally diverse grouping problem // Optim Lett, 2017, no. 11, pp. 1123-1135.
4. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to Algorithms, third edition. The MIT Press Cambridge, Massachusetts London, England, 2009. 1312 p.
5. De Amorim, S.G., Barthélemy JP. & Ribeiro C.C. Clustering and clique partitioning: Simulated annealing and tabu search approaches // Journal of Classification, 1992, no. 9, pp. 17-41.
6. Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company. 1979. 238 p.
7. Gini C. On the Measure of Concentration with Special Reference to Income and Statistics // Colorado College Publication, General Series, 1936, no. 208, pp. 73-79.
8. Graham R.L. Bounds on multiprocessing timing anomalies // SIAM Journal on Applied Mathematics, 1969, no. 17(2), pp. 416-429.
9. Korf R. Multi-Way Number Partitioning // IJCAI International Joint Conference on Artificial Intelligence, 2009, pp. 538-543.
10. Korf R. Objective functions for MultiWay number partitioning // Proceedings of the International Symposium on Combinatorial Search, 2010, no. 1(1), pp. 71-72.
11. Melo R., Ribeiro C., Riveaux M.J. The minimum quasi-clique partitioning problem: Complexity, formulations, and a computational study // Information Sciences, 2022, no. 612.
12. Ribeiro C., Riveaux M.J. An exact algorithm for the maximum quasi-clique problem // International Transactions in Operational Research, 2019, no. 26.
13. Zhou Q., Zhu T., Wu Q., Jiang Z., Wang W. An efficient iterated local search for the minimum quasi-clique partitioning problem // Computers & Operations Research, 2025, no. 179.