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.

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 05.04.2022
BCI HS-ZE02 Mittwoch, 10.15 - 12.00 Uhr 06.04.2022

 

Übung und Praktikum

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

 

Unterstützungsmaterial

Im Moodle-Arbeitsraum der Vorlesung wird Unterstützungsmaterial in Form von Vorlesungsfolien, Streams der Vorlesung und Übungsmaterial zur Verfügung gestellt.

 

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

    Dies ist eine Liste von Publikationen, die Problemlösungen für die in der Vorlesung behandelten Probleme beschreiben. Diese Veröffentlichungen werden empfohlen, wenn Sie an zusätzlichen Informationen zu diesen Problemen und ihren Lösungen interessiert sind. Sie sind für die Prüfung nicht erforderlich.

    Die Publikationen sind nach dem Datum der Veröffentlichung geordnet.

    • U. Schwiegelshohn, “An alternative proof of the Kawaguchi–Kyan bound for the Largest-Ratio-First rule,” Operations Research Letters, 39(4):255–259, 2011
    • P. Liu and X. Lu, "On-line scheduling of parallel machines to minimize total completion times", Computers & Operations Research, 36:2647-2652, 2009.
    • S. Leonardi and D. Raz, "Approximating total flow time on parallelmachines", Journal of Computer and System Sciences, 73(6):875–891,2007.
    • 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.
    • J. F. Rudin III and R. Chandrasekaran, "Improved bound for the online scheduling problem",
      SIAM Journal on Computing, 32:717–735, 2003.
    • M. Goldwasser, "Patience is a virtue: The effect of slack on the competitiveness for admission control",  Journal of Scheduling, 6:193-211, 2003.
    • L. Epstein and R. van Stee, "Lower bounds for on-line single-machine scheduling", Theoretical Computer Science, 299:439-450, 2003.
    • R. van Stee and H.L. Poutre, "Minimizing the total completion time on-line on a single machine, using restarts", Proceedings of the European Symposium of Algorithms, Springer, LNCS 2461, 872–883, 2002.
    • A.S. Schulz and M. Skutella, "The power of a-points in preemptive single machine scheduling", Journal of Scheduling, 5:121–133, 2002.
    • B. DasGupta and M. Palis, "Online real-time preemptive scheduling of jobs with deadlines on multiple machines", Journal of Scheduling, 4:297-312, 2001.
    • P. Berman, M. Charikar, and M. Karpinski, "On-line load balancing for related machines", Journal of Algorithms, 35:108–121, 2000.
    • S. Albers, "Better bounds for online scheduling", SIAM Journal on Computing, 29:459–473. 1999.
    • 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.
    • D. B. Shmoys, J. Wein, D.P. Williamson, “Scheduling Parallel Machines On-line”, SIAM Journal on Computing, 24(6):1313-1331, 1995.
    • J. Du, J.Y.-T. Leung,  and G.H. Young, "Scheduling Chain-Structured Tasks to Minimize Makespan and Mean Flow Time", Information and Computation 92:219-236, 1991
    • K.R. Baker and G.D. Scudder, "Sequencing with Earliness and Tardiness Penalties: A Review", Operations Research, 38:22-36, 1990.
    • 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.
    • U Faigle, W. Kern, and G. Turan, "On the performance of on-line algorithms for particular problems", Acta Cybernetica, 9:107-119, 1989.
    • T. Kawaguchi and S. Kyan, "Worst case bound of an LRF schedule for the meanweighted flow-time problem", SIAM Journal of Computing, 15(4):1119–1129, 1986.
    • J.K. Lenstra and A.H.G. Rinnooy Khan, "Scheduling chains on a single machine", European Journal of Operation Research, 4:270-275, 1980.
    • M.R. Garey and D.S. Johnson, "Computers and Intractability", W. H. Freeman, 1979.
    • E.L. Lawler and J. Labetoulle, "On preemptive scheduling of unrelated parallel processors by linear programming", Journal of the Assoc. Comput. Mach., 25(4), 612-619, 1978.
    • M.R. Garey and D.S. Johnson, "Strong NP-completeness results: motivation, examples, and implications",  Journal of the  Assoc. Comput. Mach., 25(3):499-508, 1978
    • E.L. Lawler, "Sequencing jobs to minimize total weighted completion time subject to precedence constraints",  Annals of Discrete Mathematics, 2:75-90,1978
    • J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker, "Complexity of machine scheduling problems"  Annals of Discrete Mathematics, 1:343-362, 1977
    • J.D. Ullman, "NP-Complete Scheduling Problems", Journal of Computer and System Sciences, 10:384-393, 1975.
    • J. Bruno, E.G. Coffman Jr., and R. Sethi, "Scheduling Independent Tasks To Reduce Mean Finishing Time", Communications of the Assoc. Comput. Mach., 17(7): 387-382, 1974
    • E.G. Coffman Jr. and R. L. Graham, "Optimal Scheduling for Two-processor Systems",  Acta Informatica, 1(3):200-213, 1971
    • E.L.Lawler and J.M. Moore, "A Functional Equation and Its Application to Resource Allocation and Sequencing Problems", Management Science, 16:77-89, 1969.

     

     

    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 05.04.2022
    BCI-HS-ZE02 Wednesday, 10.15 - 12.00 h 06.04.2022

     

     

    Tutorial and Lab Course

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

     

    Support Material

    We provide slides of the lecture, streams of the lecture as well as tutorial tasks and solutions in the moodle workspace.

     

    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

      This is a list of publications that describe original solutions to problems addressed in the lecture. These publications are recommended if you are interested in additional information on these problems and their solutions. They are not required for the exam.

      The publications are ordered using the date of publication.

      • U. Schwiegelshohn, “An alternative proof of the Kawaguchi–Kyan bound for the Largest-Ratio-First rule,” Operations Research Letters, 39(4):255–259, 2011
      • P. Liu and X. Lu, "On-line scheduling of parallel machines to minimize total completion times", Computers & Operations Research, 36:2647-2652, 2009.
      • S. Leonardi and D. Raz, "Approximating total flow time on parallelmachines", Journal of Computer and System Sciences, 73(6):875–891,2007.
      • 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.
      • J. F. Rudin III and R. Chandrasekaran, "Improved bound for the online scheduling problem",
        SIAM Journal on Computing, 32:717–735, 2003.
      • M. Goldwasser, "Patience is a virtue: The effect of slack on the competitiveness for admission control",  Journal of Scheduling, 6:193-211, 2003.
      • L. Epstein and R. van Stee, "Lower bounds for on-line single-machine scheduling", Theoretical Computer Science, 299:439-450, 2003.
      • R. van Stee and H.L. Poutre, "Minimizing the total completion time on-line on a single machine, using restarts", Proceedings of the European Symposium of Algorithms, Springer, LNCS 2461, 872–883, 2002.
      • A.S. Schulz and M. Skutella, "The power of a-points in preemptive single machine scheduling", Journal of Scheduling, 5:121–133, 2002.
      • B. DasGupta and M. Palis, "Online real-time preemptive scheduling of jobs with deadlines on multiple machines", Journal of Scheduling, 4:297-312, 2001.
      • P. Berman, M. Charikar, and M. Karpinski, "On-line load balancing for related machines", Journal of Algorithms, 35:108–121, 2000.
      • S. Albers, "Better bounds for online scheduling", SIAM Journal on Computing, 29:459–473. 1999.
      • 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.
      • D. B. Shmoys, J. Wein, D.P. Williamson, “Scheduling Parallel Machines On-line”, SIAM Journal on Computing, 24(6):1313-1331, 1995.
      • J. Du, J.Y.-T. Leung,  and G.H. Young, "Scheduling Chain-Structured Tasks to Minimize Makespan and Mean Flow Time", Information and Computation 92:219-236, 1991
      • K.R. Baker and G.D. Scudder, "Sequencing with Earliness and Tardiness Penalties: A Review", Operations Research, 38:22-36, 1990.
      • 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.
      • U Faigle, W. Kern, and G. Turan, "On the performance of on-line algorithms for particular problems", Acta Cybernetica, 9:107-119, 1989.
      • T. Kawaguchi and S. Kyan, "Worst case bound of an LRF schedule for the meanweighted flow-time problem", SIAM Journal of Computing, 15(4):1119–1129, 1986.
      • J.K. Lenstra and A.H.G. Rinnooy Khan, "Scheduling chains on a single machine", European Journal of Operation Research, 4:270-275, 1980.
      • M.R. Garey and D.S. Johnson, "Computers and Intractability", W. H. Freeman, 1979.
      • E.L. Lawler and J. Labetoulle, "On preemptive scheduling of unrelated parallel processors by linear programming", Journal of the Assoc. Comput. Mach., 25(4), 612-619, 1978.
      • M.R. Garey and D.S. Johnson, "Strong NP-completeness results: motivation, examples, and implications",  Journal of the  Assoc. Comput. Mach., 25(3):499-508, 1978
      • E.L. Lawler, "Sequencing jobs to minimize total weighted completion time subject to precedence constraints",  Annals of Discrete Mathematics, 2:75-90,1978
      • J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker, "Complexity of machine scheduling problems"  Annals of Discrete Mathematics, 1:343-362, 1977
      • J.D. Ullman, "NP-Complete Scheduling Problems", Journal of Computer and System Sciences, 10:384-393, 1975.
      • J. Bruno, E.G. Coffman Jr., and R. Sethi, "Scheduling Independent Tasks To Reduce Mean Finishing Time", Communications of the Assoc. Comput. Mach., 17(7): 387-382, 1974
      • E.G. Coffman Jr. and R. L. Graham, "Optimal Scheduling for Two-processor Systems",  Acta Informatica, 1(3):200-213, 1971
      • E.L.Lawler and J.M. Moore, "A Functional Equation and Its Application to Resource Allocation and Sequencing Problems", Management Science, 16:77-89, 1969.

       



      Nebeninhalt

      Kontakt

      M. Sc. Ganesh Kamath Nileshwar
      Tel.: 0231 755-4513

      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

      10 Credits

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

      Modul INF-MSc-612

      3V + 1Ü

      6 Credits