Winter 2017/18: Einführung in die Scheduling-Theorie

(Mathematische Modelle und Methoden für deterministische Scheduling-Probleme)

Neu:

Neu:

Termine

Vorlesung:

Mi 13.15 - 14.45 in G05-118 (40)

Fr 13.15 - 14.45 in G23-K11 (36)

Übung:

Do 13.15 - 14.45 in G22A-203 (40)

Inhalt

Die Wahlpflichtvorlesung im Umfang 4 V / 2 Ü (9 CP) richtet sich insbesondere an Studierende der Mathematik [WPF MA, B 5 Modul 10, 11, 12 und M 1-2 (Modul M1D-ba), sowie Studenten der Elektrotechnik, Informatik, Mechanik, Physik und Wirtschaftswissenschaften als mathematisches Nebenfach.
Sie befasst sich mit deterministischen Scheduling-Problemen (auch Ablaufplanung, Maschinenbelegung oder Reihenfolgeprobleme genannt). Scheduling-Probleme treten in vielen Bereichen des täglichen Lebens auf, z.B. in der Betriebswirtschaft (Auftragsplanung z.B. in der Halbleiterproduktion, Lebensmittelherstellung oder in der Metallherstellungsindustrie), Logistik (z.B. Routen- uind Tourenplanung), Informatik (Abarbeitung von Tasks durch die Prozessoren eines Computersystems), im Servicebereich (z.B. Fahrplangestaltung bei der Bahn, Planung von Starts und Landungen auf einem Airport; Personaleinsatzplanung) oder im Geundheitswesen (Auflaufplanung in Krankenhäusern) auf.
Eine Menge von Aktivitäten (Jobs) ist auf einer Menge von Ressourcen (Maschinen) so auszuführen, dass ein optimaler Plan im Sinne eines vorgegebenen Optimierungskriteriums konstruiert wird. Schwerpunkt sind die Klassifikation und Komplexität von Scheduling-Problemen, mathematische Modelle sowie exakte und approximative Algorithmen zur Lösung von ein- und mehrstufigen Scheduling-Problemen. Die Vorlesung enthält auch eine kurze Einführung in das Programmpaket LiSA (A Library of Scheduling Algorithms) (das Paket ist frei downloadbar).
Im Gegensatz zu der für Studierende der Wirtschaftswissenschaften angebotenen Scheduling-Vorlesung ist diese Veranstaltung stärker theoretisch orientiert.

Gliederung

1. Grundlagen

2. Klassifizierung von deterministischen Scheduling-Problemen

3. Zur Komplexität von Scheduling-Problemen

4. Mathematische Modelle

5. Exakte Algorithmen

6. Konstruktive und iterative Heuristiken

7. Approximationsalgorithmen mit Gütegarantie

8. Spezielle Algorithmen für ausgewählte Scheduling-Probleme

8.1. Einmaschinenprobleme

8.2. Job-Shop Probleme

8.3. Verallgemeinerte Job-Shop Probleme

8.4. Ressourcenbeschränkte Projekt-Scheduling Probleme

---

Literatur

Liste mit Basis- und weiterführender Literatur: pdf

---

Vorlesungsmaterialien (Folien)

Kapitel 1 (pdf) (15 Seiten)

Kapitel 2 (pdf) (13 Seiten)

Kapitel 3 (pdf) (8 Seiten)

Kapitel 4 (pdf) (15 Seiten)

Kapitel 5 (pdf) (24 Seiten)

Kapitel 6 (pdf) (17 Seiten)

Kapitel 7 (pdf) (11 Seiten)

Kapitel 8 (pdf) (26 Seiten)

Übungsserien zur Vorlesung

Die Lösung der nachfolgend jeweils in Klammern angegebenen Aufgabe ist schriftlich zur Abgabe vorzubereiten.

Serie 1 (pdf) (Aufgabe 6)

Serie 2 (pdf) (Aufgabe 6)

Serie 3 (pdf) (Aufgabe 3)

Serie 4 (pdf) (Aufgabe 2)

Serie 5 (pdf) (Aufgabe 6)

Serie 6 (pdf) (Aufgabe 4)

Serie 7 (pdf) (Aufgabe 4)

Hinweis

Am Ende des Semesters wird eine Klausur im Umfang von 90 Minuten angeboten. Die erfolgreiche Teilnahme an der Klausur ist Voraussetzung für die Erteilung eines Übungsscheins (falls erforderlich). Eine Teilnehme wird auch empfohlen, wenn später eine Prüfung in diesem Gebiet erfolgen soll.

Zitat: I do not object to people looking at their watches when I am speaking. But I strongly object when they start shaking them to make certain they are still working.
(Lord Birkett)