Universitätskursplanung mit Hilfe von Graphenfärbungen

Fast jeder Student wurde im Laufe seines Studiums schon mit dem Problem 
konfrontiert, dass sich die Termine von zu besuchenden Veranstaltungen 
überschneiden. Diese Umstände könnten das Studium unnötig belasten. Daher 
stellt sich zu Beginn eines jeden Semesters die Aufgabe, eine Vielzahl an 
Kursen so im zur Verfügung stehenden Zeithorizont einzuplanen, dass möglichst 
wenige Überschneidungen auftreten.

In dieser Arbeit wird auf die Planung der Veranstaltungen des 
2-Fächer-Bachelor-Studienganges eingegangen. Wegen der Vielfalt an möglichen 
Fachkombinationen treten hier zahlreiche Überschneidungsprobleme auf. 
Bei der Planung von Kursen ist daher darauf zu achten, dass Pflichtkurse 
desselben Faches nicht parallel stattfinden. Des Weiteren sollten Kurse häufig
gewählter Fachkombinationen  möglichst nicht kollidieren. Neben diesen 
Anforderungen müssen auch weitere Nebendingungen wie die Verfügbarkeit von 
Dozenten und Räumen beachtet werden.

Zur Modellierung wird ein Konfliktgraph gebildet, wobei die Knoten den 
Doppelstunden der einzuplanenden Kurse entsprechen. Kanten existieren 
zwischen denjenigen Knoten bzw. Stunden, die nicht gleichzeitig stattfinden 
sollen. Mithilfe der Techniken der Knotenfärbung wird eine Lösung gesucht, 
welche möglichst wenige Überschneidungen für die Gesamtheit der 
2-Fächer-Bachelor-Studenten erzeugt. 
Bei der Größe dieses Optimierungsproblems sind exakte Lösungsverfahren nicht 
anwendbar, daher werden heuristische Verfahren entwickelt und implementiert, 
die das Problem mit vertretbarem Aufwand lösen und hinreichend gute 
Ergebnisse liefern.