Schulische Stundenpläne
(School-Timetabling/STP)

Informelle Beschreibung:
Das School-Timetabling-Problem (STP) ist das klassische Problem des Gebietes und in seiner Grundform mit dem oben dargestellten Spezialfall des POSS (s. Abschnitt 2.1.2) identisch. Gegeben eine Menge von Lehrern und eine von Klassen, sowie eine Vorgabe, wieviele Stunden ein Lehrer eine Klasse unterrichten soll, ist eine Zuordnung von Unterrichtsstunden zu Schulstunden zu finden.

Darstellung als ILP:
Gesucht ist eine Lösung des Problems: Gegeben und finde mit

D.h. jeder Lehrer (a) und jede Klasse (b) haben pro Zeitstunde (c) maximal eine Schulstunde und erfüllen dennoch in der Summe ihr Deputat ( ).

Nebenbedingungen (z.B. [Cos94]):

• Unverfügbarkeiten von Lehrern und Klassen
• Minimierung der Springstundenzahl
• keine Klasse darf dasselbe Fach zweimal am Tag haben (mit Unterbrechung)
• keine Klasse darf ein Fach am selben Tag länger als drei Stunden haben
• die einzelnen Stunden eines Faches müssen über die Woche verteilt sein
• die Fächer müssen gleichmäßig über die Woche verteilt liegen.
• Gleichzeitigkeitsanforderungen
• optimale Fachraumausnutzung
• Lehrer mit halber Stelle haben mindestens zwei Tage frei
• örtliche Gegebenheiten: Der Übergang von einem Raum zum anderen muß z.B. innerhalb einer Pause möglich sein
• ungünstige Fachabfolgen: Z.B. drei Fremdsprachenkurse hintereinander sollten vermieden werden
• Klassenlehrer sollten jeden Tag eine Stunde in ihrer Klasse unterrichten
• konkrete Frei- und Vorbereitungszeitsanforderungen der Lehrer