Aller au contenu. | Aller à la navigation

Outils personnels

Navigation

Problemstellung

next up previous contents
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
angenommen. Kompaktheit und gleichmäßige Verteilung wurden, wenn möglich, fest integriert, können also nicht deaktiviert werden. Die Modellierung ausgefallener Anforderungen, wie geographischer Bedingungen wurde nicht vorgesehen, siehe hierzu auch Kapitel 10. Wie auch bei COOPER und KINGSTON [CK95b] könnte das System auch zur Lehrerverteilung verwendet werden, dies wird aber von den Lösungsverfahren nicht gesondert unterstützt.
Im folgenden wird das hier beschriebene Problem als RSTP (real school timetabling problem) bezeichnet.



(c) Martin Loehnertz 1999