Syllabus

Titel
0436 Mathematical Methods I - Scheduling und Kombinatorische Optimierung
LV-Leiter/innen
ao.Univ.Prof. Dr. Walter Böhm
Kontakt
  • LV-Typ
    PI
  • Semesterstunden
    2
  • Unterrichtssprache
    Deutsch
Anmeldung
09.09.2019 bis 27.09.2019
Anmeldung über LPIS
Hinweise zur LV
Planpunkt(e) Bachelor
Termine
Wochentag Datum Uhrzeit Raum
Dienstag 01.10.2019 08:00 - 10:00 TC.3.01
Dienstag 08.10.2019 08:00 - 10:00 TC.3.01
Dienstag 15.10.2019 08:00 - 10:00 TC.3.05
Dienstag 22.10.2019 08:00 - 10:00 D4.0.022
Dienstag 29.10.2019 08:00 - 10:00 TC.3.05
Dienstag 05.11.2019 08:00 - 10:00 TC.3.05
Dienstag 12.11.2019 08:00 - 10:00 TC.3.01
Dienstag 19.11.2019 08:00 - 10:00 TC.3.01
Dienstag 26.11.2019 08:00 - 10:00 TC.3.01
Dienstag 03.12.2019 08:00 - 10:00 TC.3.01
Dienstag 10.12.2019 08:00 - 10:00 TC.3.01
Dienstag 17.12.2019 08:00 - 10:00 TC.3.01

Inhalte der LV

Dieser Kurs bietet eine Einführung in die Kombinatorische Optimierung mit Schwerpunkt Scheduling.

Gegenstand des Scheduling sind Reihenfolge- und Allokationsprobleme:

  • In welcher Reihenfolge sollen bestimmte Aufgaben erledigt werden, z.B. Fertigungsschritte, Kundenbetreuung etc?
  • Welche und wieviel der vorhandenen Ressourcen verwenden wir für welche Aufgabe?

Diese Fragen sollen so beantwortet werden, dass gewisse Optimalitätskriterien erfüllt sind.

Scheduling-Aufgaben sind allgegenwärtig, hier einige Beispiele:

  • Produktionsmanagement: welche Verarbeitungsschritte sollen auf welchen Maschinen in welcher Reihenfolge erledigt werden, sodass Verspätungen in der Produktion so gering als möglich ausfallen?
  • Stundenpläne an Schulen und Universitäten: in welchem Hörsaal in welchem Zeitslot soll welcher Kurs angesetzt werden, sodass Studierenden eine kollisionsfreie Teilnahme an den Kursen möglich ist?
  • Klinikmanagement: was ist die ideale Abfolge der Operationsschritte z.B. bei einer Bypass-Operation? Welche Operationen sollen in welchem Zeitslot in welchem Operationssaal angesetzt werden, sodass die vorhandenen Einrichtungen ideal ausgelastet sind.
  • Medienmanagement: wieviel Werbezeit soll in welchem Medium zu welcher Zeit gebucht werden, um möglichst viele Kunden zu erreichen?
  • Sportmanagement: bei internationalen Bewerben wie z.B. im Fussball sollen die Termine der Events in idealer Weise gesetzt werden, sodass es keine Koillisionen gibt, Sponsorinteressen berücksichtigt werden, etc.

Scheduling ist ein sehr lebendiges und interessantes Teilgebiet der Kombinatorischen Optimierung.

Kombinatorische Optimierung befasst sich mit dem Problem, aus einer typischerweise endlichen Menge von Konfigurationen jene zu finden, für die eine bestimmte Zielfunktion optimal wird. Diese Konfigurationen können sehr vielfältig sein: die Reihenfolge, in der bestimmte Produktionsschritte erledigt werden, die Zuordnung von Aufgaben an Mitarbeiter, Standorte von Produktionsanlagen, Ersatzpläne für Anlagen, Transportpläne für Güter, etc. Diese Optimierungsaufgaben lassen sich nicht mit den Methoden der Differentialrechnung lösen, vielmehr sind neue, ganz besondere Techniken notwendig.

Die meisten Scheduling-Probleme gelten als ausserordentlich schwierig, nichtsdestoweniger sind es sehr interessante Aufgabenstellungen, die in der Praxis eine grosse Rolle spielen und deren Lösung substantielle betriebswirtschaftliche Vorteile bringt.

Das Angebot dieses Kurses richtet sich in erster Linie an Studierende, die vorhaben ihre Studien in Richtung Produktionsmanagement und Supply Chains bei Jammernegg und Taudes zu vertiefen. Für Studierende, die in Richtung Finance tendieren, ist dieser Kurs wenig geeignet.

