Scheduling Problems and Solutions

Aktuelle Informationen im Zusammenhang mit der Vorlesung, Übung und Prüfungen (Termine) werden ausschließlich über Moodle veröffentlicht. Des Weiteren dient der Moodle-Arbeitsraum mit seinen vielfältigen Kommunikationsmöglichkeiten (Chat, Mailinglisten, Forum etc.) dem kollaborativen Arbeiten im Rahmen der Vorlesung.

Interessierte Studierende melden sich bitte im LSF an.  Es werden nur Teilnehmer, die sich im LSF angemeldet haben, automatisch vom LSF in den Moodle-Arbeitsraum übertragen. Für die weiteren Ankündigungen im Rahmen der Vorlesung und der Übung wird ausschließlich Moodle genutzt.

Für das Fach "Scheduling Problems and Solutions" müssen von den Studierenden folgende Prüfungsleistungen erbracht werden:

• Erfolgreiche Bearbeitung des Praktikums (nicht für Studierende der Informatik)
• Erfolgreiche Teilnahme an der mündlichen Prüfung

• Veranstaltungsnummern:
  • Vorlesung: 08 0385
  • Übung: 08 0386
  • Praktikum: 08 0387
• 3. Semester im Master ET/IT und A&R
  • Umfang SWS: 4 V, 2 Ü, 1 P
  • Credits: 10
  • Modul 2-16, ETIT-235 bzw. AR-202
• 2. / 3. Semester in Master-Studiengängen der Informatik
  • Modultitel: Schedulingprobleme - Algorithmen und Anwendungen
  • Umfang SWS: 3 V, 1 Ü
  • Credits: 6
  • Modul INF-MSc-612
  • Für Studierende der Informatik ist die Teilnahme am Praktikum freiwillig. Außerdem dürfen sie sich für eins der Themen Parallel Machines und Shop Problems entscheiden, während das Thema Single Machines verpflichtend ist.

Die Vorlesung basiert größtenteils auf:

Michael Pinedo (New York University), "Scheduling Theory, Algorithms, and Systems", Springer 4th edition 2012, ISBN 1461419867

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 parallel machines", 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.