|
Christian Viergutz |
Complex Scheduling Problems SS 2009 |
Inhalt:
|
Termine:
|
|||||||||||||||||||||
|
Es werden komplexe Schedulingprobleme wie z.B. ressourcenbeschränkte Projektplanungsprobleme, Timetablingprobleme (Stundenplanerstellung, Schichtplanung), Produktions- und Transportplanungsprobleme vorgestellt und dafür geeignete Lösungsalgorithmen wie Lokale Suche, Lineare Programmierung, Branch-and-Bound-Algorithmen und Metaheuristiken behandelt. Im Allgemeinen betrachtet man bei komplexen Schedulingproblemen eine gegebene Menge von Aktivitäten (Jobs), die für eine bestimmte Zeitdauer bearbeitet werden müssen. Während ihrer Bearbeitung werden Ressourcen (Maschinen, Personen, Energie, Geld) benötigt, die nur mit einer begrenzten Kapazität zur Verfügung stehen. Das Hauptproblem besteht darin, einen Plan zu finden, bei dem alle Ressourcenkapazitäten eingehalten werden und eine bestimmte Zielfunktion minimiert wird. Spezielle Themen der Vorlesung sind:
|
||||||||||||||||||||||
Material zur Vorlesung 
:
- Folien: Organisatorisches und Inhalt
- Detaillierte Version der polynomialen Reduktion von HamiltonPfad auf HamiltonKreis
- Link zur PSPLIB (Project Scheduling Problem Library)
- Java-Framework für Programmieraufgaben zur Transportoptimierung (korr. Version am 12.06.)
- Folien: Wiederholungsstunde am 1.7.09
- Folien: Komplettpaket (Folien 1-11, 3,5 MB)
Teilnahme :
Die Veranstaltung ist vorgesehen für M.Sc. ab dem 2. Semester und Diplomstudierende im Hauptstudium. Teilnehmen können alle interessierten Studierenden aus den Studiengängen Informatik, Mathematik, Angewandte Systemwissenschaft und Cognitive Science.
Scheinerwerb :
Ein Schein zur Veranstaltung kann durch die erfolgreiche Absolvierung
einer 2-stündigen Klausur am Ende des Semesters erworben werden.
Prüfungsrelevant sind dabei alle Kapitel der Vorlesung sowie die Themen aus den
Übungen.
Literatur :
- Brucker, P., Knust, S. (2006)
- Complex Scheduling, Springer.
- Dorndorf, U. (2002)
- Project Scheduling with Time Windows - From Theory to Applications, Springer.
- Golden, B., editor (1988)
- Vehicle Routing: methods and studies, North-Holland.
- Grünert, T., Irnich, S. (2005)
- Optimierung im Transport, Bände I und II, Shaker Verlag, Aachen.
- Korte, B., Vygen, J. (2008)
- Kombinatorische Optimierung: Theorie und Algorithmen, Springer. [elektr. Version im Uninetz vefügbar]
- Neumann, K., Schwindt, C., Zimmermann, J. (2003)
- Project Scheduling with Time Windows and Scarce Resources - Temporal and Resource-Constrained Project Scheduling with Regular and Nonregular Objective Functions, Springer.
- Toth, P., Vigo, D., editors (2002)
- The Vehicle Routing Problem, SIAM Monographs on discrete mathematics and applications, Philadelphia.