Methodisch werden vier Linien verfolgt:

  • Graphentheorie
  • Dynamic Programming
  • Ganzzahlige lineare Optimierung, insbesondere disjunctive Programming
  • Heuristiken und Metaheuristiken


Lernergebnisse (Learning Outcomes)

Dieser Kurs soll ihnen Grundkenntnisse vermitteln in folgenden Gebieten:

  • Sequencing und Scheduling
  • Kombinatorischer Optimierung
  • Graphentheorie
  • Ganzzahlige Lineare Optimierung
  • Heuristiken und Metaheuristiken

Am Ende des Kurses sollte die Teilnehmerinnen in der Lage sein,einschlägige Fachliteratur zu diesen Themen zu lesen und zu verstehen und Bescheid zu wissen über

  • Basismethoden der kombinatorischen Optimierung
  • Klassische Scheduling-Probleme und ihre Lösung

Regelung zur Anwesenheit

Es besteht Anwesenheitspflicht in den Lehrveranstaltungen.

 

Lehr-/Lerndesign

Acht Vortragseinheiten (Details siehe unten), in denen die Methoden präsentiert werden.

 

Leistung(en) für eine Beurteilung

Nach den Einheiten 3, 6 und 8 finden schriftliche Tests statt:

  1. Test: Kapitel 1, 2 und 3
  2. Test: Kapitel 4 und 5
  3. Test: Kapitel 6 und 7

Bei jedem Test sind 3 Beispiele zu lösen, die aus den Übungsbeispielen zu den einzelnen Kapitel ausgewählt werden. Die dafür vorgesehene Arbeitszeit beträgt 45 Minuten.

Bewertung: für jedes Beispiel gibt es maximal einen Punkt. Die bei den drei Tests erreichten Punkte werden alle gleich gewichtet und ergeben in ihrer Summe eine Gesamtpunktezahl.

Aus der erreichten Gesamtpunktezahl errechnet sich die Abschlussnote nach dem Schlüssel:

  • mindestens 5, aber < 6: genügend
  • mindestens 6, aber < 7: befriedigend
  • mindestens 7, aber < 8: gut
  • mindestens 8: sehr gut

 

Erlaubte Hilfsmittel

Sie dürfen einen nichtprogrammierbaren Taschenrechner werwenden. Laptops, Smartphones etc. sind nicht erlaubt.

