Schulische Stundenpläne (School-Timetabling/STP)
Next: Daily School Timetabling Up: Übersicht über das Spektrum Previous: Terminologie
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
(c) Martin Loehnertz 1999