Next: Die interaktive Unterstützung Up: Implementierung des Rahmenprogrammes Previous: Datenstrukturen

Funktionalität und Implementierung des Editors

Objekttypen- und Objekteditor

Die beiden Abbildungen zeigen den Objekttypen- und den Objekteditor. Der Typeneditor dient in erster Linie dazu, den Objekteditor zu konfigurieren, indem eingegeben werden kann, welche Bezeichnungen im Objekteditor auftreten sollen bzw. wie die entsprechenden Felder zu interpretieren sind. Als einzige wirkliche Information wird hier festgelegt, welche Objekttypen als Zeiteinheiten zu verstehen sind.
Der Objekteditor erlaubt das Erzeugen neuer Objekte und das Zuordnen der jeweiligen Attribute, wobei diese im Mengensystem dazu verwandt werden, automatisch Mengen zu generieren (s. Abschnitt 8.2.2). Der Übersichtlichkeit halber werden die Objekte nach Typen sortiert angezeigt.

Mengeneditor

 

Der Mengeneditor ermöglicht es, Mengen zu erstellen, zu löschen und Teil bzw. Übermengenbeziehungen herzustellen. Das Mengensystem, das azyklisch, aber nicht im ungerichteten Sinne kreisfrei (i.e. kein Wald) ist, wird durch die CTree Struktur von Visual C++ dargestellt, indem jede Menge mit der Zahl ihrer Übermengen vielen Repräsentanten assoziiert wird. Entsprechend kann jede Menge sooft dargestellt werden, wie es Pfade von der (virtuellen) Wurzel des Mengensystems zu der jeweiligen Menge gibt. In der praktischen Anwendung ist aber nicht damit zu rechnen, daß ein Pfad eine Länge größer als 4 annimmt. Die Unterscheidung zwischen Teilmengen und Elementmengen wirkt sich nur auf die Ansichten aus. Einzelne Objekte können als unsichtbar markiert werden. Dies führt dazu, daß sie auf der obersten Ebene der Hierarchie des Mengeneditors nicht mehr angezeigt werden und als Ausgangsmenge für Ansichten (s. Unterkapitel 8.2.4) nicht mehr zur Verfügung stehen. Hierbei wird darauf geachtet, daß dennoch für jede Menge eine Repräsentation im Mengeneditor existiert, was wegen der Möglichkeit, daß die Übermenge über die dieser Zugriff erfolgt, gelöscht werden kann, relativ kompliziert ist. Nach Abschluß der Editierarbeiten findet eine Überprüfung dahingehend statt, daß die gewählten Relationen azyklisch sind.
Der Mengeneditor war von der Implementierung her besonders aufwendig, vor allem, was die unsichtbaren Mengen angeht. Fügt der Benutzer z.B. einen Zyklus ein (vor dem er erst bei Beenden des Editors gewarnt wird) und macht dann alle Mengen, die zu diesem Zyklus gehören unsichtbar, so besitzt jeder der Knoten einen Vorgänger, so daß dies zunächst erlaubt ist. Auf diesem Wege können aber alle Mengen des Zyklus unsichtbar werden. Dieses Problem wurde auf dem Wege behoben, daß bei Finden eines Zykluses automatisch alle beteiligten Mengen wieder sichtbar werden.

Bewertungs- und Zeiteditor

  Der Bewertungseditor dient zur Eingabe absoluter und relativer Parameter der Zielfunktion. Im oberen Kästchen in der Mitte stehen die absoluten Parameter. Einstellungen hier wirken sich auf die im rechten Listenfeld selektierten Objekte aus. Im unteren Kästchen werden der berechnete und der eingestellte Wert der Relation zwischen dem im linken Listenfeld und dem im rechten Listenfeld selektierten Objekt angezeigt. Hierbei dominiert stets der eingestellte Wert den berechneten Wert vollständig, es sei denn, es wurde egal ausgewählt bzw. bei den absoluten Parametern das entsprechende Kästchen aktiviert. Die berechneten Werte der absoluten Parameter ergeben sich als Mittelwert der entsprechenden Einstellungen der Obermengen, wobei durch Auswertung in topologischer Reihenfolge, was aufgrund der Azyklität des Mengensystems möglich ist, die Obermengen stets vor der Bestimmung dieses Parameters ausgewertet werden können. Zur Propagierung der relativen Parameter siehe Abschnitt 8.4.2.