Falls ein Test versäumt wird, steht ein Zusatztermin zur Verfügung:

    Literatur

    1 Autor/in: R. W. Conway, W. L. Maxwell, L. W. Miller
    Titel: Theory of Scheduling


    Verlag: Dover
    Anmerkungen: Das älteste Lehrbuch des Scheduling, etwas outdated, aber exzellenter Text, verhältnismäßig billig.
    Jahr: 1967
    2 Autor/in: K. R. Baker, D. Trietsch
    Titel: Principles of Sequencing and Scheduling


    Verlag: John Wiley and Sons
    Anmerkungen: Sehr gutes, leicht verständliches Lehrbuch, leider nicht billig.
    Jahr: 2009
    3 Autor/in: M. L. Pinedo
    Titel: Scheduling: Theory, Algorithms and Systems


    Verlag: Springer
    Anmerkungen: Nicht ganz leicht zu lesen, anspruchsvoll
    Jahr: 2012
    4 Autor/in: R. G. Parker
    Titel: Deterministic Scheduling Theory


    Verlag: CRC Press
    Jahr: 1995
    5 Autor/in: P. Brucker, S. Knust
    Titel: Complex Scheduling



    Verlag: Springer
    Jahr: 2011
    6 Autor/in: P. Brucker
    Titel: Scheduling Algorithms


    Verlag: Freier Download als pdf
    Anmerkungen: users.utu.fiyurnikscheduling files/Scheduling Peter Brucker.pdf
    Jahr: 2007
    7 Autor/in: M. Gondran und M. Minoux
    Titel: Graphs and Algorithms


    Verlag: John Wiley and Sons
    Anmerkungen: In der Bibliothek erhältlich
    Jahr: 1984
    8 Autor/in: E. S. Lawler
    Titel: Combinatorial Optimization: Networks and Matroids


    Verlag: Dover Books
    Jahr: 2001
    9 Autor/in: A. Gibbons
    Titel: Algorithmic Graph Theory


    Verlag: Cambridge University Press
    Jahr: 1985
    10 Autor/in: N. Christofides
    Titel: Graph Theory: An Algorithmic Approach


    Verlag: Academic Press
    Anmerkungen: In der Bibliothek erhältlich
    Jahr: 1975
    11 Autor/in: E. V. Denardo
    Titel: Dynamic Programming: Models and Applications


    Verlag: Dover Books
    Jahr: 2003

    Teilnahmevoraussetzung(en) und Vergabe von Wartelistenplätzen

    Absolvierung der Mathematik in der STEOP

    Empfohlene inhaltliche Vorkenntnisse

    Es sind keine besonderen mathematischen Vorkenntnisse notwendig. Allerdings ist dies ein Mathematik-Kurs, d.h. eine gewisse Belastbarkeit und vor allem Interesse an der Mathematik wird bei den Teilnehmerinnen und Teilnehmern vorausgesetzt.

    Erreichbarkeit des/der Vortragenden

    walter.boehm@wu.ac.at

    Detailinformationen zu einzelnen Lehrveranstaltungseinheiten

    Einheit Datum Inhalte
    1

    1. Kapitel

    Eine Einführung

    • Die Rolle der Zeit in der Produktionsplanung
    • Ein paradoxes Scheduling-Problem: die Produktion von Fahrrädern
    • Die Eigenheiten der Kombinatorischen Optimierung
    • Komplexität: über die Tractablility von Scheduling Problemen
    • Vorstellung der Inhalte, Organisation der LV, Literatur
    2

    2. Kapitel

    Graphentheorie

    • Graphen und Netzwerke - Grundbegriffe
    • Präzedenzgraphen in der Produktion
    • Pfade und Zyklen
    • Bäume und Wälder
    • DAGs - directed acyclic graphs
    • Topologisches Sortieren von DAGs
    • kürzeste und längste Pfade - Dynamic Programming
    • Kritische Pfade und Makespan
    3

    3. Kapitel

    1-Maschinen Scheduling, 1. Teil

    • Performance Maße im Scheduling 
    • Fertigstellungszeiten - die SPT- und WSPT- Regel von Smith
    • Completion Times und Release Dates
    • Makespan Probleme, die ERD-Regel
    • Due Dates, totale und maximale Lateness, die EDD-Regel
    • Der Algorithmus von Lawler
    • Tardiness - Verspätungen
    • Die Anzahl der verspäteten Jobs - der Algorithmus von Moore
    4

    1. Test

    5

    4. Kapitel

    1-Maschinen Scheduling, 2. Teil

    • Totale Tardiness und Dynamic Programming
    • Das Assignment Problem und der Ungarische Algorithmus
    • Totale Tardiness bei konstanten Prozesszeiten
    • Abhängige Jobs - Ketten
    • Lawler's Algorithmus
    6

    5. Kapitel

    Parallele Maschinen

    • Makespan und Lastausgleich
    • List Processing
    • Die Knuth-Kleitman Regel
    • Grahams Bound für das parallele Maschinen Problem
    • Longest Processing Times
    • Bin Packing und die Multifit Heuristik
    • Totale Fertigstellungszeiten als Performance Maß
    • Parallele Maschinen und abhängige Jobs
    • Die Critical Path Methode
    • Die Lösung für das Fahrrad-Problem
    • Intrees und Hu's Algorithmus
    7

    6. Kapitel

    Sequencing in Flow Shops

    • Architektur und Charakteristika von Flow Shops
    • Performancemaße: Makespan und totale Fertigstellungszeit
    • Permutations-Flow Shops
    • Drei grundlegende Eigenschaften
    • Johnsons Algorithmus für 2-Maschinen Flow Shops
    • Die Heuristik von Gupta
    • Proportionale Flow Shops
    • Grundlagen der Ganzzahligen Linearen Optimierung
    • Formulierung und Lösung des Flow Shop-Problems als ganzzahliges LP
    • Einfaches Assembly Line Balancing - optimale Zykluszeit
    8

    2. Test

    9

    7. Kapitel

    Open Shops und Jobs Shops

    • Definitionen und Problemstellung
    • Der Schedule eines Open Shops, die LAPT-Regel
    • Konstante Prozesszeiten und Lateinische Quadrate
    • Job Shops und Disjunctive Graphs
    • Lösung mittels ganzahliger linearer Programme
    • Johnson’s 2-Maschinen Job Shop
    10

    8. Kapitel

    Local Search und Metaheuristiken

    • Metaheuristiken - Begriffbestimmung
    • Datenstrukturen
    • Random Sampling
    • Local Search
    • Tabu Search
    • Simulated Annealing
    • Genetische Algeorithmen

     

    11

    3. Test

     

    Zuletzt bearbeitet: 21.08.2019



    Zurück