Problemstellung
Next: Modell Up: Grundlegende ArchitekturModell und Previous: Grundlegende ArchitekturModell und
Problemstellung
In dieser Arbeit wurde als Problem das University Timetabling mit festen Zeitstunden gewählt, da dieses genau den
angestrebten Einsatzgebieten (vgl. Kapitel 1) entspricht.
Um einige Nebenbedingungen einfacher darstellen zu können, wurde allerdings die Sichtweise etwas geändert: Zunächst wird das Ganze nicht mehr aus Sicht der Curricula, sondern aus Sicht
der Kurse betrachtet. Ein Kurs, im folgenden Gruppe genannt, besteht aus den Curricula, an denen
er beteiligt ist, d.h. eine Gruppe enthält die Schüler, Lehrer und Räume, die für die entsprechende Schulstunde relevant sind.
Dieses Problem ist entspricht somit in der Grundform einem mehrfachen Set-Packing bzw. einem mehrdimensionalen Bin-Packing Problem.
Da aber nicht alle Ressourcen statisch sind, wird das Ganze so weiter relaxiert, daß jede Gruppe aus Ressourcenanforderungen der Form 3 Biologieräume besteht. Die statischen Ressourcen gehen darin auf, indem hier stets die volle Zahl der zur Verfügung stehenden Objekte angefordert wird (1 Herr Meier). Hierbei wird explizit vorgesehen, daß sich diese Anforderungen in beliebiger Weise überschneiden können. D.h. es kann durchaus auch vorkommen, daß ein Raum sowohl Biologie- als auch Chemieraum sein kann. Die Aufgabe besteht also in der Auswahl der flexiblen Ressourcen und dem kollisionsfreien Zuordnen zu den Zeitstunden. Es ist hier nicht sinnvoll, dies in mehrere Probleme aufzuteilen, da stets Beziehungen zwischen den flexiblen Objekten und den Zeitstunden gegeben sind. Als Nebenbedingungen werden
- Abwesenheitszeiten,
- bevorzugte Zeiten,
- bevorzugte Ressourcen,
- und Springstundenminimierung
Im folgenden wird das hier beschriebene Problem als RSTP (real school timetabling problem) bezeichnet.
(c) Martin Loehnertz 1999