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 so 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. (Zum Beispiel liegt diese Zahl beim Leistungskurs Mathematik an Gymnasien bei 5 Unterrichtseinheiten.) 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.

Exakte Problemformulierung:
Gesucht ist eine Verteilung aller Unterrichtseinheiten auf p Zeiteinheiten so, dass kein Schüler zur selben Zeiteinheit mehr als eine Unterrichtseinheit belegen muß.

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_b', so werden ausserdem Kanten zwischen jedem Knoten von K_b und jedem Knoten von K_b' 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₁, K₂ und K₃ gegeben mit der in der Tabelle dargestellten Unterrichtseinheitenzahl, zwei Schüler S₁ und S₂ wählten die folgende Kursbelegung. Der Schüler S₁ belegt die Kurse K₁ und K₂, der Schüler S₂ belegt die Kurse K₂ und K₃.
Gesucht ist ein Kursplan in 4 Zeiteinheiten.

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

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:

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 ≥ 3 ein NP-vollständiges Optimierungsproblem ist.