Open Access

Pavel Safre

• Diese Arbeit zeigt, dass die optimale Verteilung von Individuen in Gruppen unter Beachtung ihrer Zeitpräferenzen ein NP-schweres Problem ist. Daher liegt es Nahe, dass für große Teilnehmerzahlen eine optimale Lösung nicht in praxistauglicher Zeit berechnet werden kann. Hier kann eine geeignete Heuristik Abhilfe schaffen. Da dieses Problem in Universitäten für Studierende bei der Zuteilung der Übungsgruppen für Hunderte von Teilnehmern jedes Semester aufs Neue gelöst werden muss, macht es Sinn, dabei eine rechnergestützte Lösung einzusetzen. In dieser Arbeit werden die gängigsten in Deutschland und insbesondere an der Goethe-Universität Frankfurt am Main verwendeten Gruppeneinteilungssysteme untersucht. Alle aktuell eingesetzten Lösungen weisen offensichtliche Mängel auf. In dieser Arbeit wird analysiert, weshalb es dazu kommt und gezeigt, wie diese Mängel vermieden werden können. Außerdem werden Kriterien entwickelt und diskutiert, die ein gutes Gruppeneinteilungssystem erfüllen sollte. Es wird beschrieben, inwiefern eine gute mit einer Heuristik schnell berechenbare approximative Lösung des Gruppeneinteilungsproblems besser als eine perfekte Lösung sein könnte. Mehrere Heuristiken werden verglichen und eine für dieses Problem gut passende wird entwickelt und implementiert. Mithilfe der Beispielimplementierung und anhand anonymisierter Anmeldedaten für die Veranstaltungen aus vergangenen Jahren wird gezeigt, welche Ergebnisse bei dem Wechsel zu einem solchen System erreicht werden können. Weiterhin wird analysiert, wie ein solches Gruppeneinteilungssystem an die anderen an Universitäten eingesetzten digitalen Systeme angekoppelt werden kann. Das ist notwendig, um zu vermeiden, dass die redundanten Studierendendaten doppelt gepflegt werden müssen. Somit werden Konsistenz und Korrektheit der Daten bei dem Einsatz eines neuen Systems gefördert. Abschließend wird ein Ausblick in die Zukunft der Gruppeneinteilungssysteme gegeben und beschrieben, welche Aspekte in diesem Bereich weiterhin wichtig sein könnten.
• This thesis shows that the optimal distribution of individuals in groups under consideration of their temporal preferences is a NP-hard problem. This suggests that an optimal solution cannot be computed in practical time. A suitable heuristic can provide thereby a remedy. Due to the fact that this problem has to be solved for hundreds of course participants, when a university has to distribute students in groups for the group study, it makes sense to use thereby a PC-aided solution. This thesis examines the group distribution systems, which are most commonly used in Germany and especially in Goethe University Frankfurt. All these solutions have obvious flaws. This thesis analyzes why these problems were encountered and how they may be prevented in the future implementations. Furthermore criteria is developed and discussed, that are essential for a good group distribution system. Here is described, in what way a good approximate result, gained with a quick heuristic approach, may be better than a perfect result. Multiple heuristics were compared with each other and a new one was developed and implemented, that suits best for this particular problem. With the aid of the implemented prototype and the anonymized registration data of the past years it is demonstrated, what kind of results may be achieved, if such a system is used for this task. In addition it is analyzed, how such group distribution system may be connected with the other computer systems in a university. This is necessary to avoid the need of the double maintenance of the redundant student data. Consequently the consistency and correctness of the user data is facilitated if an additional system is to be deployed. In conclusion the forecasts in this branch are provided and it is shown, which aspects could be the most relevant in the future.