LEA
Institut für Informatik der Technischen Universität München
Lehrstuhl für Effiziente Algorithmen
Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Systementwicklungsprojekt / Diplomarbeit

Entwurf eines Frameworks für Scheduling-Algorithmen


Bei Scheduling-Problemen beschäftigt man sich mit der Frage, wie Jobs in einem System von parallelen Maschinen optimal abgearbeitet werden können. Hierbei kann man beispielsweise sowohl an die Zuteilung von Prozessen zu Prozessoren denken, als auch an die Einplanung von Werkstücken auf Maschinen.

Da Scheduling-Probleme offensichtlich in vielen Bereichen innerhalb und auch außerhalb der Informatik auftauchen, findet dieses Gebiet schon seit langem in der Forschung Beachtung. Auch wenn im Laufe der Jahre zahlreiche Ergebnisse erzielt werden konnten, so bleiben immer noch etliche offene Fragen, die unter anderem auch am Lehrstuhl für Effiziente Algorithmen im Rahmen eines Sonderforschungsbereiches untersucht wurden.

Als Hilfsmittel zum Entwurf von Scheduling-Verfahren und zur Präsentation beispielsweise im Rahmen der Lehre wurde ein Framework zur Implementierung, Simulation und Visualisierung von Scheduling-Algorithmen realisiert. Innerhalb dieses Projektes besteht für Sie Gelegenheit zur Durchführung eines Systementwicklungsprojektes oder auch einer Diplomarbeit.

Das Projekt kann grob in folgende Teilgebiete unterteilt werden:

Eine Arbeit (DA/SEP) am Scheduling-Framework kann z.B. folgende Themen beinhalten: Der Inhalt und Umfang Ihres Arbeitspaketes kann mit uns abgesprochen werden und richtet sich nach Ihren Interessen und Vorkenntnissen, sowie nach der Anzahl der Bearbeiter. Abgestimmte Arbeiten von mehreren Interessenten sind nicht nur möglich, sondern auch erwünscht. Als Implementierungssprache wurde aus Effizienzgründen und wegen der komfortablen Bibliothek LEDA (Library for Efficient Datatypes and Algorithms) C++ gewählt. Auf einen sauberen, auf Wiederverwendbarkeit ausgerichteten Entwurf wird großen Wert gelegt. Zum Design wird die objektorientierte, graphische Modellierungssprache UML verwendet. Hierbei kommt das CASE-Tool Together/C++ zum Einsatz, das die Modellierung und die Erstellung von Dokumentation unterstützt. Together/C++ hat auch in der Industrie große Verbreitung und entspricht dem aktuellen Stand der Softwaretechnik.

Voraussetzungen: Die folgenden Kenntnisse sind für das Projekt von Nutzen, aber selbstverständlich müssen Sie nicht auf allen diesen Gebieten ausführliche Erfahrungen mitbringen, sofern Sie motiviert und bereit sind, sich fehlende Kenntnisse anzueignen.

Was den Umgang mit den eigentlichen Scheduling-Algorithmen betrifft, so können Sie sich je nach Interessenslage viel oder wenig damit beschäftigen. Dies hängt ganz von der Gestaltung Ihres Arbeitspakets ab.

* Kenntnisse in C++, LEDA
* Objektorientierter Entwurf mit UML
* Grundlegendes Wissen über effiziente Implementierung von Algorithmen (Vorlesung Effiziente Algorithmen, Algorithmenpraktikum)

Aufgabensteller: Prof. Dr. Ernst W. Mayr

Betreuung: Hanjo Täubig, Thomas Schickinger


Thomas Schickinger, Hanjo Täubig
Last modified: Thu May 16 16:49:25 CEST 2002