Der Zeiteditor erlaubt es, die relative Anordnung der Zeiteinheiten zueinander anzugeben und festzulegen, welche Stunden am selben Tag bzw. zwischen zwei Pausen stattfinden. Diese Anordnung wird für die relativen Nebenbedingungen, insbesondere für die Berechnung der Springstundenzahl, benötigt. Alternativ wäre es möglich, die im Bewertungseditor vorgebbaren, aber in der momentanen Implementierung ignorierten Relationen zwischen zwei Zeitobjekten auszuwerten, was zwar eine größere Flexibilität, aber mit |Zeitstundenzahl| einzugebenden Relationen eine große Unübersichtlichkeit mit sich bringen würde. [CK95b] führen ein dem Zeiteditor äquivalentes Konstrukt in ihrer Eingabesprache auf, was daran liegt, daß sie ebenfalls Zeitstunden als Objekte betrachten.

Ansichten

  Die völlige Abwendung von festliegenden Entitäten wie Schülern und Lehrern erfordert eine flexiblere Art der Darstellung der Datensätze. Hierzu wurde eine Tabelle mit einstellbaren Kategorien geschaffen, die es erlaubt, nahezu jede beliebige in Timetabling-Programmen übliche Ausgabeform zu wählen. Insbesondere sind - eine geeignete Wahl im Mengeneditor vorausgesetzt - auch die Outline Darstellungen nach [Hil81] möglich. Die vollständige Übertragung dieses Schemas auf die Druckausgabe erlaubt zugleich, nun wieder im Schulkontext interpretiert, das automatische Erstellen von Klassen-, Raum-, Lehrer- und sämtlichen Übersichtsplänen.
Um eine erträgliche Geschwindigkeit des Bildaufbaus bei Verschiebungen zu gewährleisten, wird diese Tabelle stets vollständig im Speicher gehalten, wobei allerdings zu aufwendige Tabellen - der Benutzer kann de facto eine Tabelle mit |Anzahl der Objekte Feldern anfordern - nicht angefertigt werden. In die Tabelle werden diejenigen Felder der jeweiligen Gruppe bzw. Stunde bevorzugt eingetragen, die sich nicht aus dem Tabellenkontext ergeben. Die anderen, deren Namen zumeist ohnehin in den Tabellenüberschriften stehen, werden nur angegeben, sofern noch Platz zur Verfügung steht; diese werden bei Ausschneide-Operationen entfernt (s. dort). Die übernächste Darstellung zeigt einen Ausschnitt aus einer solchen Tabelle.

Die erste Abbildung zeigt den Dialog, der die Auswahl der Tabellenformen ermöglicht. Sowohl horizontal, als auch vertikal ist ein bis zu dreistufiger Hierarchieaufbau möglich. Im Feld Auswahl kann die Anzeige auf bestimmte Datensätze beschränkt werden, wobei die Auswahlbox angibt, daß die Teilmengen der angegebenen Menge nach und nach als Grundlage verwandt werden sollen. Bei der Bildschirmdarstellung kann mittels + und -\ zwischen verschiedenen Teilmengenkonfigurationen gewählt werden; sämtliche möglichen Kombinationen aus den drei Auswahl-Feldern werden durchlaufen. Beim Druck werden automatisch alle Konfigurationen ausgegeben, wobei zwischen zweien ein Seitenvorschub erfolgt und bei übergroßen Tabellen diese korrekt paginiert auf mehrere Seiten verteilt werden.

