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.
|