Terminologie

Obwohl das Gebiet als solches schon relativ alt ist [Lew61], konnte sich bis heute keine einheitliche Terminologie durchsetzen. Infolgedessen mußten innerhalb dieser Arbeit eigene Definitionen vorgenommen werden, wobei zu großen Teilen SCHAERF [Sch95] gefolgt wurde.  

Scheduling, Roostering

Im allgemeinen wird die automatische Stundenplanerstellung als Teilgebiet des Schedulingbetrachtet. Wie WREN [Wre95] hierzu ausführt, hat sich diese Relation aber im Laufe der Zeit verschoben, insbesondere, da sich der Schwerpunkt im Schedulinglangsam zugunsten speziellerer Fragestellungen verändert hat. In [Wre95] finden sich folgende Definitionsversuche:

Scheduling

ist das Lösen praktischer Probleme bestehend aus der von Nebenbedingungen beeinflußten Zuordnung von Ressourcen zu Objekten, die in der Raumzeit angeordnet werden, wobei (laut WREN) die Wahl der Methoden keine Rolle spielt. Häufig tritt dabei auch ein Optimierungsaspekt hinzu.

Timetabling

ist Schedulingmit dem Versuch, die Nebenbedingungen so gut wie nur möglich zu erfüllen.

Scheduling (speziell)

ist Schedulingzur Minimierung einer Teilmenge der verwendeten Ressourcen.

Roostering

ist die Ressourcenzuteilung in einem ansonsten fertigen Plan.

Sequencing

beschränkt sich auf die Angabe einer Reihenfolge, ohne konkrete Zeitpunkte oder Orte festzulegen.

Somit ergibt sich das folgende Bild, wobei auffällig ist, daß es keinen eigentlichen Unterschied zwischen Schedulingund Timetablingmehr gibt.

Obwohl sich das Timetablingals Gebiet vom speziellen Schedulingschon soweit entfernt hat, daß einige Autoren bereits explizit darauf hinweisen, wenn sie Methoden aus diesem Gebiet anwenden [SM97], sind doch einige grundlegende Ideen aus diesem Themenkomplex übernommen worden. Beschränkt man sich zunächst auf die herkömmliche Aufgabe des Scheduling, Aktionen, die bestimmte Ressourcen benötigen, zeitlich anzuordnen, so können folgende Adjektive dieses Gebiets zur genaueren Klassifikation der automatischen Stundenplanerstellung verwendet werden:

preemptiv nicht preemptiv:

Preemptiv bedeutet, daß die Aktionen unterbrochen werden können.

statisch dynamisch:

Als dynamisch bezeichnet man die Variante des Problems, bei der einzelne Aktionen verplant werden müssen, bevor alle dem Algorithmus bekannt sind. Der dynamische Fall tritt z.B. beim Prozessor-Scheduling auf. Diese Variante fällt somit in den Bereich der Online-Algorithmen.

Demnach wäre Stundenplanerstellung nichtpreemptives, statisches Scheduling.

Das open shop scheduling model (OSS)

  Das Open Shop Scheduling Modell (z.B. [dW96]) unterscheidet sich vom schulischen Problem in erster Linie durch den verwendeten Kontext: Eine Menge von Prozessoren soll eine Menge von Aufgaben bearbeiten. Jede Aufgabe besteht aus n Einzelschritten , wobei Einzelschritt auf Prozessor ausgeführt werden muß. Jeder Prozessor kann nur einen Einzelschritt gleichzeitig behandeln und von jeder Aufgabe kann sich nur ein Einzelschritt in Bearbeitung befinden.

DEWERRA [dW96] unterscheidet weiter zwischen dem preemptiven OSS (POSS) und dem nichtpreemptiven (NOSS). Bei ersterem können die Einzelschritte zu beliebigen Zeitpunkten unterbrochen und später fortgesetzt werden. Dem schulischen Problem entspräche ein diskretisiertes POSS, bei dem die Einzelschritte in jeweils nicht unterbrechbare kleinere Stücke gleicher Größe aufgeteilt werden können.

Im Rahmen des sogenannten shop scheduling gibt es noch zwei weitere Modelle, flow shop (FSS) und job shop (JSS). Beim job shop ist eine Reihenfolge der einzelnen Operationen einer Aufgabe vorgegeben, beim flow-shop haben alle Aufgaben die gleiche Zahl von Einzelschritten und die Reihenfolgen sind ebenfalls für alle identisch.

Eigene Bezeichnungen

Die folgenden Bezeichnungen entsprechen größtenteils dem an Schulen üblichen Sprachgebrauch.

• Zeitstunde: Im Gegensatz zur Schulstunde ein Zeitrahmen, zu dem eine solche stattfinden kann. Hier wird angenommen, daß sich verschiedene Zeitstunden nicht überlappen, d.h. daß ein Objekt dadurch, daß es in Stunde a verfügbar ist, nicht a priori in Stunde b nicht zur Verfügung steht.
• Differenzierungsstunde: Unter differenziertem Unterricht soll hier eine Unterrichtseinheit verstanden werden, an der verschiedene Lehrer und Klassen gleichzeitig teilnehmen. So werden z.B. häufig die Schüler einer Jahrgangsstufe in zwei nach Geschlechtern getrennten Gruppen in Sport unterrichtet.
• Springstunde: Als Springstunde bezeichnet man eine Zeitstunde, zu der ein Objekt (Lehrer, Klasse) keinen Unterricht hat, vor der und nach der dieses aber beschäftigt ist. Insbesondere können diese auch für Lehrer-Klassen-Paare definiert werden.
• Relative Nebenbedingung: Eine Anforderung an eine Zuordnung, die durch eine andere Zuordnung beeinflußt wird. So kann z.B. eine Springstunde nur dann auftreten, wenn eine andere Stunde vorhanden ist, relativ zu der sie springt.
• Harte Bedingungen: Harte Nebenbedingungen sind solche, die unabdingbar sind, wie z.B. diejenige, daß keine Person zur selben Zeit an verschiedenen Orten sein kann. Analog sind weiche Nebenbedingungen erwünscht aber nicht notwendig. Eine Lösung, die die harten Nebenbedingungen erfüllt, heißt geeignet und die zugehörige Aufgabe das Such-Problem. Eine geeignete Lösung, die die weichen Nebenbedingungen bestmöglich erfüllt, heißt optimal und man spricht entsprechend vom Optimierungsproblem.
• Flexible Ressource: Eine flexible Ressource ist eine, die zu einem gewissen Grad und kontextabhängig ausgetauscht werden kann. So z.B. ist ein Klassenraum eine flexible Ressource, da zumeist in einen anderen Raum ausgewichen werden kann. Wird dieser aber explizit angefordert, so wird er zur statischen Ressource. Lehrer und Klassen treten zumeist als solche auf.