Es gibt zwei getrennte, farblich voneinander abgehobene Editoren für Vorgaben und Ergebnisse (vgl. Abschnitt 5.3.2). Beim Wechsel vom einen zum anderen wird die jeweils selektierte Position in der Tabelle beibehalten, so daß ein leichter Vergleich von Vorgaben und Zustand möglich ist. Um Tabellen dieser Größe verwalten zu können, mußte eine eigene Bildlauf-Funktion entwickelt werden, da der von Windows für ein Fenster zur Verfügung gestellte Speicher nicht ausreichte. Diese eigene Funktion erlaubt es zudem vorzugeben, daß mit jedem Schritt um ein ganzes Feld weitergesprungen wird bzw. bei einem Klick auf die Bildlaufleiste um eine ganzzahlige Anzahl von Feldern. Die Implementierung erwies sich als recht aufwendig, da die Feldbegrenzungen von der jeweiligen Hierarchieebene abhängen. In Anhang A findet sich ein Beispiel für die Druckausgabe.

Selektionen werden durch Anklicken eines Tabellenfeldes vorgenommen, betreffen aber stets die gewählte Gruppe bzw. Stunde, so daß alle Repräsentationen dieser Gruppe (Stunde) in der Tabelle markiert werden. Klickt man unterhalb der Gruppen in ein Tabellenkästchen, so wird dieses ganz markiert. Dies dient z.B. der Vorbereitung einer Einfügeoperation. Beim Anzeigen von Stunden wird zudem auf auftretende Widersprüche hingewiesen. Kollidierende Stunden werden mit einem roten Rahmen versehen. Zudem wird auf Basis der den Stunden zugrundeliegenden Gruppen versucht, eine Ressourcen-Optimierung (s. Abschnitt 8.4.3) durchzuführen. Stunden, bei denen dies nichts hilft, werden im Plan durchgestrichen. Bei nicht durchgestrichenen Mengen kann durch Selektion und anschließendes Aktivieren des Befehls Zeitstunde Optimieren\ zu dem bestimmten Matching übergegangen werden. Des weiteren können Stunden an einer Position festgehalten werden, was es erlaubt, einen gegebenen Plan zu ergänzen bzw. Abwesenheitszeiten unter Umgehung des Bewertungssystems direkt einzugeben.
An dieser Stelle tritt ein semantisches Problem auf. Im Rahmen von Zeitslot Optimieren kann jede Stunde mit anderen Ressourcen versehen werden, je nachdem wie es die zugehörige Gruppe vorgibt. Hierbei werden sämtliche Änderungen, die der Benutzer von Hand an dieser Gruppe vorgenommen hat, gelöscht. Dem Anwender steht es aber durchaus frei, die Stunde soweit zu verändern, daß sie zu einer anderen Gruppe zu gehören scheint, so daß die Gefahr besteht, daß die Optimierung der Zeitstunde Verwirrung stiftet, da scheinbar Stunden die Gruppen, auf denen sie basieren, wechseln. Es tritt also die Frage auf, welche Eigenschaften charakteristisch für die Gruppenzugehörigkeit einer Stunde sind.

Gruppen- und Stundeneditor

Die beiden dargestellten Dialoge ermöglichen das Editieren von Gruppen bzw. Stunden. Es besteht die Möglichkeit, diese nochmals in Untermengen aufzugliedern, da z.B. bei einer Differenzierungsstunde, die Mathematik und Schwimmen beinhaltet, die Bevorzugung von Schwimmhallen zum Schwimmen keine Auswirkungen auf die Raumwahl für die Mathematikstunden haben sollte. Diese Trennung wird zur Zeit noch nicht unterstützt; derselbe Effekt kann aber erzielt werden, indem man die speziellen Räume unter einer Menge Fachräume zusammenfaßt und generell die Verwendung von Fachräumen empfiehlt. Der Zwang, zum Schwimmen die entsprechende Sportstätte zu verwenden, kann dann über die Konstruktion des Mengensystems umgesetzt werden.

