Sprungmarken

Servicenavigation

Hauptnavigation

Sie sind hier:

Hauptinhalt

Schedulingprobleme - Algorithmen und Anwendungen

Please find the English version below

Schedulingprobleme - Algorithmen und Anwendungen

 

Die Veranstaltung findet in englischer Sprache statt.

 

Interessierte Studierende melden sich bitte im LSF an. Dabei ist zu beachten, dass sich alle Studierende - egal welcher Fachrichtung - ausschließlich bei der LSF-Veranstaltung 080385 mit der Bezeichnung "Scheduling Problems and Solutions", Vorlesung, eintragen mögen. Es werden nur Teilnehmer dieser Veranstaltung vom LSF in den Moodle-Arbeitsraum als Teilnehmer übertragen.

Durch Ihre Anmeldung im LSF können Sie an der Veranstaltung in Moodle in digitaler Form teilnehmen. Für das Einführungskapitel stehen schon Folien und Videos in Moodle zur Verfügung.

 

Für die weiteren Ankündigungen im Rahmen dieser Vorlesung wird ausschließlich Moodle genutzt.
 

Vorlesung

Dozent Ort Zeit Beginn
Prof. Dr.-Ing. Uwe Schwiegelshohn BCI ZB-E04 Dienstag, 10.15 - 12.00 Uhr 21.04.2020
BCI HS-ZE02 Mittwoch, 10.15 - 12.00 Uhr 22.04.2020

 

Übung und Praktikum

Dozent Ort Zeit Beginn
Ganesh Nileshwar Übung
BCI ZB-E04 Donnerstag, 10.15 - 12.00 Uhr 23.04.2020
Ganesh Nileshwar Praktikum
P1-01-108 (Retina Pool) Praktikum an drei Terminen im Semester: N.N. xx.xx.2020

 

Unterstützungsmaterial

Sie können die Folien der Vorträge herunterladen. Solange Sie nicht persönlich am Vortrag im Hörsaal teilnehmen können, erhalten Sie einen Diavortrag mit Audiokommentaren. Während der ersten zwei Wochen haben Sie zwei Alternativen: Sie können entweder eine mp4-Datei oder eine ppsx-Datei herunterladen. Für letztere benötigen Sie einen kostenlosen Powerpoint-Viewer oder Powerpoint. Als Student können Sie entweder Office365Pro für 5 EUR pro Monat oder Office365Cloud kostenlos erhalten. Die Universität verlangt von uns die Verwendung von ppsx, da mp4 einen wesentlich größeren Speicherbedarf hat. Daher haben Sie zwei Wochen Zeit, um mindestens einen Powerpoint-Viewer zu erhalten. Danach wird es nur noch ppsx-Dateien geben.

 

Lehrinhalte

Die Vorlesung orientiert sich an dem Buch: Michael Pinedo (New York University), "Scheduling Theory, Algorithms, and Systems", Springer 4th edition 2012, ISBN 1461419867

 

  • Introduction to the lecture and the topic
    1. Organization
    2. Scheduling Language
    3. Classes of Schedules
    4. Complexity

  • Single machine environment
    1. Makespan and total weighted completion time
    2. Lateness and tardy jobs
    3. Total tardiness and  total earliness and tardiness
    4. Online  problems
    5. Bicriterial problems

  • Parallel machine environments
    1. Makespan
    2. Total weighted completion time and lateness
    3. Online problems

  • Shop systems
    1. Flow shop
    2. Job shop and open shop
     

     

Präsenzübungen

Zur Unterstützung der Übungsinhalte werden unregelmäßig Präsenzübungsblätter verteilt, die von den Teilnehmern vorbereitet und in der Übung gemeinsam gelöst werden sollen.

 

Prüfungen

Für den Erwerb der  Credit Punkte müssen die Praktikumsaufgaben erfolgreich bearbeitet werden  und die abschließende mündliche Prüfung (20 - 40 Minuten) bestanden werden.

 

Weiterführende Literatur

  • M.R. Garey and D.S. Johnson, "Computers and Intractability", W. H. Freeman
  • A.S. Schulz and M. Skutella, "The power of a-points in preemptive single machine scheduling", Journal of Scheduling, 5:121–133, 2002.
  • H. Hoogeveen and A.P.A. Vestjens, "Optimal on-line algorithms for single-machine scheduling", in 5th International Integer Programming and Combinatorial Optimization Conference, LNCS 1084:404–414. Springer, 1996.
  • E.J. Anderson and C.N. Potts, "Online scheduling of a single machine to minimize total weighted completion time", Mathematics of Operations Research, 29(3):686–697, 2004.
  • M. Goldwasser, "Patience is a virtue: The effect of slack on the competitiveness for admission control",  Journal of Scheduling, 6:193-211, 2003
  • B. DasGupta and M. Palis, "Online real-time preemptive scheduling of jobs with deadlines on multiple machines", Journal of Scheduling, 4:297-312, 2001
  • E.L. Lawler, "A dynamic programming algorithm for preemptive scheduling of a single machine to minmize the number of late jobs", Annals of Operations Research, 26:125-133,1990
  • J.K. Lenstra and A.H.G. Rinnooy Khan, "Scheduling chains on a single machine", European Journal of Operation Research, 4:270-275, 1980

 

