Job Scheduling

Job Scheduling Optimierung

Job Scheduling
Optimierung mit grafischer Darstellung des Optimierungsprozesses
Aufgabenbeschreibung
Gegeben sind n Prozessoren und m Jobs. Jedem Job ist eine Prozessorlaufzeit tm zugeordnet. Ziel ist es, eine möglichst gute, im Idealfall eine optimale Zuordnung der Jobs auf die Prozessoren zu finden.

Hierzu ist eine Bewertungsfunktion für die Zuordnungen notwendig, diese ist dann zu minimieren. Es sollen verschiedene Bewertungsfunktionen realisiert werden: Im einfachsten Fall die Minimierung der Gesamtlaufzeit, aber auch die Minimierung der Antwortzeiten oder Kombinationen hiervon.

Die Anzahl der Prozessoren und die Menge der zu verteilenden Jobs soll frei wählbar sein. Die Jobs sollen einmal zufallsgesteuert erzeugt werden: zum Beispiel durch eine Gleichverteilung in einem Intervall, Poisson-verteilt mit gegebenem Mittelwert oder anderen sinnvollen Strategien. Es soll aber auch möglich sein, aus einer Konfigurationsdatei eine vollständige, per Hand erzeugte Problemstellung zu laden. Eine erzeugte Problemstellung soll aber auch abgespeichert werden können.

Als Lösungsstrategien sind unterschiedliche Ansätze zu implementieren: Zufallssuche, Heuristiken wie erst lange Jobs, dann die mit kurzer Laufzeit oder umgekehrt, schrittweise Verbesserung durch Vertauschen, genetische Algorithmen, Einschränkungserfüllung, ...

Die Aufteilung der Jobs auf die Prozessoren kann durch Balkendiagramme dargestellt werden: Jeder Balken repräsentiert den Zustand eines Prozessors über die Zeit, jeder Job wird als Teilstück mit unterschiedlicher Farbe in diesem Balken dargestellt.

Zusätzlich soll der Rechenaufwand für die unterschiedlichen Algorithmen dargestellt werden, so daß die Effizienz und die Güte der verschiedenen Algorithmen vergleichbar wird.

Programmiersprachen und Werkzeuge
100% Java, JDK 1.2 oder neuer, optionaler Aufruf von externen Programmen, z.B in Prolog für spezielle Algorithmen.
Umgebung
ablauffähig als Java Applet im WWW oder als Applikation
Das Speichern von Konfigurationen braucht nur von einer Applikation aus möglich zu sein. Die Klassen sind nach Java Beans Namenskonventionen zu entwickeln.
Testwerkzeuge
appletviewer, Java fähiger browser, bean box

Hauptnavigation