Löschen, Kopierfunktionen und Zurücknahmefunktion

  Das Programm erlaubt es, Einträge von einer Position einer Tabelle in eine andere zu kopieren, wobei die jeweiligen Gruppen kontextsensitiv angepaßt werden, indem die entsprechenden Mengen, die zum Einfügen der Gruppe an der Anfangsposition geführt haben, entfernt werden und die für das Erscheinen an der neuen Position erforderlichen Mengen hinzugefügt werden. Hierbei werden die Mengen durch etwaige gemeinsame Teilmengen ersetzt, so daß z.B. statt Dienstag und 4. Stunde Dienstag 4.Stunde eingesetzt wird. Die Bestimmung der minimalen Menge von Mengen, die zur Einfügung an dieser Stelle der Tabelle notwendig ist, entspricht dem Set-Cover Problem und ist daher -vollständig. Auch bei kleinen Objektzahlen ließe sich der Aufwand hierfür an dieser Stelle nicht rechtfertigen, da noch nicht einmal gesichert ist, daß der Benutzer die Auswahl verstehen bzw. gutheißen würde. Daher wurde so vorgegangen, daß jede Menge der Reihe nach mit allen nachfolgenden Mengen verglichen wird; wird eine gemeinsame Teilmenge gefunden, so wird die erste durch diese ersetzt und die zweite gelöscht.

Angenommen, es gäbe am Ende noch zwei Mengen, die eine gemeinsame Teilmenge haben, dann betrachte den Zeitpunkt, zu dem die erste Menge mit den folgenden verglichen wurde. Die zweite Menge ist als gemeinsames Element im Schnitt einer oder mehrerer anderer Mengen entstanden. Da auf dieser Ebene nur Teilmengen betrachtet werden, muß das Element, das später die Vereinigung der beiden Mengen erlaubt also bereits Element jeder dieser Ausgangsmengen sein. Damit wären diese aber alle bereits zum betrachteten Zeitpunkt entfernt worden.
Der Benutzer sollte allerdings während Kopiervorgängen die Tabellenform nicht wechseln, da somit natürlich die hier eingeführte Logik durchbrochen würde. Es besteht die Möglichkeit, die erzeugten Stunden von Hand nachzubessern.

Die Kopierfunktion kann durch Hinzunahme der Zwischenablage in ihrem Funktionsumfang erweitert werden.
Ist die Zwischenablage ausgeblendet, so wird beim Kopieren oder Ausschneiden der jeweils oberste Eintrag mit den neuen Daten überschrieben, so daß sich das Ganze wie eine herkömmliche Kopierfunktion verhält. Ist sie aber eingeblendet, so wird das Kopierte (Ausgeschnittene) der Zwischenablage hinzugefügt und kann vom Benutzer in beliebiger Reihenfolge entnommen werden, so daß dem Benutzer eine nur durch den Speicherplatz begrenzte Zahl verschiedener Zwischenspeicher zur Verfügung steht. Das Einfügen kann als das Einsetzen einer leeren Gruppe interpretiert werden.

Die Operationen Einfügen, Löschen, Ausschneiden, Kopieren und Einsetzen können bis zu 30 Schritte rückgängig gemacht und wiederhergestellt werden, wobei dies ein willkürlich gewählter Wert ist. Hierbei können alle rückgängig gemachten Schritte so lange wiederhergestellt werden, bis der Benutzer eine neue Operation vornimmt. Dem Ganzen wurde das folgende System zugrundegelegt:

Sämtliche Aktionen werden als das Bewegen von Objekten entlang der dargestellten Pfeile interpretiert, wobei die Trennung zwischen Precreate Buffer und Delete Buffer nicht unbedingt notwendig ist, da die Objekte durch einen eindeutigen Bezeichner unterschieden werden können. Ausschneiden und ähnliche zerlegbare Operationen werden z.B. als Kopieren und Löschen interpretiert, so daß der Benutzer ggf. einmal häufiger die Wiederherstellen-Funktion aufrufen muß, um das gewünschte Ergebnis zu erzielen. Liegt die letzte Operation, bei der eine Stunde oder Gruppe benötigt wurde, mehr als 30 Schritte zurück, wird das entsprechende Objekt gelöscht. Wird eine Stunde aus den Voraussetzungen gelöscht, so werden automatisch alle Stunden im Stundenplan gelöscht, die mit dieser im Zusammenhang stehen. Ein Rückgängigmachen dieser Auswirkung ist z.Zt. nicht möglich, da dies für Stunden und Gruppen getrennt ginge und sich die entsprechenden Stunden somit auf nichtexistierende Anforderungen beziehen würden.

---

Next: Die interaktive Unterstützung Up: Implementierung des Rahmenprogrammes Previous: Datenstrukturen

(c) Martin Loehnertz 1999