Skip to content. | Skip to navigation

Personal tools

Sections

Modell

next up previous contents
Next: Gesamtaufbau Up: Grundlegende ArchitekturModell und Previous: Problemstellung

Modell

Das betrachtete Problem als ILP

Als Eingabe seien gegeben: Eine Menge von Objekten tex2html_wrap_inline6510 , eine Menge von Mengen tex2html_wrap_inline6512 , T als Menge von Timeslots und eine Menge von Kursen tex2html_wrap_inline6516 , wobei jeder Koeffizient von k angibt, wieviele Objekte der entsprechenden Gruppe benötigt werden, und tex2html_wrap_inline6520 die Vielfachheit des jeweiligen Kurses angibt. Der Einfachheit halber seien die Gruppenbeziehungen durch eine Matrix tex2html_wrap_inline6522 kodiert.

Dann stellt sich das Suchproblem in der folgenden Form dargif: Da es der Verständlichkeit dient, werden die Variablen mit den entsprechenden Objekten anstatt ihrer Indices in den jeweiligen Mengen indiziert: Finde

displaymath6524

und

displaymath6526

mit

     eqnarray1605

tex2html_wrap_inline6528 gibt an, zu welchen Zeiten eine Stunde eines Kurses liegt. tex2html_wrap_inline6530 beschreibt, welche Objekte zu welchen Zeitpunkten welchem Kurs in welcher Funktion zugeordnet werden.

  • Bedingung 5.1 gibt an, daß jede Stunde eines Kurses genau einmal stattfindet.
  • 5.2 sorgt dafür, daß zu dieser Stunde dem Kurs ausreichend Ressourcen zugeordnet werden.
  • Bedingung 5.3 sorgt dafür, daß die Ressourcen nur zu Aufgaben verwandt werden, für die sie geeignet sind. Hier sei tex2html_wrap_inline6532 der charakteristische Vektor für o aus tex2html_wrap_inline6536 .
  • 5.4 legt fest, daß jedes Objekt pro Zeiteinheit höchstens einmal verwendet werden darf.
Das oben vorgestellte Modell erlaubt es noch, mehrere Stunden eines Kurses, der ausschließlich aus flexiblen Ressourcen besteht, derselben Zeitstunde zuzuordnen. Dies kann durch

displaymath6538

unterbunden werden. Dies wird hier nicht explizit gefordert; einige der Lösungsverfahren produzieren aber nur Lösungen, die dies beachten. Da es sehr unwahrscheinlich ist, daß dieser Fall vorkommt, wird darauf aber nicht weiter eingegangen.
Daß diese Konstruktion so relativ kompliziert ist, liegt an der Anforderung, die flexiblen Ressourcen nur zu bestimmten Zeiten auszuwählen. Ließe man hier quadratische Constraints zu, so könnte man bei y die Zeitdimension sparen. Bei einer durchschnittlichen Schule von 30 Klassen, 40 Lehrern, 40 Räumen, 35 Zeitstunden, im Schnitt 3 Zeitstunden pro Kurs, 10 Kursen pro Klasse und 100 Gruppen ergibt sich eine Zahl von 300 Millionen Variablen. Entfernte man das Problem flexibler Ressourcen vollständig, wären es nur ca. 31500, d.h. ca. um einen Faktor tex2html_wrap_inline6560 weniger. Eine ebenfalls mögliche Art der Darstellung ist die, jeweils statt tex2html_wrap_inline6562 nur tex2html_wrap_inline6564 zu verwenden und als weitere - nur mit ähnlichem Aufwand wie oben darstellbare - Nebenbedingung zu verlangen, daß es eine Abbildung von tex2html_wrap_inline6566 nach tex2html_wrap_inline6568 gibt, so daß die obigen Bedingungen erfüllt sind. Im Zusammenhang mit Abschnitt 8.4.3 erkennt man, daß bei Festhalten von tex2html_wrap_inline6528 das Bestimmen von tex2html_wrap_inline6530 durch ein Matchingverfahren geschehen kann. Daher wird zumeist darauf verzichtet, tex2html_wrap_inline6530 mit zu verwalten, so daß auch hier die Variablenzahl - allerdings auf Kosten der Komplexität - sehr stark verringert werden kann.  

Zielfunktion

Allen nachfolgend aufgeführten Verfahren wurde eine einheitliche Zielfunktion zu Grunde gelegt. Aus der Menge der Nebenbedingungen konnten hier natürlich nur die einbezogen werden, für die ein Modellierungsschema vorgesehen ist. Insbesondere können also Anforderungen, welche Stunden nicht aufeinanderfolgen dürfen o.ä., nicht kodiert werden (siehe hierzu Kapitel 10). Die Zielfunktion wurde in mehreren Schichten organisiert, so daß sie am besten als lexikographische Ordnung auf einem Vektor von Zielwerten angesehen werden kann. Dies läßt sich natürlich auch realisieren, indem jeder Koeffizient des Vektors mit dem Maximalwert des nächsten Koeffizienten gewichtet wird (vgl. Kapitel 6.6.5.1), dies wurde hier aber der Übersichtlichkeit halber nur in der Kurzanzeige während des laufenden Optimerungsprozesses getan. Die oberste Schicht repräsentiert nochmals die Kollisionsfreiheit, da diese bei einem der Verfahren nicht als Nebenbedingung auftritt.
Im schulischen Umfeld läßt sich das Konzept Fach nicht umgehen. Daher sei tex2html_wrap_inline6576 eine Abbildung, die jedem Kurs das zugehörige Fach zuordnet. Des weiteren sei die Menge der Zeiteinheiten in Tage zerlegt: tex2html_wrap_inline6578 und dem Zeitverlauf entsprechend angeordnet. Dann baut sich das Ganze wie folgt auf:

Kollisionen tex2html_wrap_inline6580
Maximale
Stundenzahl einer
Fach-Klassen-Paarung tex2html_wrap_inline6582 ist Klasse tex2html_wrap_inline6584
Fach-Klassen-Springstunden tex2html_wrap_inline6586 ist Klasse tex2html_wrap_inline6584
Klassenspringstunden tex2html_wrap_inline6590 ist Klasse tex2html_wrap_inline6584
Bevorzugte Zeitpunkte tex2html_wrap_inline6594
Bevorzugte flexible Objekte tex2html_wrap_inline6596
Lehrerspringstunden tex2html_wrap_inline6590 ist Lehrer tex2html_wrap_inline6584

Wobei w sowohl das Verhältnis zwischen Objekten, als auch das von Objekten zu Zeiteinheiten angibt. Diese Bewertung kann neutral sein. In diesem Falle wird ein Wert aus den Relationen der betreffenden Übermengen ermittelt (s. Abschnitt 8.4). Der Übersichtlichkeit halber wurde in der Tabelle weggelassen, daß t' und t'' zum selben Tag gehören müssen, wie t.

Der Unterschied zwischen Klassen- und Lehrerspringstunden muß vom Benutzer angefordert werde (s. Paragraph 8.2.3), da zunächst kein Unterschied zwischen den Objekttypen vorgesehen ist. Die Normalisierung der Gruppen zueinander erfolgt unter Ausschluß der Paarungen mit Wert 0, da deren große Zahl Veränderungen in diesem Bereich fast völlig nivellieren würde (vgl. Abschnitt 8.4.2).
Die letzte Subfunktion wird in der Implementierung allerdings nicht exakt so ausgewertet wie hier beschrieben, sondern es fließen nur diejenigen Paare ein, bei denen das eine ein statisches und das andere ein dynamisches Objekt ist, Die Beziehung zwischen den festen Objekten ergäbe ohnehin nur eine Konstante, die für alle Lösungen gleich ist; die Hinzunahme der Beziehungen zwischen flexiblen Objekten ließe selbst die Bestimmung von tex2html_wrap_inline6530 bei feststehendem tex2html_wrap_inline6528 tex2html_wrap_inline5146 -hart werden (s. Unterkapitel 3.6.1). An einigen Stellen, an denen die Geschwindigkeit der Auswertung von besonderer Bedeutung ist, wird hier nur festgestellt, wieviele dieser Ressourcen verfügbar sind.


next up previous contents
Next: Gesamtaufbau Up: Grundlegende ArchitekturModell und Previous: Problemstellung

(c) Martin Loehnertz 1999