Um ein Gefühl für die Stundenplanung per Hand zu bekommen, versuchen Sie doch einmal das folgende Stundenplan-Problem zu lösen!

Unter dem Stundenplan-Problem aus der Informatik versteht man die Verplanung von Veranstaltungen (den Aktivitäten) auf Räume (den Ressourcen) über der Zeit unter der Berücksichtigung von Beschränkungen. In unserem Planspiel sind zwei Räume vorgegeben, wie sie uns von der Hochschulverwaltung zugewiesen sein könnten (die Ressourcen: siehe Abbildung). Der Überschaubarkeit wegen sind die Räume nur montags, dienstags und mittwochs jeweils mit 2 Veranstaltungen belegbar und zwar in den Zeiten von 8 bis 10 Uhr und von 10 bis 12 Uhr. Raum 1 ist mittwochs von 10 bis 12 Uhr schon anderweitig belegt. In Raum 1 können wir daher Veranstaltungen auf 5 Termine legen, in Raum 2 auf 6 Termine. Insgesamt stehen uns also 11 freie Termine zur Verfügung.

Raum 1

Raum 2

Abbildung: Unsere Ressourcen: zwei Räume

Darüber hinaus sind 5 Fächer bestehend aus 7 Veranstaltungen zu verplanen (die Aktivitäten: siehe Tabelle 1). Wir haben insgesamt 3 Dozenten: X, Y und Z. Dozent X hält die Vorlesung A, Dozent Y unterrichtet die Fächer B und C und Dozent Z lehrt die Fächer D und E. Die Fächer C und E unterteilen sich jeweils in eine Vorlesung und eine Übung.

Dozent	Fach	Veranstaltung	Piktogramm
X	A	Vorlesung A
Y	B C	Vorlesung B Vorlesung C1, Übung C2
Z	D E	Vorlesung D Vorlesung E1, Übung E2

Tabelle 1: Unsere Aktivitäten: sieben Veranstaltungen

Betrachten wir Tabelle 1: Die Dozenten Y und Z halten jeweils drei Veranstaltungen. Da weder Dozent Y noch Dozent Z sich räumlich zerteilen können, muß gelten:

Keine Veranstaltung eines Dozenten darf zeitlich parallel zu einer anderen Veranstaltung desselben Dozenten liegen.

Nun sind noch eine Reihe von weiteren Beschränkungen bei der Stundenplanung zu berücksichtigen: Jeder Dozent hat seine individuellen Zeitwünsche: Dozent X möchte aus welchen Gründen auch immer nur mittwochs unterrichten, Dozent Y nicht montags und Dozent Z nicht montags von 8 bis 10 Uhr.

Tabelle 2: Die Zeitvorgaben der Dozenten

Darüber hinaus sind bei der Planung noch Vorgaben der Studienordnung für jedes Studiensemester zu berücksichtigen (siehe Tabelle 3). In unserem Beispiel betrachten wir die Vorgaben für ein einziges Studiensemester: Die Fächer C und E sind Pflicht (rote Piktogramme). Die Veranstaltungen A und D sind Pflichtfächer nach Wahl, von denen der Student ein Fach belegen muß (gelbe Piktogramme). Aus diesen Bedingungen der Studienordnung heraus sollte ein Student also die Fächerkombinationen C, E, und A oder C, E und D belegen können. Die Veranstaltung B (grünes Piktogramm) ist ein reines Wahlfach, das Studierende freiwillig hören können.

Tabelle 3: Die Studienordnung

Aus diesen drei unscheinbaren Vorgaben der Studienordnung ergibt sich bei systematischer Betrachtung eine Fülle von Beschränkungen der Form, welche Veranstaltung nicht gleichzeitig zu einer anderen stattfinden darf. All solche Beschränkungen sind in der nachfolgenden Tabelle aufgelistet. Außerdem sind zu jeder Veranstaltung die zeitlichen Vorgaben der entsprechenden Dozenten angeführt. Schließlich muß offensichtlich noch gelten, daß zwei Veranstaltungen zur gleichen Zeit nicht im selben Raum stattfinden dürfen. Somit haben wir in Tabelle 4 unsere Problemstellung kompakt dargestellt. Bemerkenswert ist bei diesem einfachen Beispiel schon die Komplexität des Problems, die sich in der Anzahl der zu erfüllenden Nebenbedingungen niederschlägt.

Tabelle 4: Alle Beschränkungen

Die Aufgabenstellung kurzgefaßt: Plazieren Sie alle sieben Veranstaltungen so, daß alle Beschränkungen aus Tabelle 4 erfüllt werden! Nun viel Vergnügen bei der Lösung dieses Stundenplanproblems (es gibt mehrere korrekte Lösungen)!

Mit Java wäre das der interaktive Selbstversuch gewesen!

Benötigt Netscape Communicator.

Web-Designer: Hans Peter Kunz. UniPlaner-Logo: Veit Duwe, Lübeck. Letzte Änderung: 25-11-1998.