Endgültige Ausschreibung des Projektes
Stundenplanerstellung

Problemstellung

Die Erstellung von Stundenplänen im Schul- und Universitätsbereich stellt ein schwieriges Optimierungsproblem dar. Stundenpläne bestehen aus den folgenden Elementen:

• einer Menge von Lehrenden L
• einer Menge von Klassen K
• einer Menge von Lehrveranstaltungen V
• einer Menge von Räumen R
• einer Menge von Raumklassen S
• einer Menge von Zeitschienen Z

Die einzelnen Elemente sind durch verschiedene Attribute charakterisiert, die im folgenden kurz vorgestellt werden.

• ein Lehrer $l\in L$ besitzt die Attribute
  • $\mathit{Nummer}(l) \in {\mathbb{N} }$ - eindeutige Nummer des Lehrers
  • $\mathit{Name}(l) \in \Sigma^*$ - Name des Lehrers
  • $\mathit{freie\_Tage}(l) \in {\mathbb{N} }$ - die Anzahl der Tage, die pro Woche unterrichtsfrei sein sollten
  • $\mathit{unverfuegbar}(l) \subset Z$ - Zeitslots, an denen der Lehrer nicht zur Verfügung steht
• eine Klasse $k \in K$ besitzt die Attribute
  • $\mathit{Nummer}(k) \in {\mathbb{N} }$ - eindeutige Nummer der Klasse
  • $\mathit{Name}(k) \in \Sigma^*$ - Name der Klasse
  • $\mathit{Groesse}(k) \in {\mathbb{N} }$ - Größe der Klasse
  • $\mathit{freie\_Tage}(k) \in {\mathbb{N} }$ - die Anzahl der Tage, die pro Woche unterrichtsfrei sein sollten
  • $\mathit{unverfuegbar}(k) \subset Z$ - Zeitslots, an denen die Klasse nicht zur Verfügung steht
• eine Veranstaltung $v \in V$ besitzt die Attribute
  • $\mathit{Nummer}(v) \in {\mathbb{N} }$ - eindeutige Nummer der Veranstaltung
  • $\mathit{Name}(v) \in \Sigma^*$ - Name der Veranstaltung
  • $\mathit{Lehrer}(v) \subset L$ - involvierte Lehrer
  • $\mathit{Klassen}(v) \subset K$ - involvierte Klassen
  • $\mathit{Raumanzahl}(v) \in {\mathbb{N} }$ - Anzahl der benötigten Räume
  • $\mathit{Raumklasse}(v) \subset S$ - bevorzugte Raumklassen
  • $\mathit{alternative\_Raumklasse}(v) \subset S$ - alternative Raumklassen
  • $\mathit{Stundenmodus}(v) \in ({\mathbb{N} }\cup \bar{{\mathbb{N} }})^+$ - Modus, in dem die Veranstaltung abzuhalten ist, z.B. ,,1`` bedeutet eine Stunde pro Tag und ,,2`` eine Doppelstunde pro Tag. Elemente $\bar{n} \in \bar{{\mathbb{N} }}$ werden nur 14-tägig abgehalten.
  • $\mathit{alternativer\_Stundenmodus}(v) \in ({\mathbb{N} }\cup \bar{{\mathbb{N} }})^+$ - ein alternativer Stundenmodus
  • $\mathit{Randplatzierung}(v) \in \{0,1\}$ - die Veranstaltung soll bevorzugt am Rand platziert werden
  • $\mathit{gekoppelte\_Veranstaltung}(v) \subset V$ - die Veranstaltung darf nicht an denselben Tagen wie die gekoppelten abgehalten werden.
• ein Raum $r \in R$ besitzt die Attribute
  • $\mathit{Nummer}(r) \in {\mathbb{N} }$ - eindeutige Nummer des Raums
  • $\mathit{Name}(r) \in \Sigma^*$ - Name des Raums
  • $\mathit{Groesse}(r) \subset {\mathbb{N} }$ - Größe des Raums
  • $\mathit{unverfuegbar}(r) \subset Z$ - Zeiten, zu denen der Raum nicht verfügbar ist.
• eine Raumklasse $s \in S$ besitzt die Attribute
  • $\mathit{Nummer}(s) \in {\mathbb{N} }$ - eindeutige Nummer der Raumklasse
  • $\mathit{Name}(s) \in \Sigma^*$ - Name der Raumklasse
  • $\mathit{Raeume}(s) \subset R$ - Räume der Raumklasse
• eine Zeitschiene $z \in Z$ besitzt die Attribute
  • $\mathit{Nummer}(z) \in {\mathbb{N} }$ - eindeutige Nummer der Zeitschiene
  • $\mathit{Name}(z) \in \Sigma^*$ - Name der Zeischiene
  • $\mathit{Tag}(z) \subset \{1,2,3,4,5\}$ - Tag
  • $\mathit{Tageszeit}(z) \in \{\mathit{vormittag},\mathit{nachmittag},\mathit{abend}\}$ - Tageszeit
  • $\mathit{Slot}(z) \in {\mathbb{N} }$ - Nummer des Slots der jeweiligen Tageszeit
  • $\mathit{Pause}(z) \in \{0,1\}$ - anschließende Pause

Beim Stundenplanerstellungsproblem besteht die Aufgabe darin, eine Zuordnung der Lehrveranstaltungen V auf die Räume R und die Zeitschienen Z zu finden, so dass die folgenden (harten) Randbedingungen erfüllt sind:

• jeder Lehrer wird jeder Zeitschiene nur einmal zugeordnet
• jede Klasse wird jeder Zeitschiene nur einmal zugeordnet
• jedem Raum ist pro Zeitschiene nur eine Veranstaltung zugeordnet

Ein solches reines Erfüllungsproblem ist allerdings sehr oft nicht ausreichend für eine Stundenplangestaltung. Daher sind folgende zusätzlichen (weichen) Randbedingungen noch zu berücksichtigen - diese können je nach Anforderungen unterschiedlich gewichtet werden (bzw. durch eine Gewichtung 0 nicht zum Tragen kommen):

• verletzte unterrichtsfreie Tage der Lehrer
• verletzte unterrichtsfreie Tage der Klasse
• Verletzung der Unverfügbarkeit eines Lehrers
• Verletzung der Unverfügbarkeit einer Klasse
• Verletzung der Unverfügbarkeit eines Raumes
• zu geringe Größe der Räume für eine Veranstaltung
• Verletzung der primären Raumklasse einer Veranstaltung
• zusätzliche Verletzung der alternativen Raumklasse einer Veranstaltung
• Verletzung des primären Stundenmodus einer Veranstaltung (mit Berücksichtigung der gekoppelten Veranstaltungen)
• zusätzliche Verletzung der alternativen Stundenmodus einer Veranstaltung (mit Berücksichtigung der gekoppelten Veranstaltungen)
• Verletzung einer Pause durch eine Doppelstunde
• Verletzung der erwünschten Randplatzierungen
• Minimierung der Hohlstunden der Klassen
• Minimierung der Hohlstunden der Lehrer
• Minimierung der Veranstaltungen am Vormittag für jede Klasse
• Minimierung der Veranstaltungen am Nachmittag für jede Klasse
• Minimierung der Veranstaltungen am Abend für jede Klasse
• angestrebte Gleichverteilung der Termine jeder Veranstaltung über die Woche

Software-Anforderungen

• Import von Daten aus Textdateien (Format gegeben)
• Gewichtung von unterschiedlichen Randbedingungen für die Bewertung eines Stundenplans
• Möglichkeit einen Stundenplan zu speichern und zu laden (beliebiges Format)
• Potentielle Auswahl aus verschiedenen Optimierungsverfahren
• ein oder zwei Optimierungsverfahren sind zu implementieren, eine geeignete Schnittstelle soll das Hinzufügen von weiteren Verfahren ermöglichen (hierbei ist insbesondere zu beachten, dass die unterschiedlichen Verfahren unterschiedliche Darstellungen von Lösungen benutzen können, aus denen dann jeweils ein zu bewertender Stundenplan erzeugt werden kann.)
• Optimierungen mit einer zufälligen Initialisierung
• manuelle Veränderungen an einem Stundenplan (der z.B. das Ergebnis einer Optimierung ist)
• Für einzelne Verfahren (z.B. lokale Suche) kann auch eine Optimierung ausgehend von dem Resultat einer vorherigen Optimierung (oder dem manuell veränderten Resultat) stattfinden.
• ein Optimierungsmodul mit einem evolutionären Algorithmus
• ein Optimierungsmodul mit einer lokalen Suche
• Anzeige der noch vorhandenen Konflikte bei resultierenden Stundenplänen
• anzeigen/drucken von Stundenplänen für einzelne Klassen und Lehrer
• Es sollten Möglichkeiten vorgesehen (aber nicht komplett implementiert) werden, Änderungen am Stundenplanproblem vorzunehmen (z.B. andere Zuordnung der Lehrer zu den Veranstaltungen aufgrund des Ausfalls eines Lehrers, Hinzufügen einer Veranstaltung). Dadurch kann ein bestehender Stundenplan inkonsistent werden, sollte aber durch eine lokale Optimierung wieder verbessert werden können. Veränderte Stundenplanprobleme sollten unter einem neuen Namen abgespeichert werden können.

Angebote

Angebote beinhalten die folgenden Punkte:

• einen Oberflächenprototyp mit Beschreibung der Funktionalität
• kurze Beschreibung der geplanten Schnittstelle für die Optimierungsmodule
• Abschätzung der benötigten Mannstunden bzw. des Preises - eine detailliertere Aufschlüsselung kann hilfreich sein
• Voraussichtliche Planung mit Terminen für Präsentationen von Zwischenergebnissen beim Kunden - vorgegeben sind die folgenden Termine:
  • Prototyp und Angebot: 19. Juni 2000
  • Vergabe des Auftrags: 21. Juni 2000
  • Ergebnis einer Optimierung: 16. Oktober 2000
  • Fertige Software: 4. Dezember 2000
  • Weitere Ergebnisse von Optimierungen: 8. Januar 2001

Über dieses Dokument ...

This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -t Ausschreibung -split +0 ausschreibung_final.tex.

The translation was initiated by Karsten Weicker on 2000-05-08