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:
    
      - Simulationskern
 
      - Visualisierung und graphischer Editor (hierbei ist
	beispielsweise auch die Realisierung des automatischen Layouts von Graphen
	interessant)
 
      - Automatische Generierung von Probleminstanzen
 
      - Realisierung von Hilfsfunktionen und Datenstrukturen, die
	in Scheduling-Algorithmen benötigt werden (z. B. Berechnung des
	kritischen Pfades, Umwandlung unterschiedlicher Darstellungen für
	Präzedenzrelationen)
 
      - Exemplarische Implementationen von Scheduling-Algorithmen
 
    
  Eine Arbeit (DA/SEP) am Scheduling-Framework kann z.B. folgende
  Themen beinhalten:
    
      - Corba-Anbindung der Scheduling-Algorithmen
 
      - Erweiterung des Frameworks um stochastische Scheduling-Modelle
	und -Algorithmen (Generierung, Visualisierung, statistische Analyse)
      
 
      - Implementierung ausgewählter Scheduling-Algorithmen. Im Rahmen einer
	Diplomarbeit könnten auch eigene Verfahren und Heuristiken
	entwickelt und untersucht werden.
      
 
    
  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