Dirk Schumacher (Paderborn)

Hallo,
nehmen wir an, man möchte einen Studienverlaufsplan erstellen. Dieses Szenario richtet sich vornehmlich an Hochschulen, könnte aber auch für sonstige Personen interessant sein. Als Fachschaft kommen wir immer mal wieder mit Änderungen an Studienplänen in Kontakt und werden nach unserer Meinung gefragt. Die Frage ist aber, wie schwierig ist es einen Studienverlaufsplan zu erstellen und wieviele verschiedene Möglichkeiten hat man?

Zur Beantwortung dieser Frage, sollte zunächst geklärt werden, was ein Studienverlaufsplan überhaupt ist. Es ist eine Menge von Modulen gegeben, die auf bestehende Semester verteilt werden soll. Manche Module haben Voraussetzungen; so sollte z.B. "Grundlagen der Programmierung 1" vor "Grundlagen der Programmierung 2" gehört werden. Diese bilden eine partielle Ordnung auf den Modulen, die zusätzlich berücksichtigt werden sollte. Module verfügen desweiteren über Credit-Points und in jedem Semester sollten um die 30 gehört werden. Auch wird nicht jedes Modul in jedem Semester angeboten. Ein Beispiel aus der Praxis findet sich hier .

Betrachtet man die Semester als "Bins", so kommt dieses Problem dem Bin Packing Problem schon recht nahe. Formalisiert könnte es so aussehen:

• Eine Menge von $n$ Semestern: $S = \{S_1, \ldots, S_n\}$
• Eine Menge von $k$ Modulen: $M = \{m_1, \ldots, m_k\}$
• Die Credit Points pro Modul: $ects: M \rightarrow \mathbb{N^+}$
• Eine partielle Ordnung (Voraussetzungs-Relation): $\prec \subseteq M \times M$
• Eine Unter- und Obergrenze der ECTS pro Semester: $lb/ub: S \rightarrow \mathbb{N^+}$
• Das Modulangebot: $poss \subseteq S \times M$

Das Problem einen Studienplan zu finden, gestaltet sich also wie folgt:

1. $S$ ist eine Partition von $M$
2. Voraussetzungen beachten: $(x,y \in M, x \prec y\text{ und } x\in S_i, y \in S_j) \Rightarrow i < j$
3. Credit-Points beachten: $\forall s \in S \text{ } lb(s) \leq \sum_{m \in s}ects(m) \leq ub(s)$
4. Angebot der Module: $\forall s \in S\text{ }\forall m \in s \text{ } poss(s,m)$

Auch deckt das Modell nicht alle Use-Cases (is ja auch schon spät) ab; so ist es nicht ohne weiteres möglich Restriktionen à la "Bachelor Arbeit erst nach erfolgreichen 120 CP" zu modellieren.
Natürlich könnte man sich noch Zielfunktionen überlegen. Wie z.B. die Minimierung des durchschnittlichen Aufwands pro Semester.
Insgesamt erscheint es mir aber sinnvoll, möglichst viele valide Anordnungen zu generieren und dann per Hand auszuwählen. Vermutung ist hier, dass die Restriktionen die Anzahl der Partitionen hinreichend reduziert.
Als Lösungsalgorithmen kommen natürlich die meisten Contraint-Programming Algorithmen in Frage. Auch habe ich damals ein Integer-Programming Model ohne Zielfunktion geschrieben, das ein ähnliches Problem löst. Dies eignet sich recht gut, da für IP Probleme gute Modellierungs-Sprachen existieren.

Wie es der Zufall will, habe ich mal wieder eine Prüfung am Donnerstag, so dass ich auch diese geistigen Ergüsse zunächst auf Eis legen werde.