English Version

 

 

Scheduling Problems and Solutions

The language of the lecture is English.

If you are interested in listening to the lecture then please sign on using LSF.

Please note that all interested students independent of the study program must sign on for the LSF-course 080385 entitled "Scheduling Problems and Solutions". Only participants of this course are automatically transferred as participants into the Moodle workspace. Do not use any version of this course from a previous year.

 

We will exclusively use Moodle for any further announcements regarding this course.

  

Lecture

Lecturer Room Time Start
Prof. Dr.-Ing. Uwe Schwiegelshohn BCI-ZE-ZB04 Tuesday, 10.15 - 12.00 h 21.04.2020
BCI-HS-ZE02 Wednesday, 10.15 - 12.00 h 22.04.2020

 

Tutorial and Lab Course

Lecturer Room Time Start
Ganesh Nileshwar BCI-ZE-ZB04 Thursday, 10.15 - 12.00 h 23.04.2020
IRF Pool Three lab course meetings. Meeting times will be announced later.

 

Support Material

You can download slides of the lectures. As long as you are not allowed to personally join the lecture in the lecture hall, you will receive a slide stream with audio comments. During the first two weeks, you have two alternatives: you can either download an mp4 file or a ppsx file. For the latter, you need a free powerpoint viewer or powerpoint. As a student you can obtain either Office365Pro for  5 EUR a month or Office365Cloud for free. The university requires us to use ppsx since mp4 has a significantly larger memory footprint. Therefore, you have two weeks time to obtain at least a powerpoint viewer. Afterwards, there will only be ppsx files.

 

Content

The lecture is mainly based upon the textbook: Michael Pinedo (New York University), "Scheduling Theory, Algorithms, and Systems", Springer 4th edition 2012, ISBN 1461419867

 

  • Introduction to the lecture and the topic
    1. Organization
    2. Scheduling Language
    3. Classes of Schedules
    4. Complexity
  • Single machine environment
    1. Makespan and total weighted completion time
    2. Lateness and tardy jobs
    3. Total tardiness and  total earliness and tardiness
    4. Online  problems
    5. Bicriterial problems
  • Parallel machine environments
    1. Makespan
    2. Total weighted completion time and lateness
    3. Online problems
  • Shop systems
    1. Flow shop
    2. Job shop and open shop

  

Tutorials

To support the contents of the exercise, presence exercise sheets are distributed at irregular intervals, which are to be prepared by the participants and solved together in the exercise.

 

Exams

In order to obtain the credit points, the internship tasks must be successfully completed and the final oral examination (20 - 40 minutes) must be passed.

  

Additional Literature

  • M.R. Garey and D.S. Johnson, "Computers and Intractability", W. H. Freeman
  • A.S. Schulz and M. Skutella, "The power of a-points in preemptive single machine scheduling", Journal of Scheduling, 5:121–133, 2002.
  • H. Hoogeveen and A.P.A. Vestjens, "Optimal on-line algorithms for single-machine scheduling", in 5th International Integer Programming and Combinatorial Optimization Conference, LNCS 1084:404–414. Springer, 1996.
  • E.J. Anderson and C.N. Potts, "Online scheduling of a single machine to minimize total weighted completion time", Mathematics of Operations Research, 29(3):686–697, 2004.
  • M. Goldwasser, "Patience is a virtue: The effect of slack on the competitiveness for admission control",  Journal of Scheduling, 6:193-211, 2003
  • B. DasGupta and M. Palis, "Online real-time preemptive scheduling of jobs with deadlines on multiple machines", Journal of Scheduling, 4:297-312, 2001
  • E.L. Lawler, "A dynamic programming algorithm for preemptive scheduling of a single machine to minmize the number of late jobs", Annals of Operations Research, 26:125-133,1990
  • J.K. Lenstra and A.H.G. Rinnooy Khan, "Scheduling chains on a single machine", European Journal of Operation Research, 4:270-275, 1980


Nebeninhalt

Veranstaltungsnummern

080385, 080386 und 080395

für die Master-Studiengänge ET/IT und A&R:

Modul 2-16, ETIT-235 und Modul AR-202

4V + 2Ü + 1P AQA

10 Credits

für die Master-Studiengänge der Informatik:

Modul INF-MSc-612

3V + 1Ü

6 Credits