Scheduling

Inhalt

Scheduling umfasst die Planung von Abläufen mittels Berechnung von Aufgaben-Reihenfolgen, unter Optimierung gegebener Zielfunktionen und Berücksichtigung von Randbedingungen.

Die Studierenden sollen in dieser Veranstaltung einen Überblick über Scheduling gewinnen, übliche Problemstellungen verstehen, deren Komplexität begreifen, Lösungsverfahren anwenden und auf andere Problemstellungen übertragen können.

Behandelt werden:

Modellierung und Zielfunktionen
Grundlagen der Komplexitätstheorie für numerische Probleme
Modelle mit einer Maschine
Modelle mit zeitabhängiger Bearbeitungszeit
Modelle mit mehreren Maschinen (Parallele Maschinen, Flow Shops, Job Shops, Open Shops)

Beispiel: Es seien vier Aufträge j=1,...,4 gegeben. Diese sollen nacheinander auf einer Maschine eingeplant werden. Ziel sei die Minimierung der Summe aller Fertigstellungszeiten C₁+C₂+C₃+C₄. Im Bild sind zwei Sequenzen dargestellt, S₁ und S₂. Es ist erkennbar, dass S₂ besser abschneidet als S₁. In diesem Fall lässt sich die optimale Sequenz durch Sortieren der Aufträge nach ihrer Dauer ermitteln. Das Problem ist also in polynomieller Zeit, abhängig von der Auftragsanzahl, lösbar. Darf jeder Auftrag jedoch erst nach einem gewissen Freigabetermin eingeplant werden, handelt es sich um ein NP-vollständiges Optimierungsproblem, es kann also nicht mehr in polynomieller Zeit gelöst werden (außer P=NP).

Dozent

Prof. Dr. Uwe Schöning
Helmut Sedding

Ablauf

Vorlesung und Übung:
Montags 12:30-14:00 Uhr in Raum O27-2203
Donnerstags 12:30-14:00 Uhr in Raum O27-2203

Klausur:
19.07.2018, 12:00 Uhr in Raum O27-2203