Syllabus

Title
0353 Mathematical Methods I - Scheduling und Kombinatorische Optimierung
Instructors
ao.Univ.Prof. Dr. Walter Böhm
Contact details
Type
PI
Weekly hours
2
Language of instruction
Deutsch
Registration
09/20/21 to 10/01/21
Registration via LPIS
Notes to the course
Subject(s) Bachelor Programs
Dates
Day Date Time Room
Wednesday 10/06/21 08:00 AM - 10:00 AM TC.0.04
Wednesday 10/13/21 08:00 AM - 10:00 AM TC.0.03 WIENER STÄDTISCHE
Wednesday 10/20/21 08:00 AM - 10:00 AM TC.0.02 Red Bull
Wednesday 10/27/21 08:00 AM - 10:00 AM TC.0.04
Wednesday 11/03/21 08:00 AM - 10:00 AM TC.2.01
Wednesday 11/10/21 08:00 AM - 10:00 AM TC.2.01
Wednesday 11/17/21 08:00 AM - 10:00 AM TC.2.01
Wednesday 11/24/21 08:00 AM - 10:00 AM Online-Einheit
Wednesday 12/01/21 08:00 AM - 10:00 AM Online-Einheit
Wednesday 12/15/21 08:00 AM - 10:00 AM Online-Einheit
Wednesday 01/12/22 08:00 AM - 10:00 AM TC.0.02 Red Bull
Wednesday 01/19/22 08:00 AM - 10:00 AM TC.0.04

Contents

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, Approximationen
    • Heuristiken und Metaheuristiken

     

      Learning outcomes

      Dieser Kurs soll ihnen Grundkenntnisse vermitteln in folgenden Gebieten:

      • Sequencing und Scheduling
      • Kombinatorischer Optimierung
      • Graphentheorie
      • 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

      Attendance requirements

      Es besteht Anwesenheitspflicht in den Lehrveranstaltungen. Zwei Einheiten dürfen versäumt werden.

      Die Termine am 15. Dezember und 19. Januar sind Reservetermine für alle Fälle.

       

      Teaching/learning method(s)

      Acht Vortragseinheiten (Details siehe Lernen & Üben), in denen die Methoden präsentiert werden.

       

      Assessment

      Nach den Einheiten 3, 5 und 7 finden schriftliche Tests statt:

      1. Test: Kapitel 2 und 3, 27. Oktober, 9 bis 10 Uhr
      2. Test: Kapitel 4 und 5, 17.November, 9 bis 10 Uhr
      3. Test: Kapitel 6 und 7, 19. Januar, 9 bis 10 Uhr

      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 60 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

      Bei den Tests dürfen Sie elektronische Hilfsmittel verwenden. Sie sind sogar ausdrücklich eingeladen, selbst benötigte Algorithmen zu programmieren. Dafür empfehle ich R, eine universelle Rechenumgebung.

       

        Prerequisites for participation and waiting lists

        Absolvierung der Mathematik in der STEOP

        Readings

        1 Author: R. W. Conway, W. L. Maxwell, L. W. Miller
        Title: Theory of Scheduling


        Publisher: Dover
        Remarks: Das älteste Lehrbuch des Scheduling, etwas outdated, aber exzellenter Text, verhältnismäßig billig.
        Year: 1967
        2 Author: K. R. Baker, D. Trietsch
        Title: Principles of Sequencing and Scheduling


        Publisher: John Wiley and Sons
        Remarks: Sehr gutes, leicht verständliches Lehrbuch, leider nicht billig.
        Year: 2009
        3 Author: M. L. Pinedo
        Title: Scheduling: Theory, Algorithms and Systems


        Publisher: Springer
        Remarks: Nicht ganz leicht zu lesen, anspruchsvoll
        Year: 2012
        4 Author: R. G. Parker
        Title: Deterministic Scheduling Theory


        Publisher: CRC Press
        Year: 1995
        5 Author: P. Brucker, S. Knust
        Title: Complex Scheduling



        Publisher: Springer
        Year: 2011
        6 Author: P. Brucker
        Title: Scheduling Algorithms


        Publisher: Freier Download als pdf
        Remarks: users.utu.fiyurnikscheduling files/Scheduling Peter Brucker.pdf
        Year: 2007
        7 Author: M. Gondran und M. Minoux
        Title: Graphs and Algorithms


        Publisher: John Wiley and Sons
        Remarks: In der Bibliothek erhältlich
        Year: 1984
        8 Author: E. S. Lawler
        Title: Combinatorial Optimization: Networks and Matroids


        Publisher: Dover Books
        Year: 2001
        9 Author: A. Gibbons
        Title: Algorithmic Graph Theory


        Publisher: Cambridge University Press
        Year: 1985
        10 Author: N. Christofides
        Title: Graph Theory: An Algorithmic Approach


        Publisher: Academic Press
        Remarks: In der Bibliothek erhältlich
        Year: 1975
        11 Author: E. V. Denardo
        Title: Dynamic Programming: Models and Applications


        Publisher: Dover Books
        Year: 2003

        Recommended previous knowledge and skills

        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.

        Availability of lecturer(s)

        walter.boehm@wu.ac.at
        Last edited: 2021-09-17



        Back