The SEKO assignment. Efficient and fair assignment of students to multiple seminars

• Authors: HOßFELD Tobias
• Languages of publication: EN

Abstracts

EN

Seminars are offered to students for education in various disciplines. The seminars may be limited in terms of the maximum number of participants, e.g., to have lively interactions. Due to capacity limitations, those seminars are often offered several times to serve the students’ demands. Still, some seminars are more popular than others and it may not be possible to grant access to all interested students due to capacity limitations. In this paper, a simple, but efficient random selection using key objectives (SEKO) assignment strategy is proposed which achieves the following goals: (i) efficiency by utilizing all available seminar places, (ii) satisfying all students by trying to assign at least one seminar to each student, and (iii) fairness by considering the number of assigned seminars per student. We formulate various theoretical optimization models using integer linear programming (ILP) and compare their solutions to the SEKO assignment based on a real-world data set. The real-world data set is also used as the basis for generating large data sets to investigate the scalability in terms of demand and number of seminars. Furthermore, the first-in first-out (FIFO) assignment, as a typical implementation of fair assignments in practice, is compared to SEKO in terms of utilization and fairness. The results show that the FIFO assignment suffers in real world situations regarding fairness, while the SEKO assignment is close to the optimum and scales regarding computational time in contrast to the ILP.

Keywords

EN

assignment problem; limited capacity; utilization; at least on seminar (ALOS) ratio; fairness; integer linear; programming (ILP); first-in first-out (FIFO) assignment; random selection using key objectives (SEKO)

• Publisher: Politechnika Wrocławska. Oficyna Wydawnicza Politechniki Wrocławskiej
• Journal: Operations Research and Decisions
• Year: 2023
• Volume: 33
• Issue: 3
• Pages: 1-27

Contributors

author

HOßFELD Tobias

• Chair of Communication Networks, Faculty of Mathematics and Computer Science, University of Würzburg, Germany

References

• Al Mulhim, E. N., and Eldokhny, A. A. The impact of collaborative group size on students’ achievement and product quality in project-based learning environments. International Journal of Emerging Technologies in Learning (iJET) 15, 10 (2020), 157–174.
• Avi-Itzhak, B., Levy, H., and Raz, D. Quantifying fairness in queuing systems: Principles, approaches, and applicability. Probability in the Engineering and Informational Sciences 22, 4 (2008), 495–517.
• Cattrysse, D. G., and Van Wassenhove, L. N. A survey of algorithms for the generalized assignment problem. European Journal of Operational Research 60, 3 (1992), 260–272.
• Chen, L.-T., and Liu, L. Social presence in multidimensional online discussion: The roles of group size and requirements for discussions. Computers in the Schools 37, 2 (2020), 116–140.
• Efraimidis, P. S. Weighted random sampling over data streams. In Algorithms, Probability, Networks, and Games. vol. 9295 of Lecture Notes in Computer Science, C. Zaroliagis, G. Pantziou, and S. Kontogiannis, Eds., Springer, Cham 2015, pp. 183–195.
• Garg, N., Kavitha, T., Kumar, A., Mehlhorn, K., and Mestre, J. Assigning papers to referees. Algorithmica 58, 1 (2010), 119–136.
• Hoßfeld, T., Skorin-Kapov, L., Heegaard, P. E., and Varela, M. A new QoE fairness index for QoE management. Quality and User Experience 3, 1 (2018), 4.
• Jain, R. K., Chiu, D.-M. W., and Hawe, W. R. A quantitative measure of fairness and discrimination for resource allocation in shared computer systems. DEC Research Report TR-301, Eastern Research Laboratory, Digital Equipment Corporation, Hudson, MA, 1984.
• Magnanti, T. L., and Natarajan, K. Allocating students to multidisciplinary capstone projects using discrete optimization. Interfaces 48, 3 (2018), 204–216.
• Öncan, T. A survey of the generalized assignment problem and its applications. INFOR: Information Systems and Operational Research 45, 3 (2007), 123–141.
• Rezaeinia, N., Góez, J. C., and Guajardo, M. Efficiency and fairness criteria in the assignment of students to projects. Annals of Operations Research 319, 2 (2021), 1717– 1735.
• Roeder, T. M., and Saltzman, R. M. Schedule-based group assignment using constraint programming. INFORMS Transactions on Education 14, 2 (2014), 63–72.
• Wang, F., Chen, B., and Miao, Z. A survey on reviewer assignment problem. In New Frontiers in Applied Artificial Intelligence. 21st International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems. IEA/AIE (Wrocław, 2008), vol. 5027 of Lecture Notes in Computer Science, N. T. Nguyen, L. Borzemski, A. Grzech, and M. Ali, Eds., Springer, Berlin 2008, pp. 718–727.
• Wierman, A. Fairness and scheduling in single server queues. Surveys in Operations Research and Management Science 16, 1 (2011), 39–48.

Identifiers

DOI

10.37190/ord230301