Prof. Dr. Sigrid Knust, M.Sc. Mareike Paul
	Complex Scheduling Problems SS 11

Termine:

Inhalt:

Es werden komplexe Schedulingprobleme (ressourcenbeschränkte Projektplanungsprobleme, Timetabling- und Sportligaplanungsprobleme) und effiziente Lösungsalgorithmen für diese Probleme (lokale Suche, genetische Algorithmen, constraint propagation, lineare Programmierung, Branch-and-Bound-Algorithmen) behandelt.

Bei allen diesen Problemen ist eine Menge von Aktivitäten (Jobs) gegeben, 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.

Beispiele für solche Probleme finden sich in der Produktionsplanung, der Schulstundenplanung, Eisenbahnscheduling, Sportligaplanung, usw.

• Das RCPSP (Resource-constrained project scheduling problem), einige Verallgemeinerungen und Anwendungen
• Heuristiken für das RCPSP
• Constraint propagation für das RCPSP
• Untere Schranken für das RCPSP
• Branch-and-Bound Algorithmen für das RCPSP
• Sportligaplanung
• Schichtplanung

Materialien:

• Überblick (PDF) (Überblick, Lernziele)
• ZIB Optimization Suite (enthält Zimpl, SCIP und SoPlex)

Literatur:

• Baptiste, P., Le Pape, C., Nuijten, W. (2001): Constraint-Based Scheduling -- Applying Constraint Programming to Scheduling Problems, International Series in Operations Research and Management Science, Vol. 39, Kluwer.
• Brucker, P., Knust, S. (2006): Complex Scheduling, Springer.
• Demeulemeester, E., Herroelen, W. (2002): Project Scheduling, A Research Handbook, Kluwer.
• Dorndorf, U. (2002): Project Scheduling with Time Windows - From Theory to Applications, Springer.
• 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.
• PSPLIB

Teilnehmer:

Die Veranstaltung ist vorgesehen für M.Sc. ab dem 2. Semester und Diplomstudierende im Hauptstudium. Teilnehmen können alle interessierten Studierende aus den Studiengängen Informatik, Mathematik, Angewandte Systemwissenschaft und Cognitive Science.

Insbesondere können im Anschluss an die Veranstaltung Master- oder Diplomarbeiten vergeben werden.

Schein: