Zeitpläne müssen in vielen unterschiedlichen Bereichen erstellt werden, z.B. in der Schulstundenplanung oder der Personaleinsatzplanung. Da es sehr mühsam ist, komplexe Zeitpläne wie Schulstundenpläne per Hand zu erstellen, werden die meisten Zeitpläne computerunterstützt generiert. Dazu wurde am Lehrstuhl in den vergangenen Jahren eine Software entwickelt, die es ermöglicht, die Planung unter zu Hilfenahme verschiedener Optimierungalgorithmen durchzuführen. Diese Version der Zeitplanungssoftware wurde aus einer auf genetischen Algorithmen basierenden Version weiterentwickelt, wobei sich zeigte, dass einige Erweiterungen wegen der notwendigen Kompatibilität zur Grundversion nicht optimal implementieren ließen.Erlangen Advanced Time Tabling Software EATTS ist die innovative Entwicklungs- und Produktionsumgebung zur Erstellung optimierter Zeitplanungen.
Ressourcen
Zeitplanungsprobleme treten in der Praxis in verschiedenen Formen auf: Schichtpläne, Fertigungspläne, Stundenpläne u.v.a. Allen gemeinsam ist, dass bestimmte Ereignisse unter
Berücksichtigung von Randbedingungen möglichst optimal geplant werden müssen. Das Ergebnis der Planung ist dann ein Zeitplan. Im Beispiel der Schulplanerstellung wären die Ereignisse Schulstunden, denen Ressourcen wie Lehrer, Klassen und Räume zugeordnet werden müssen. Die Ressourcen werden in Typen unterteilt. Für jeden dieser Typen können beliebig viele Attribute vom Benutzer definiert werden.
Eine Zeitplanerstellung beginnt typischerweise mit der Erfassung der einzuplanenden Ressourcen. Diese kann durch Import eines Datenbestandes oder manuelle Erfassung geschehen.
Ergebnisse
Als Ergebnisse der Planungsalgorithmen werden Zeitpläne erstellt. Diese können in verschiedenen Formaten gespeichert und angezeigt werden. So ist es z. B. möglich, verschiedene Sichten auf einen Plan zu erzeugen.
Typisch ist die Anbindung über einen Browser, d.h. den einzelnen Benutzern werden entsprechend ihren Privilegien die Sichten und Funktionen zur Verfügung gestellt.
Randbedingungen
Die Beschreibung von Randbedingungen ist meist viel komplexer als die von Ressourcen und Ereignissen.
Zum Einen müssen die Randbedingungen exakt formuliert werden, zum Anderen darf die Übersichtlichkeit nicht verloren gehen, um z. B. Widersprüche oder Lücken entdecken zu können, die ja leider nicht automatisch gefunden werden können. Randbedingungen kommen in vielen Varianten vor, weshalb eine flexible Spezifikation notwendig ist. In der Spezifikation kann auf Ressourcen und/oder deren Attribute, die ja vom Benutzer definiert werden, zugegriffen werden. Abhängig vom Typ dieser Variablen, unter anderem Integer, Gleitkomma und Zeichenketten, stehen Verknüpfungs- und Vergleichsoperatoren zur Verfügung, um die Bedingungen zu formulieren. Zusätzlich werden die Parameter der Kostenfunktion gewählt, um bei einer Verletzung der Randbedingung die entsprechenden Strafpunkte zu berechnen.
Eine Besonderheit unserer Software ist, dass Randbedingungen nicht nur als "unbedingt einzuhalten (hard)" oder "nach Möglichkeit einzuhalten (soft)" klassifiziert werden können, sondern auch als "darf im Ausnahmefall verletzt werden (soft hard)". Somit kann die Verletzung bestimmter Randbedingungen im Ausnahmefall erlaubt werden. So kann beispielsweise flexibel auf den Ausfall von Ressourcen reagiert werden, indem ein neuer Zeitplan erstellt wird, der möglichst wenig Abweichungen vom bisherigen Plan hat, z. B. muss ja nicht der gesamte Stundenplan aller Schüler neu erstellt werden, nur weil ein Lehrer krank geworden ist, oder ein Klassenraum wegen eines Rohrbruchs nicht benutzbar ist. In diesen Fällen soll nur ein Vertretungsplan erstellt werden.
Algorithmen
Herzstück der Planung sind die verwendeten Algorithmen. Abhängig von der Natur der Randbedingungen und den gewünschten Eigenschaften kann aus einer Vielzahl von bereits implementierten Algorithmen ausgewählt werden: Genetische Algorithmen - Evolutionäre Algorithmen - Branch-and-Bound - Tabu Search - Simulated Annealing - Graphenfärbung - Soft Computing - Schwarm Intelligenz.
Für den Einstieg stehen vorkonfigurierte Algorithmen zur Verfügung, der fortgeschrittene Benutzer kann aber die Parameter der Algorithmen an seine Bedürfnisse anpassen oder neue Algorithmen implementieren. Alle diese Algorithmen können in Experimenten beliebig zu Berechnungssequenzen kombiniert werden. Die Konfiguration eines Experiments kann abgespeichert werden und z. B. als Vorlage für ein neues Experiment dienen oder nochmals ausgeführt werden.
Ausführung von Experimenten
Die Algorithmen werden entweder auf einem dedizierten Server ausgeführt und bei Bedarf über das TCP/IP-Protokoll auf weitere Rechner verteilt. Die Abbildung zeigt den Dialog zur Auswahl und zum Start der Experimente und die Übersicht der laufenden Experimente. Der Browser verbindet sich in regelmäßigen Abständen automatisch mit dem Server und erhält von diesem den aktuellen Stand der Berechnung. Dieser Statusinformationen beinhalten unter anderem die Kosten des bisher besten gefundenen Plans sowie eine Abschätzung für die verbleibende Berechnungszeit. Nach Beendigung der Berechnung werden die Ergebnisse gespeichert und die Dateien, die zur Visualisierung der Pläne nötig sind erstellt. Der Planer kann nun entscheiden, ob die Qualität der gefundenen Lösung ausreichend ist, oder ob er auf ihrer Basis weitere Optimierungsläufe starten will.
Ergebnisse
Als Ergebnisse der Planungsalgorithmen werden Zeitpläne erstellt. Diese können in verschiedenen Formaten gespeichert und angezeigt werden. So ist es z.B. möglich verschiedene Sichten auf den Plan zu erzeugen.
Typisch ist die Anbindung über einen Browser, d.h. den einzelnen Benutzern werden entsprechend ihren Privilegien die Sichten und Funktionen zur Verfügung gestellt.
Zusammenfassung
Die Software ist in Java implementiert und damit plattform-übergreifend verfügbar, insbesondere für die Betriebssysteme Windows und Linux.
Für den Betrieb von EATTS werden folgende frei verfügbare kostenlose Software-Produkte benötigt:
Optional kann ein dedizierter EATTS-Server konfiguriert werden. Dazu wird benötigt:
Java Laufzeitumgebung (JRE Java Runtime Environment) (min v5.0),
über TCP/IP Netzwerk erreichbare Rechner zur verteilten Berechnung (optional).
Im Jahr 2008 wurde die Struktur der Algorithmen optimiert um die nebenläufige Berechnung zu beschleunigen. Dies soll in Zukunft auf Rechner mit Multi-Core-Prozessoren ausgedehnt werden.
Da es sich die Installation der Software durch die potentiellen Nutzer als zu komplex herausgestellt hat, wurde eine abgespeckte Version implementiert, die keine Datenbank mehr benötigt, sondern deren Datenhaltung und Austausch auf XML-Dokumenten basiert. Zusätzlich wird eine Variante angeboten, bei der die Nutzer ihre Experimente auf einem an der Universität Erlangen installierten Server rechnen lassen können.
Die Oberfläche der Software wurde komplett als web-basierte Anwendung reimplementiert.
Auf der CeBIT 2009 wurde die neue Version der Software vorgestellt, die jetzt EATTS Erlangen Advanced Time tabling System heißt.