|
In
vielen Bereichen des täglichen Lebens steht der Mensch vor der Aufgabe,
mit möglichst geringem Aufwand möglichst hohen Nutzen zu erzielen.
Er wird also mit Problemen konfrontiert, für die er die bestmöglichen
Lösungen sucht. Als besonders schwierig stellt sich immer wieder
die kostengünstigste Verteilung von Ressourcen im Bereich Organisation
und Planung heraus. Ein spezielles Problem aus diesem Bereich ist
das Stundenplan-Problem oder das timetabling, welches
die zeitliche Anordnung einer Menge von Aktivitäten und Ressourcen
unter bestimmten Nebenbedingungen umfaßt.
Viele
Bildungseinrichtungen beschäftigen Jahr für Jahr eine Anzahl
von Lehrkräften mit der Erstellung von Stundenplänen. Die dabei
erzielten Ergebnisse kommen zumeist unter beträchtlichem Zeitaufwand
zu stande und entsprechen selten den Vorstellungen der Betroffenen.
Zur Auflösung dieses Mißverhältnisses können
spezielle Optimierungs-Programme einen wertvollen Beitrag leisten.
Die
hier dargestellte Software ist zwar im Rahmen einer umfangreichen
Studien-Arbeit entstanden. (Dort ist auch
nachzulesen, was das alles mit evolutionärer Programmierung
zu tun hat.) Ein hohes Maß an Praxis-Tauglichkeit war
jedoch trotzdem ein wichtiger Bestandteil der Zielstellung.
Szenarien
Grau ist alle Theorie. Im folgenden werden daher einige reale
Szenarien von Unterrichts-Formen und -Situationen dargestellt,
die durch das Beschreibungs-Modell der Software erfaßt werden.
1.
Lehrer Leibnitz gibt pro Woche drei Stunden Unterricht in Mathematik
bei der Klasse 10b. Keine der Stunden darf am selben Tag stattfinden.
2. Lehrer Goethe gibt pro Woche drei Stunden Unterricht
in Deutsch bei der Klasse 10b. Eine dieser Stunden findet Dienstags
in der ersten Stunde im Raum 001 statt.
3. Lehrer Einstein unterrichtet die Klasse 10b in Physik.
Von den drei Stunden pro Woche, die alle im Physikraum stattfinden
müssen, folgen zwei direkt aufeinander.
4. Aufgrund der niedrigen Klassenstärken werden die Klassen
2a und 2b für den Werken-Unterricht bei einem Lehrer zusammengelegt.
Dieser Lehrer steht nur Dienstags bis Freitags zur Verfügung.
5. Ab der 7. Klasse müssen alle Schüler eine weitere Fremdsprache
wählen. Es wird Einführungs-Unterricht in Spanisch, Französisch
und Suaheli angeboten. In einer Stunde pro Woche teilen sich die
drei 7. Klassen entsprechend der Wahl der einzelnen Schüler auf
die drei Sprach-Stunden auf. Die drei Stunden finden alle zur
selben Zeit und in den Räumen 001, 002 und 003 statt.
6. In den Sportstunden der Klasse 10a wird eine Aufteilung
in Jungen und Mädchen vorgenommen. Je ein Sportlehrer ist für
einen Teil verantwortlich. Der Unterricht findet in der Sporthalle
statt. Die Klasse 7a hingegen hat ihren Sportunterricht nur bei
einem Lehrer in der selben Sporthalle.
7. Wenn es das Fach zuläßt, finden alle Stunden der Klasse
8a in einem bestimmten Raum statt - dem Klassenraum.
8. Für alle Klassen soll realisiert werden, daß die Schule
Montags und Freitags möglichst früh zu Ende ist.
9. Die Schulleitung weist jedem Lehrer eine Bereitschaftsstunde
zu, so daß stets, wenn möglich, ein Lehrer zur Verfügung steht.
10. Die Musikstunden, die Lehrer Mozart bei der Klasse
6a gibt, dürfen frühestens in der 5. Stunde stattfinden - eine
davon unbedingt am Montag.
11. Lehrer und Klassen haben so wenig Freistunden wie möglich.
12. Die Stunden einer jeden Klasse sind möglichst gleichmäßig
auf die Unterrichtstage verteilt. Gleiches gilt für Lehrer.
13. Die 8. Klassen sollten möglichst nicht Physik und Chemie
an einem Tag haben.
14. Die 8. bis 10. Klassen haben stets bei zwei Sport-Lehrern
Unterricht (Jungs und Mädchen getrennt), während alle jüngeren
Klassenstufen bei nur einem Lehrer haben. In letzterem Fall wird
die Turnhalle geteilt und zwei Klassen haben gleichzeitig Sport.
Stammdaten-Verwaltung
- Fächer,
Lehrer, Klassen - wie üblich
- Räume:
Reservierung für bestimmte Fächer und Definition von
Klassenräumen ist möglich
- Kurse
werden unterstützt (!)
- Es
sind maximal 12 Stunden + optional eine Nullte Stunde pro Tag
verfügbar.
- Maximal
7 Tage pro Woche können gewählt werden.
(Aber wer brauch schon mehr als 5 ?)
Folgende
Nebenbedingungen
lassen
sich festlegen
- Zeit-Restriktionen
Für jeden Lehrer, jede Klasse und jeden Raum können
beliebige Zeiten reserviert bzw. gesperrt werden.
- Raum-Pre-Sheduling
Unterrichts-Stunden können auf bestimmte Räume festgelegt
werden - speziell wird die Definition von Klassenräumen
unterstützt.
- Zeit-Pre-Sheduling
Unterrichts-Stunden können auf bestimmte Zeiten festgelegt
werden. Möglich ist die Vorgabe einer exakten Zeit (also
Tag + Stunde) oder eines Zeit-Bereiches.
- Mehrfach-Stunden
... werden unterstützt (Doppelstunde, Dreifachstunde,
...)
- Fach-Restriktionen
Fach-gleiche Stunden oder bestimmte Fächer-Kombinationen
einer Klasse können auf verschiedene Tage der Woche verteilen
werden.
Automatische
Plan-Erstellung
und Optimierungs-Ziele
- Einhaltung/
Beachtung aller definierten Nebenbedingungen
- Freistunden
... sind zeitlich zusammenhängende unbelegte Unterrichts-Zeiten
eines Tages, die von belegten Stunden eingeschlossen sind -
häufig das schwierigste Problem bei der Plan-Erstellung.
Das Programm nimmt eine automatische Minimierung der Freistunden
für Klassen und Lehrer vor.
- Stundenverteilung
Sowohl für Klassen, als auch für Lehrer, wird eine homogene
Verteilung der Stunden einer Woche auf die einzelnen Tage angestrebt.
- Trennungs-Fehler
... ergeben sich, wenn Fach-Restriktionen (siehe Nebenbedingungen)
nicht eingehalten werden können. Das Programm minimiert
Trennungs-Fehler.
- Die
Entscheidung, welche der Optimierung-Ziele verfolgt werden,
kann durch den Nutzer selbst bestimmt werden. Standardmäßig
bietet das Programm jedoch einen "Schritt-für-Schritt-Ablauf"
an, der sich in der Praxis bewährt hat.
Mauelle
Planerstellung
- Die
Software stellt ein komfortables Modul zur Verfügung, welches
die manuelle Veränderung eines Planes ermöglicht (siehe
ScreenShot).
- Soll
eine Stunde an eine andere Zeit verschoben werden, werden automatisch
alle möglichen Austausch-Stunden angeboten.
- Für
eine Freistunde lassen sich automatisch alle in Frage kommenden
Stunden ermitteln.
- Per
Maus lassen sich Stunden in dem Plan verschieben. Ist eine solche
Verschiebung nicht möglich, wird die Ursache des Konfliktes
angegeben - etwa, wenn der Raum bereits belegt ist, wenn der
an der zu verschiebenden Stunde beteiligte Lehrer zum betreffenden
Zeitpunkt bereits bei einer anderen Klasse unterrichtet u.s.w.
...
- Die
meisten Nebenbedingungen können manuell geändert werden.
Wurde für eine Problem-Stunde manuell eine gute Lösung
gefunden, läßt sie sich z.B. fest im Plan verankern
(Zeit-Restriktion) und kann durch folgende automatische Optimierungen
nicht mehr verschoben werden.
- Es
ist dem Nutzer freigestellt, zwischen automatischer und manueller
Plan-Erstellung zu wechseln. Die automatische Optimierung kann
durch eine manuelle Phase unterbrochen und anschließend
wieder gestartet werden.
Vertretungsplan
Ausgabe
- Die
Ausgabe erfolgt per OLE-Automation nach MS Word.
- Es
können (alle oder ausgewählte) Stundenpläne für
Lehrer und Klassen bzw. Belegungs-Pläne für Räume
und Vertretungs-Pläne ausgegeben werden.
- Die
Ausgabe erfolgt stets in Tabellenform.
Unterstützte
Schul -bzw.
Unterrichts-Typen
Unterstützt
wird Unterricht im Klassenverband
und die Definition von Kursen.
Für
Schulen, die ein komplettes Kurs-System fahren, ist die Software
also i. allg. nicht geeignet.
Entwicklungs-Informationen
Für
die Entwicklung der Software wurde der C++ Builder 3.0 von Borland
verwendet.
Der Entwicklungs-Zeitraum belief sich auf ungefähr 6 Monate.
Die Software
umfaßt ca. 19 000 Zeilen Quellcode.
An
dieser Stelle möchte ich einige Danksagungen loswerden.
Danke, für
-
die Bereitstellung des Entwicklungssystems durch die Firma CODie
Software Products
- viel
Geduld und wertvolle Ratschläge von Herr Dr. Staubel von
der Berliner Ingenieursgesellschaft REUS
- die
Zeit, die einige Lehrer als Versuchskaninchen aufgebracht haben
Screen-Shot
und Download
Der
folgende Screen-Shot zeigt einen Ausschnitt des Fensters, in welchem
die manuelle Plan-Erstellung erfolgt. Die dunkel hervorgehobene
Stunde soll an eine andere Zeit verschoben werden. Dazu muß
sie ihren Platz mit einer anderen Stunde tauschen. Die Software
findet 3 Stunden, die in Frage kommen (grün umrandet).
Die übrigen Farben kennzeichnen die Unterrichts-Typen (Kurse
rot und Mehrfachstunden blau).
Die
vorliegende Version ist frei verfügbar und voll funktionsfähig.
Eine Hilfe-Datei steht nicht zur Verfügung.
Mitgeliefert
wird ein Beispiel-Plan (BspPlan.pdt). Aus dieser Datei läßt
sich bei Bedarf die zugehörige Stamm-Daten-Datei erzeugen.
Für
nähere Informationen zu den Optimierungs-Algorithmen, Programm-Interna
und was das alles eigentlich mit evolutionärer Programmierung
zu tun hat, wird auf die umfangreiche Studien-Arbeit verwiesen.
Studien-Arbeit:
expose.zip
(285K, pdf-Dokument)
Das
Programm: SPGenerator.zip
(627K, Programm-Datei + Beispiel-Plan)
|