Das Kursplanungsproblem

Alljährlich findet vor dem Schuljahresbeginn in Schulen und Gymnasien ein Stöhnen der Verantwortlichen für die Unterrichtsplanung statt: Wie sind alle Klassen, alle Lehrer, alle Räume und die zur Verfügung stehende Tageszeit unter einen Hut zu bringen? Das hier vorgestellte Kursplanungsproblem ist eine Form eines solchen Stundenplanproblems.

Ein Kurs ist ein Unterrichtsfach (bspw. das Fach Mathematik) mit einer vorgegebenen Zahl von Unterrichtseinheiten pro Woche. Es sei nun eine Zahl von Kursen mit jeweilig bestimmtem Unterrichtseinheitenumfang vorgegeben. Jeder Schüler kann sich (unter Einhaltung gewisser bekannter Regeln und Bedingungen) eine bestimmte Zahl von Kursen aussuchen, die er belegen will. Diese Auswahl kann durchaus bei verschiedenen Schülern verschiedene Gestalt annehmen. Das Kursplanungsproblem besteht nun darin, Unterrichtseinheiten widerspruchsfrei für alle Schüler zu verteilen.

Kursplanungsproblem: Gesucht ist eine Verteilung aller Unterrichtseinheiten auf $p$ Zeiteinheiten so, dass kein Schüler zur selben Zeiteinheit mehr als eine Unterrichtseinheit belegen muss.

Um dieses Problem zu modellieren, nutzen wir die Graphentheorie. Es entsteht aus den folgenden Betrachtungen der Entwurf eines Graphen: Sei $L_a$ eine Unterrichtseinheit des Kurses $K_b$. Die Unterrichtseinheit $L_a$, zu $K_b$ gehörig, werde durch einen Knoten $m_{ab}$ repräsentiert, demzufolge besitzt jede Unterrichtseinheit jedes Kurses einen entsprechenden Knoten. Für jeden Kurs werden so Kanten eingeführt, dass alle Unterrichtseinheiten des Kurses jeweils paarweise benachbart sind. Belegt ein Schüler den Kurs $K_b$ und $K_c$, so werden ausserdem Kanten zwischen jedem Knoten von $K_b$ und jedem Knoten von $K_c$ gezogen.

Die Lösung des Problems läuft auf die Lösung eines Knotenfärbungsproblems hinaus.

Graphentheoretische Problemformulierung: Gesucht ist eine Knotenfärbung aller Knoten mit $p$ Farben so, dass keine zwei benachbarten Knoten diesselbe Farbe erhalten.

Beispiel: Es seien die Kurse $K_1$, $K_2$ und $K_3$ gegeben mit der in der Tabelle dargestellten Unterrichtseinheitenzahl (Tabelle 2), zwei Schüler $S_1$ und $S_2$ wählten die folgende Kursbelegung. Der Schüler $S_1$ belegt die Kurse $K_1$ und $K_2$, der Schüler $S_2$ belegt die Kurse $K_2$ und $K_3$. Gesucht ist ein Kursplan in 4 Zeiteinheiten.

Kurs	Zahl der Unterrichtseinheiten	Repräsentierende Knoten
$K_1$	$1$	$m_{11}$
$K_2$	$2$	$m_{12}$, $m_{22}$
$K_3$	$2$	$m_{13}$, $m_{23}$

Nach der obigen Vorschrift entsteht dann der in der folgenden Abbildung 4 gezeigte Graph.

Abbildung 4: Graph zur Kursplanung.

In diesem Graph sind auf die Knoten $p=4$ Farben zu verteilen, ohne dass zwei benachbarte Knoten diesselbe Färbung erhalten. Durch einfaches Überlegen und durch Hinsehen gelangt man sehr schnell zu der folgenden Lösung (Tabelle 3).

1. Stunde	Unterrichtseinheit 1 von $K_1$
	Unterrichtseinheit 1 von $K_3$
2. Stunde	Unterrichtseinheit 1 von $K_2$
3. Stunde	Unterrichtseinheit 2 von $K_2$
4. Stunde	Unterrichtseinheit 2 von $K_3$

Diese Klasse von Problemen werden mit grossen Zahl von Kursen und vielen verschiedenenartigen Schülerbelegungen sehr kompliziert. Abhängig von der Zahl $p$ ist es nicht immer möglich, einen Kursplan in $p$ Zeiteinheiten zu finden. Es wurde nachgewiesen, dass das Kursplanungsproblem für $p\ge 3$ ein NP-vollständiges Optimierungsproblem ist.