Uni-Logo

Complex Scheduling Problems


Inhalt:

RCPSP

Es werden komplexe Schedulingprobleme (ressourcenbeschränkte Projektplanungsprobleme, Anwendungen aus der Logistik, Timetabling- und Sportligaplanungsprobleme) und effiziente Lösungsalgorithmen (lokale Suche, genetische Algorithmen, constraint propagation, lineare Programmierung, Branch-and-Bound-Algorithmen) behandelt. Diese Veranstaltung ist gleichzeitig eine Einführung in allgemeine Lösungsmethoden der kombinatorischen Optimierung.
Darauf aufbauend soll es im nächsten SS eine Projektgruppe geben, die sich mit Optimierungsproblemen in Lagern beschäftigt.

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, der Schulstundenplanung, Eisenbahnscheduling, Sportligaplanung, usw.

Mögliche spezielle Themen sind:

Materialien:


Literatur:


Teilnehmer:

Die Veranstaltung ist vorgesehen für M.Sc. ab dem 1. Semester. 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 Masterarbeiten vergeben werden.


Schein:

Voraussetzung für den Erwerb eines Scheins zur Veranstaltung ist die regelmässige Teilnahme an den Übungen, die erfolgreiche Bearbeitung der Übungsaufgaben (jeweils 50% der Maximalpunkte in theoretischen und 50 % der Maximalpunkte in praktischen Aufgaben) und die erfolgreiche Absolvierung einer Klausur am Ende des Semesters. Prüfungsrelevant sind alle Kapitel der Vorlesung sowie die Themen aus den Übungen.