Modell

Das betrachtete Problem als ILP

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

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

und

mit

gibt an, zu welchen Zeiten eine Stunde eines Kurses liegt. 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 der charakteristische Vektor für o aus .
• 5.4 legt fest, daß jedes Objekt pro Zeiteinheit höchstens einmal verwendet werden darf.

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 weniger. Eine ebenfalls mögliche Art der Darstellung ist die, jeweils statt nur zu verwenden und als weitere - nur mit ähnlichem Aufwand wie oben darstellbare - Nebenbedingung zu verlangen, daß es eine Abbildung von nach gibt, so daß die obigen Bedingungen erfüllt sind. Im Zusammenhang mit Abschnitt 8.4.3 erkennt man, daß bei Festhalten von das Bestimmen von durch ein Matchingverfahren geschehen kann. Daher wird zumeist darauf verzichtet, 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 eine Abbildung, die jedem Kurs das zugehörige Fach zuordnet. Des weiteren sei die Menge der Zeiteinheiten in Tage zerlegt: und dem Zeitverlauf entsprechend angeordnet. Dann baut sich das Ganze wie folgt auf:

Kollisionen
Maximale
Stundenzahl einer
Fach-Klassen-Paarung	ist Klasse
Fach-Klassen-Springstunden	ist Klasse
Klassenspringstunden	ist Klasse
Bevorzugte Zeitpunkte
Bevorzugte flexible Objekte
Lehrerspringstunden	ist Lehrer

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 bei feststehendem -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.