Informatik-Logo
Fakultät für Informatik - Technische Universität München

Lehrstuhl für Effiziente Algorithmen

TUM-Logo


Hauptseminar im SS 2003:
Scheduling

Termin: Donnerstag, 14:15-15:45 Uhr
Raum: MI 03.11.018.

Im Sommersemester 2003 veranstaltet der Lehrstuhl für Effiziente Algorithmen ein Hauptseminar zum Thema "Scheduling".
Darunter versteht man die Problematik der Zuordnung von Ressourcen zu Benutzern oder Jobs vor dem Hintergrund der Optimierung einer bestimmten Zielfunktion. Dies kann im einfachsten Fall die Zeit bis zur Beendigung des letzten Jobs sein, aber auch andere Zielfunktionen, wie z.B. die gewichtete Summe der Zeiten zwischen Ankunft und Fertigstellung der Aufgaben, sind denkbar.
Wir betrachten die theoretischen Grundlagen von Scheduling-Algorithmen mit unterschiedlichsten Anforderungen. Das betrifft die Anzahl der Maschinen, die Unterbrechbarkeit, Abhängigkeiten in der Bearbeitungsreihenfolge, die Möglichkeit der Ankunft neuer Jobs (Online-Algorithmen), Wahrscheinlichkeitsverteilungen der Ankunfts- und Bearbeitungszeiten, Echtzeitanforderungen, sowie im Multiprozessortask-Scheduling vor allem die Topologie der Vernetzung der Prozessoren (z.B. Line, Mesh, Hypercube und andere). Weiterhin werden aktuelle Forschungsthemen wie Hyperthread-Scheduling und Broadcast-Scheduling eine Rolle spielen. Es ergeben sich damit zwangsläufig auch Berührungspunkte zu den Fachgebieten Betriebssysteme, Netzwerke und Rechnerarchitekturen.
[Termine] [Literatur] [Hinweise]
Seminarleitung: Hanjo Täubig


Termin Thema Vortragender
17. April 2003 Klassifikation von Scheduling-Problemen und -Algorithmen, 1-Prozessor-Scheduling Steffi Lämmle
24. April 2003 Tutorial - Suche nach relevanten wiss. Publikationen, Internetsuchmaschinen und Digital Libraries -
1. Mai 2003 (Maifeiertag)
8. Mai 2003 Scheduling für mehrere parallele Prozessoren
stattdessen: Tutorial - Erstellung wiss. Publikationen mit LaTeX
Abdelmounaime Barzali
15. Mai 2003 Scheduling mit Kommunikationskosten
stattdessen: Tutorial - LaTeX-Publikationen mit dem Springer LNCS-Style
Yanyan Huang
22. Mai 2003 JobShop Scheduling
stattdessen: Vorstellung des Scheduling-Simulationstools Sketch-it!
Hassan Soubeity
29. Mai 2003 (Christi Himmelfahrt)
5. Juni 2003
12. Juni 2003 OpenShop / FlowShop Scheduling Alexander Kruppa
19. Juni 2003 (Fronleichnam)
26. Juni 2003 DA-Vortrag: Simulation of Algorithms for Stochastic Scheduling Problems Bertolt Meier
3. Juli 2003 Scheduling von Multiprozessor-Task Patrick Löffler
10. Juli 2003 Stochastische Scheduling-Probleme Matthias Rahlf

Vorläufige Teilnehmerliste


Themen & Literatur

Die detaillierte Themenliste mit Literaturangaben finden Sie hier.


Seminarvorgaben

* Ein Schein für die erfolgreiche Teilnahme am Hauptseminar wird vergeben, wenn folgende Leistungen erbracht worden sind:
Probevortrag (ohne Bewertung) Der Probevortrag erfolgt spätestens 10 Tage vor dem Seminarvortrag beim Betreuer. Vorzulegen sind dabei die fertig ausgearbeiteten Folien oder ähnliche Präsentationshilfsmittel und die Erstfassung der Seminarbeit.
Vereinbaren Sie für den Probevortrag rechtzeitig einen Termin beim Betreuer (spätestens eine Woche vor dem anvisierten Termin).
Seminarvortrag (in mindestens zufriedenstellender Qualität) Der Seminarvortrag ist zum festgelegten Termin zu halten und dauert 60 (+/-5) Minuten. Tafelvorträge werden nicht akzeptiert. Nach dem Vortrag muss auf Fragen aus dem Publikum eingegangen werden.
Seminararbeit (in mindestens zufriedenstellender Qualität) Die Endfassung der Seminarbeit ist spätestens am 10.7.2003 zum letzten Seminarvortrag als TeX-Datei und Postscript-Datei abzugeben. Der Umfang der Seminararbeit beträgt 10 (+/- 1) Seiten (ohne Literaturverzeichnis) im LNCS-Style (Springer-Verlag) unter LaTeX (Hinweise siehe unten). Außer der ausgeteilten Literatur sind mindestens 5 weitere relevante Literaturquellen zu verarbeiten.

Hinweise zur Anfertigung einer Seminararbeit

* Die Seminararbeiten werden nach der letzten Seminarveranstaltung gemeinsam in einem Seminarband als Technischer Bericht der Fakultät für Informatik der TU München veröffentlicht. Damit eine einheitliche Form erzielt wird, müssen alle Ausarbeitungen mit dem Textsatzsystem LaTeX erstellt werden. Hierzu sind folgende Richtlinien zu beachten:
  • Es ist der LNCS-Style (die Datei llncs.cls) des Springer-Verlages zu verwenden.
  • Der folgende Rahmen ist zu verwenden (seminararbeit.tex). Dabei dürfen die Seitengröße und der Font nicht verändert werden.
  • Ein Beispiel kann in der Datei example.tex gefunden werden (das Bild example.eps wird eingebunden)
  • Die Ausarbeitung soll auf die verwendete Literatur verweisen, diese Literatur ist mit BibTeX zu verwalten und in einer eigenen Datei zu speichern (hier die zum Beispiel gehörende Datei: example.bib).
* Bei Fragen zu LaTeX sei einerseits auf die folgenden Links hingewiesen, ferner kann auch der Betreuer um Hilfestellungen bzw. Literaturangaben gebeten werden.
* Eine weitere Anleitung zur Erstellung von Ausarbeitungen finden sie hier.

Hinweise zur Gestaltung der Seminarvorträge

* Merkblatt zur Gestaltung eines Seminarvortrags. (Die Tipps auf diesem Merkblatt sind keine offiziellen Anforderungen oder Bewertungskriterien der TU München, sondern aus der Praxis eines Seminarleiters heraus entstandene Ratschläge.)
* Tipps zur Erstellung von Folien mit LaTeX (einschließlich Rahmen-Datei als Vorlage)


Weitere Auskünfte bei Hanjo Täubig.


Letzte Änderung: Hanjo Täubig am 3.7.2003