2. Problembeschreibung

2.1. Definition Stundenplanung

2.2. Die hier behandelte Instanz des Problems

2.2.1 Allgemein

• Einer Menge von Veranstaltungen V = {v₁, v₂, ..., v_n}
  Eine Veranstaltung ist dabei ein Treffen einer Menge von Teilnehmern
  Teil = {teil₁, teil₂, ..., teil_k}
  in einem bestimmten Raum, zu einer festen Zeit und für eine feste Zeitdauer (in diesem Fall eine Stunde und 15 Minuten). Die Teilnehmer verbrauchen Platz in dem Raum, der diesen nur begrenzt zur Verfügung stellt.
  Ausserdem benötigt eine Veranstaltung für ihren Ablauf noch eine Menge von Ressourcen
  Res = {res₁, res₂, ..., res_l},
  die der Raum, in dem die Veranstaltung stattfindet, zur Verfügung stellen muss.
  Beispiel:
  Eine Veranstaltung ist einer von den 2 Blöcken, aus denen die Vorlesung Analysis1 besteht und soll mit Analysis1_1 bezeichnet werden.
  Die Menge der Teilnehmer an Analysis1_1 ist dabei Teil = {Harms, II1, WI1}
  Die Teilnehmer beanspruchen genau soviel Platz, wieviel reale Personen sie repräsentieren.
  Die Menge der Ressourcen, die Analysis1_1 benötigt, ist dabei Res = {Tafel}.
  Der Begriff Veranstaltung ist also nicht mit dem Begriff Vorlesung zu verwechseln, da eine Vorlesung aus mehreren Veranstaltungen bestehen kann.
• Einer Menge von Räumen R = {r₁, r₂, ..., r_m}
  in denen Veranstaltungen stattfinden können. Ein Raum stellt eine bestimmte Anzahl AnzR von Plätzen für die Teilnehmer einer Veranstaltung und eine Menge von Raumressourcen
  RaumRes = {raumres₁, rraumres₂, ..., raumres_o}
  für den Ablauf einer Veranstaltung zur Verfügung.
  Beispiel:
  Ein Raum ist Hörsaal 5,
  der 150 Plätze
  und die Menge RaumRes = {Tafel, Beamer, Video, Audio} zur Verfügung stellt.
• Einer Menge von Zeitfenstern Z = {z₁, z₂, ..., z_p}.
  in denen Veranstaltungen stattfinden können. Zeitfenster sind die zeitlichen Anteile in welche die Planungsperiode (in unserem Fall eine Woche) eingeteilt ist, und in denen jeweils eine Veranstaltung stattfinden kann (in unserem Fall eine Stunde und 15 min).
  Beispiel:
  Montag 8:00-9:15 ist ein Zeitfenster
  Montag 17:00-18:15 ist ein Zeitfenster
  
• Eine Menge von Nebenbedingungen N, die Abhängigkeiten zwischen den Elementen der drei oben genannten Mengen beschreiben.

2.2.2. Nebenbedingungen

2.2.2.1. Allgemein

2.2.2.2 Notwendige Nebenbedingungen

• Gültige Raumbelegung
  Der Raum r, der einer Veranstaltung v zugeordnet wird, muss genügend Platz für alle Teilnehmer von v zur Verfügung stellen, und die Menge der Ressourcen die v benötigt, muss eine Teilmenge der Ressourcen sein, die r zur Verfügung stellt.
• Verhinderung eines Raum Clash
  In einem Raum r kann während eines Zeitfensters z nur maximal eine Veranstaltung v stattfinden. Das heisst, die Zuordnung, welche die Lösung beschreibt, muss injektiv sein.
• Ein Teilnehmer kann während eines Zeitfenster an maximal einer Veranstaltung teilnehmen. Das heisst, die Mengen der Teilnehmer der Veranstaltungen, die im gleichen Zeitfenster stattfinden, müssen disjunkt sein.

2.2.2.3 Erstrebenswerte Nebenbedingungen

• Raumauslastung
  Veranstaltungen sollten in Räumen stattfinden, bei denen die Differenz zwischen Raumkapazität und Platzverbrauch der Teilnehmer möglichst minimal ist.
• Teilnehmerauslastung
  Die Anzahl der Veranstaltungen, an denen ein Teilnehmer teilnehmen muss, sollte ein Maximum pro Tag nicht überschreiten, und sollte gleichmässig über die Planungsperiode (eine Woche) verteilt sein.
• Bewegungsminimierung
  Veranstaltungsteilnehmer sollten zwischen Veranstaltungen so wenig wie möglich die Veranstaltungsräume wechseln müssen

2.3. Komplexität des Problems