AG Kombinatorische Optimierung

Complex Scheduling Problems

(V4+Ü2)



Inhalt


Es werden ressourcenbeschränkte Projektplanungsprobleme und effiziente Lösungsalgorithmen (MIPs, Heuristiken, lokale Suche, genetische Algorithmen, constraint propagation, lineare Programmierung, Branch-and-Bound-Algorithmen) behandelt.


RCPSP

Gegeben ist eine 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.

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

Stichworte:

Literatur

Materialien

Teilnahme

Die Veranstaltung ist vorgesehen für M.Sc. ab dem 1. Semester. Grundkenntnisse aus der kombinatorischen Optimierung werden vorausgesetzt.

Schein

Voraussetzung für den Erwerb eines Scheins zur Veranstaltung ist die regelmäßige Teilnahme an den Übungen, die erfolgreiche Bearbeitung der praktischen Übungen und die erfolgreiche Absolvierung einer Prüfung (Klausur) am Ende des Semesters. Prüfungsrelevant sind alle Kapitel der Vorlesung sowie die Themen aus den Übungen.