Institut für Wirtschaftswissenschaft > Abteilungen > Abteilung für Betriebswirtschaftslehre und Unternehmensforschung > Studium > Abschlussarbeiten > Zu vergebende Arbeiten > Vergleichende Beurteilung von Verfahren zur Lösung von Timetabling Problemen

Aufgabenstellung

Zwei zentrale Vertreter von Timetabling Problemen sind das Course Timetabling Problem sowie das Examination Timetabling Problem. Das Ziel des Course Timetabling Problems besteht darin, einen (i.d.R. wöchentlichen) Zeitplan für alle Vorlesungen einer Universität oder eines Fachbereichs zu erzeugen, der zeitliche Überschneidungen jener Vorlesungen minimiert, die von denselben Studenten besucht werden. Aufgabe des Examination Timetabling Problem ist es, einen Zeitplan für die Prüfungen einer Menge von universitären Lehrveranstaltungen zu finden, der die zeitliche Überschneidung von Prüfungen, die von denselben Studenten abgelegt werden, unterbindet und der die Zeiträume zwischen Prüfungszeitpunkten für alle Studenten maximiert. Für beide Probleme gilt, dass Sie in NP liegen.

Ziel der Diplomarbeit ist es, die Eignung von lokalen Suchverfahren und von Constraint Propagation Verfahren zur Lösung der genannten Timetabling Probleme zu untersuchen. Lokale Suchverfahren sind Heuristiken, die ausgehend von einer Ausgangslösung den Suchraum "durchwandern", wobei in jeder Iteration von einer Lösung zu einer "benachbarten" Lösung gewechselt wird. Somit kommt der Repräsentation einer Lösung und dem Nachbarschaftsbegriff (Wann sind zwei Lösungen "benachbart"?) eine besondere Bedeutung zu. Die Idee des Constraint Propagation ist es, den Such- und Optimierungsvorgang zu vereinfachen, indem die Menge der zulässigen Lösungen sukzessive verkleinert wird. Dazu werden aus den vorliegenden Problemdaten zusätzliche Nebenbedingungen abgeleitet. Im besten Fall lässt sich auf diese Weise der Lösungsraum so weit verkleinern, dass nur noch eine Lösung zulässig ist, die dann auch optimal sein muss.

Literatur: z.B.

  • Schaerf, A. (1995): A Survey of Automated Timetabling. Centrum voor Wiskunde en Informatica (CWI), Niederlande.
  • Burke, E., Erben, W. (Hrsg.) (2000): PATAT 2000 – Proceedings of the 3rd international conference on the Practice And Theory of Automated Timetabling. Fachhochschule Konstanz.
  • Aarts, E., Lenstra, J.K. (1997): Local Search in Combinatorial Optimization. Wiley & Sons.
  • Marriott, K., Stuckey, P.J. (1999): Programming with Constraints – An Introduction, 2. Aufl. MIT

Nähere Auskünfte: Zimmermann

 

Kontakt  Sitemap  Impressum
© TU Clausthal 2017