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)

Materialien:

• Überblick (PDF) (Überblick, Lernziele)
• Korrigierte Seiten 102-109
• Folien: Zusammenfassung zum RCPSP (Update am 4.7.07)
• Kapitel zu Sportligaplanung

Übungsblätter:

• Blatt 1 (RCPSP-Beispiel, Schichtplanung in Krankenhäusern, PSPLIB)
• Blatt 2 (Planung von Tischtennisligen, RCPSP mit Mindest- und Höchstabständen, Charakterisierung von RCPSP-Instanzen), Artikel zu Aufgabe 5 (PDF)
• Blatt 3 (Semesterstundenplan, Schedule-Generierungsschemata, Earliest Start Schedule), RCPSP-Instanzen für P2 (zip)
• Blatt 4 (ESS mit partiell-erneuerbaren Ressourcen, Multi-Mode left shifts, Metaheuristiken)
• Blatt 5 (Symmetrische Tripel, Simulated Annealing für das RCPSP)
  • Artikel über Simulated Annealing
  • PSPLIB: Single-Mode Instanzen
  • Ergebnisse für n=120: j120hrs.sm
  • Musterlösung zu Prog.-Aufgabe P2, kann (muss aber nicht) als Grundlage für P3 verwendet werden.
• Blatt 6 (SSD-Matrix, Input-/Output Tests, Constraint Propagation für das RCPSP)
• Blatt 7 (CP für kumulative Ressourcen, Vereinfachungen beim MRCPSP, Disjunktive Mengen und Output-Test)
• Blatt 8 (Eigenschaften, Beispiel und Implementation zu unteren Schranken)
• Blatt 9 (Branch-and-Bound Algorithmen für das RCPSP, Erstellung einer Klausuraufgabe) Musterlösung A17
• Blatt 10 (Algorithmen für die Sportligaplanung, Erstellung balancierter Spielpläne)
• Blatt 11 (DRRTs, HAPs)

Folien aus den Präsenzübungen

• Folien 1 (LP/IP-Wiederholung, RCPSP-Beispiel)
• Folien 2 (Komplexität und das RCPSP)

Abgabe der Übungsblätter:

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: