UnivIS
Informationssystem der Friedrich-Alexander-Universität Erlangen-Nürnberg © Config eG 
FAU Logo
  Sammlung/Stundenplan    Modulbelegung Home  |  Rechtliches  |  Kontakt  |  Hilfe    
Suche:      Semester:   
 Lehr-
veranstaltungen
   Personen/
Einrichtungen
   Räume   Forschungs-
bericht
   Publi-
kationen
   Internat.
Kontakte
   Examens-
arbeiten
   Telefon &
E-Mail
 
 
 Darstellung
 
Druckansicht

 
 
Einrichtungen >> Technische Fakultät (TF) >> Department Informatik (INF) >> Lehrstuhl für Informatik 2 (Programmiersysteme) >>
Algorithmen für Zeitplanungsprobleme

Das Problem der Zeitplanerstellung (Timetabling) besitzt zahlreiche Anwendungsbereiche, so zum Beispiel die Schulstundenplanung, die Personaleinsatzplanung oder die Stundenplanung an Universitäten. Aufgrund des großen Aufwands, den die manuelle Erstellung solcher Zeitpläne erfodert, besteht Bedarf nach einer automatisierten Vorgehensweise. Daher wurden in den letzten Jahren verschiedene computergestützte Verfahren getestet und auch angewendet. Beispiele für solche Verfahren sind Genetische Algorithmen, Tabu Search, Constraint-Logische Programmierung oder diverse andere Heuristiken. Jedoch unterscheiden sich alle bisherigen Implementierungen der Algorithmen für Timetabling-Probleme in ihren Datenstrukturen und damit auch in ihrer Problemlösung, die an die jeweilige Datenstruktur angepasst werden muss.
Um den Beschreibungs- und Implementierungsaufwand für neue Timetabling-Probleme zu reduzieren sowie eine größere Vergleichbarkeit unterschiedlicher Timetabling-Probleme zu gewährleisten, wurde daher im Jahr 2002 zunächst eine formale Beschreibung des Timetabling-Problems vorgenommen. Daraus wurde eine allgemeine Timetabling-Sprache und ein Timetabling-Framework entwickelt, mit der beliebige Timetabling-Probleme beschrieben werden können. Für einen konkreten Planungzeitraum kann dann mit Hilfe eines Genetischen Algorithmus oder eines einfachen Suchverfahrens ein Zeitplan erstellt werden.
Nächstes Forschungsziel wird der Vergleich unterschiedlicher Optimierungsverfahren sein, mit dem Ziel, die Eignung der Verfahren zur Erstellung von Zeitplänen zu untersuchen. Weiterhin ist die Untersuchung der Struktur von Zeitplanungsproblemen von Interesse, um Rückschlüsse auf die Lösbarkeit von Zeitplanungsproblemen unterschiedlicher Komplexität ziehen zu können.
Beteiligte:
Dr.-Ing. Matthias Gröbner

Stichwörter:
Zeitplanung; Timetabling; Zeitplanerstellung; Genetische Algorithmen;Genetischer Algorithmus; Personaleinsatzplanung; Schulstundenplanung; Schulstundenplanerstellung; Timetable; Tabu Search; Evolutionäre Verfahren

Laufzeit: 1.11.1999 - 31.12.2002

Kontakt:
Telefon +49 9131 85 27825
UnivIS ist ein Produkt der Config eG, Buckenhof