[zurück zum Inhalt]
 

4. Die Stundenplan-Algorithmen


In diesem Abschnitt finden Sie Informationen zu den, in der Schulverwaltung verwendeten Stundenplanalgorithmen.
Spezielle Informationen zur Version 1.2BETA2 befinden sich im Abschnitt 2 dieser Dokumentation.

4.1. Allgemeines

- Im Folgenden stelle ich die Algorithmen mit ihren Vor- und Nachteilen  im einzelnen vor. Dabei gehe ich von meinen eigenen Erfahrungswerten aus. Als Grundlage dienten dabei 5 Klassen.
- Die genaue Arbeitsweise der Algorithmen werde ich in der nächsten Zeit auf meine Homepage stellen.
- Bei den randomisierten Algorithmen habe ich die, von Borland implementierte Funktion, übernommen. Leider liefert diese zum einen nicht besonders gute Zufallswerte und zum anderen gibt sie nach jedem Start des Programms genau dieselben Werte, wie schon nach dem letzten Programmstart aus. Kurioser Weise sorgt dieses Verhalten für teilweise erstaunlich gute - und sogar reproduzierbare - Ergebnisse (auf meinen Testdaten wohlgemerkt).
Möchten Sie ein anderes Ergebnis erhalten, sollten Sie die Algorithmen direkt nacheinander starten und dabei die Schulverwaltung nicht beenden.

4.2. Backtracking-Algorithmus

Vorteile:
+ schnell
+ relativ gute Ergebnisse
+ übernimmt bereits vorgegebene Dauertermine
Nachteile:
- liefert kein optimales Ergebnis
- Freistunden können im Ergebnis vorkommen

Beschreibung:
Der Backtracking-Algorithmus geht "Greedy" vor, d.h. er verteilt nacheinander für jede Klasse die jeweiligen Stunden, genau in der Reihenfolge, wie sie im Curriculum angegeben wurden.

4.3. Randomisierter-Tetris-Algorithmus

Vorteile:
+ relativ gute Ergebnisse (teilweise besser als Backtracking)
+ schnell
+ übernimmt bereits vorgegebene Dauertermine
Nachteile:
- (zu diesem Zeitpunkt) keine Beachtung von Doppelstunden, bzw. das mehrfache Vorkommen von Terminen an einem Tag bleibt unberücksichtigt
- gibt in einigen Fällen keine Lösung aus (ist aber endlich)

Beschreibung:
Dieser Algorithmus sollte einmal zur Probe gestartet werden. Entweder ist das Ergebnis gut oder man kann es verwerfen. Sollte der Algorithmus keine Lösung ausgeben, sollten Sie ihn erneut starten.
Insbesondere dieser Algorithmus hat, was die Qualität der Ausgabe betrifft, noch Verbesserungspotential.

4.4. Brettspiel-Algorithmus (ohne Bedingungen)

Vorteile:
+ Geschwindigkeit liegt im Mittelfeld
+ Gute Ergebnisse
Nachteile:
- liefert Lücken und berücksichtigt keine "Doppelstunden"
- berücksichtigt keine vorgegebenen Termine
- es gibt Situationen, in denen der Algorithmus nicht endlich ist

Beschreibung:
Die Brettspielalgorithmen gehen ungefähr so vor, wie es der "Mensch" machen würde: er "sucht" einfach eine Lösung.
Bei dieser Variante gelten keine Bedingungen (sie sollte daher nur dann eingesetzt werden, wenn Letztere nicht benötigt werden).
Da diese Algorithmen nicht besonders effizient von mir implementiert wurden (aus Zeitmangel), haben die Brettspielalgorithmen eine ziemlich hohe Laufzeit. So benötigt dieser Algorithmus auf einem Athlon 500 ca. 5 Sekunden bei 5 Klassen.
Ein weiteres Problem ist die, in einigen Fällen "unendlich" lange Laufzeit. Aus diesem Grund ist es jederzeit möglich, den Algorithmus mit einem Klick auf "Abbrechen" anzuhalten. Der aktuelle "Berechnungstand" wird dann ausgegeben.

4.5. Brettspiel-Algorithmus (keine Freistunden)

Vorteile:
+ sehr gute Ergebnisse
Nachteile:
- (zur Zeit) relativ lange Laufzeit
- keine Berücksichtigung von vorgegebenen Terminen
- keine Beachtung von Doppelstunden
- es gibt Situationen, in denen der Algorithmus nicht endlich ist

Beschreibung:
Dieser Algorithmus arbeitet analog zu 4.4., nur dass nun keine Freistunden mehr erlaubt werden. Dies erhöht die Laufzeit noch einmal erheblich. Auf einem Athlon 500 benötigt der Algorithmus bei 5 Klassen ca. 30 Sekunden. Ich möchte betonen, dass diese Laufzeit zu 50% von meiner schlechten Implementierung abhängt - dort ist also noch Verbesserungspotential vorhanden.
Erstaunlicherweise liefert dieser Algorithmus, obwohl er nicht auf irgendwelche Doppelstunden-Konstellationen achtet, Stundenpläne, die dies berücksichtigen (dies gilt für meine Test-Daten - wie dies in der Praxis aussieht, kann ich leider nicht sagen - hier wäre ich für Informationen dankbar).

4.6. Brettspiel-Algorithmus (alle Bedingungen)

Vorteile:
+ sehr gute Ergebnisse
+ achtet auch auf Doppelstunden
Nachteile:
- (zur Zeit) relativ monströse Laufzeit
- keine Berücksichtigung von vorgegebenen Terminen
- es gibt Situationen, in denen der Algorithmus nicht endlich ist

Beschreibung:
Der Algorithmus arbeitet analog zu 4.5., mit dem Unteschied, dass nun auch auf Doppelstunden geachtet wird. Dadurch erhöht sich die Laufzeit noch einmal: Auf einem Athlon 500 bei 5 Klassen benötigte der Algorithmus im günstigsten Fall 5 Minuten. Allerdings sollte ich nicht verschweigen, dass das Ergebnis die anderen
Algorithmen geschlagen hat.

4.7. Bemerkungen zu den Brettspielalgorithmen:

Während die Berechnung der Stundenpläne läuft, werden Informationen angezeigt. Auch wenn hier scheinbar für alle Klassen angezeigt wird, dass die noch einzuordnende Fächeranzahl 0 ist, so stimmt dies nicht immer. Die Berechnungen sind erst beendet, wenn dies ausdrücklich angezeigt wird, bzw. sich das Fenster automatisch schließt.

4.8. Schlussbemerkung

Falls Sie andere Stundenplan-Algorithmen kennen, greife ich diese gerne auf (sofern sie nicht durch ein Patent o.ä. geschützt sind). Die Arbeitsweise meiner Algorithmen werde ich in der nächsten Zeit auf meine Homepage stellen.
 

[zurück zum Inhalt]