Dr. Sigrid Knust, Christian Viergutz
	Complex Scheduling Problems SS 07

Termine:

Inhalt:

Es werden komplexe Schedulingprobleme (ressourcenbeschränkte Projektplanungsprobleme, verallgemeinerte Shop-Schedulingprobleme, Timetabling- und Sportligaplanungsprobleme) und effiziente Lösungsalgorithmen für diese Probleme (lokale Suche, constraint propagation, lineare Programmierung, Branch-and-Bound-Algorithmen, genetische 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
• Das Jobshop-Problem
• Heuristiken für das Jobshop-Problem
• Verallgemeinerungen des Jobshop-Problems (Transport, begrenzte Zwischenspeicher)

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.

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 Mathematik, Angewandte Systemwissenschaft und Cognitive Science.

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

Schein: