apl. Prof. Dr. Frank Werner

Otto-von-Guericke Universität Magdeburg

Institut für Mathematische Optimierung


Download
 
Kontakt Publikationen Aktivitäten & Interessen Lehre Betreuung Laufbahn & Projekte Private Links
 
  
 

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

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



Neu:

Ab Wintersemester 2017/18 findet diese Lehrveranstaltung im Umfang von 6 Stunden je Woche (4 h Vorlesung und 2 h Übung) statt.



Neu:

Die Übungen beginnen am 19. Oktober 2017.



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.

Diese Lehrveranstaltung ist wieder im Lehrangebot im Wintersemester 2019/20.



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)



<frank.werner@mathematik.uni-magdeburg.de>

  
English version Last updated: 14 Dec 2017