Themis: Lösungsmodell

Ereignisse in einem Stundenplan haben immer ein Zeitfenster, aber u.U. (noch) keinen Raum. Daraus ergeben sich für ein Ereignis die folgenden Möglichkeiten der Zuordnung:

1. Zeitfenster und Raum
2. Zeitfenster, aber keinen Raum
3. weder Zeitfenster noch Raum

Gibt es Ereignisse mit 2. oder 3., so ist der Plan unvollständig. Die Anzeige im Fenster "Ereignisse" kann auf Ereignisse mit Eigenschaft 3. eingeschränkt werden.

Die Gültigkeitsprüfung bezieht sich immer nur auf die im Plan vorhandenenDaten. Fehlt beispielsweise bei einem Ereignis die Raumzuordnung, werden die Zulässigkeitskriterien, die sich auf Räume beziehen, nicht geprüft. Insbesondere ist der leere Stundenplan gültig, aber unvollständig, sofern es im Informationsmodell Ereignisse gibt.

Gültige Pläne werden bezüglich der Optimierungskriterien bewertet. Dabei verteilt Themis Strafpunkte, wenn Konstellationen im Plan erkannt werden, die ungünstig erscheinen. In den meisten Fällen wird es so sein, dass aufgrund der Datenlage null Strafpunkte nicht erreichbar sind. Dennoch gilt: Weniger Strafpunkte = bessere Pläne.

Wird beispielsweise ein Zeitfenster verwendet, obwohl dieses Zeitfenster für den Dozenten als unerwünscht (gelb) gekennzeichnet ist, wird ein Strafpunkt zur Summe aller Strafpunkte hinzugefügt.

Es gibt mehrere Möglichkeiten, die Optimierungskriterien individuell anzupassen. Bei einigen Kriterien kann die Anzahl der Strafpunkte je Verstoß verändert werden. Dazu zählen die Strafpunkte für die Verwendung von Räumen und Zeitfenstern.

Die Gesamtanzahl der Strafpunkte ist eine gewichtete Summe der Strafpunkte der Einzelkriterien. In den Einstellungen können die Gewichte aller Kriterien individuell eingestellt werden. Insbesondere wird mit Gewicht 0 das entsprechende Kriterium ausgeschaltet.

Der Benutzer kann jedem Ereignis ein beliebiges Zeitfenster und einen beliebigen Raum zuordnen: alles ist möglich - unabhängig von Zulässigkeit und Bewertung.

Ereignisse ohne Raum und Zeitfenster werden im Fenster "Ereignisse" aufgelistet und können in den Plan gezogen werden. Ebenso wird per drag&drop das Zeitfenster eines bereits eingeplanten Ereignisses verändert. Über das Kontextmenü lässt sich die Raumzuordnung vornehmen.

Wird ein Ereignis zum Verschieben ausgewählt, unterstützt Themis den Benutzer durch Vorausberechnung von Gültigkeit und Planbewertung: Ein Zeitfenster erscheint grün (rot), wenn die Verlegung des Ereignisses in dieses Zeitfenster zu einem (un-)gültigen Plan führt. Ausserdem werden je Zeitfenster die Anzahl der Gültigkeitsverstöße (in roten Zeitfenstern) bzw. die Strafpunkte (in grünen Zeitfenstern) angezeigt. 

Für grüne Zeitfenster werden zusätzliche Rauminformationen angezeigt: Das Symbol "kein Raum" sagt aus, dass die Verlegung des Ereignisses in dieses Zeitfenster zwar einen gültigen Plan ergibt, aber dass in diesem Zeitfenster kein gültiger Raum für das Ereignis existiert. Das Symbol "Raumwechsel" bedeutet, dass ein gültiger Plan nur dadurch erreicht wird, dass der bereits zugeordnete Raum gewechselt wird. Diesen Raumwechsel macht Themis automatisch und wählt dabei den Raum mit der günstigsten Bewertung.

Themis verfügt über einen Algorithmus, der jeden gültigen Plan zu einem zulässigen Plan ergänzt, falls das kombinatorisch überhaupt möglich ist. Dabei wird der Ausgangsplan verändert. Insbesondere kann dieser Algorithmus auf dem leeren Plan starten und alle Ereignisse automatisch einplanen. Existiert kein zulässiger Plan oder wird der Algorithmus vom Benutzer abgebrochen, wird der Ausgangsplan nicht verändert (auch nicht teilweise).

Der Algorithmus ist aufrufbar, wenn folgende Vorbedingungen erfüllt sind:

• Der Ausgangsplan ist gültig, aber unvollständig.
• Die Daten im Informationsmodell sind konsistent.

Sind bei Aufruf des Algorithmus bereits Ereignisse im Plan vorhanden, werden die getroffenen Zuordnungen in jedem Fall beibehalten.

Achtung: Abhängig von den Daten kann es Konstellationen geben, so dass die bereits festgelegten Zuordnungen eine Vervollständigung eines Plans unmöglich machen, obwohl ein anderer zulässiger Plan existiert.

Module können im Informationsmodell als "zu verplanen" oder "nicht zu verplanen" gekennzeichnet werden. Alle Ereignisse von nicht zu verplanenden Modulen werden vom Algorithmus nicht eingeplant, es sei denn, sie sind bereits im Ausgangsplan vorhanden.

Themis verfügt über einen Optimierungsalgorithmus, der immer aufgerufen werden kann, wenn der Ausgangsplan vollständig ist. Der Algorithmus liefert auch nach Abbruch durch den Benutzer den besten bisher gefundenen Plan zurück. Wurde der Ausgangsplan durch den Algorithmus verbessert, erzeugt Themis einen neuen Ergebnisplan (der Ausgangsplan bleibt erhalten).

Der Algorithmus miniminiert zunächst die Anzahl der Gültigkeitsverstöße, bis ein gültiger Plan gefunden wurde, und sucht anschließend einen Plan mit minimalen Strafwerten. Ist der Ausgangsplan bereits gültig, fällt die erste Phase weg.

Jedes Projekt verfügt über eine Liste von Stundenplänen. Kopien vorhandener Pläne können der Liste hinzugefügt und dann verändert werden, so dass Zwischenstände erhalten bleiben. Der Benutzer kann jederzeit zu einem anderen Plan in der Liste wechseln.