Termine:
| Vorlesung: |
| Di | 12:15-13:45 | Raum 31/E05 |
| Mi | 12:15-13:45 | Raum 31/449a |
|
| Übung: |
| Mo | 12:15-13:45 | Raum 31/423 |
Inhalt:
We study complex scheduling problems (resource-constrained project scheduling,
generalized shop scheduling problems, timetabling, sports league scheduling)
and efficient solution methods for them (local search methods, constrained
propagation, linear programming, branch-and-bound algorithms, genetic
algorithms).
In all these problems we are given a set of activities (jobs) which have to be
processed for a certain time. During processing they need some additional
resources (machines, people, energy, money) which are available with limited
capacities. The main problem consists in finding a schedule which satisfies the
resource constraints and minimizes a certain objective function.
Examples for such problems can be found in production planning, school
timetabling, railway scheduling, sports league scheduling, etc.
Special topics are:
- The resource-constrained project scheduling problem (RCPSP), some
generalizations and applications
- Constraint propagation for the RCPSP
- Lower bounds for the RCPSP
- Heuristics for the RCPSP
- Branch-and-bound algorithms for the RCPSP
- Applications (timetabling, sports league scheduling)
- Complex job-shop problems
- Heuristics for the job-shop problem
- Generalizations of the job-shop problem (transportation, limited buffers)
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. (2005):
Complex Scheduling, Springer (to appear).
- 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:
Teilnehmen können alle interessierten Studierende aus den Studiengängen
Mathematik, Angewandte Systemwissenschaft und Cognitive Science.
Insbesondere können im Anschluss an die Veranstaltung Bachelor- oder
Diplomarbeiten vergeben werden.
Schein:
Voraussetzung für den Erwerb eines Scheins zur Veranstaltung
ist die regelmäßige 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.
Zusätzlich sollte jede Gruppe in den Übungen mindestens einmal eine Lösung
einer Programmieraufgabe vorstellen.
Prüfungsrelevant sind alle Kapitel der Vorlesung sowie die Themen
aus den Übungen.
| Last update: 14.03.2005 (SK) |
