348
6 Abbildung von Anwendungen
∀k :
i,a:i→k
c i ≤ κ k .
(6.18)
Das Problem der Auswahl einer Teilmenge von Objekten derart, dass der Gesamtprofit
i b i für die Objekte in den Rucksäcken maximiert wird, heißt 0-1-MultipleKnapsack-Problem (MKP).
Unter Ausnutzung eines Algorithmus für das MKP können wir Jobs m Prozessoren zuordnen. Dabei würden wir evtl. nicht alle Jobs wirklich einem Prozessor
zuordnen können. Bei identischen Prozessoren wären alle Kapazitäten gleich. Für
uniforme Prozessoren können wir die Kapazität benutzen, um die Geschwindigkeiten bzw. die Performanz der Prozessoren zu modellieren. Das MKP ist ebenfalls
NP-hart.
Aufgrund der Komplexität des Schedulings für synchrone Ankunftszeiten gibt es
keine Hoffnung auf effiziente optimale Algorithmen für das allgemeine Problem. In
der Praxis werden daher Heuristiken benutzt. Diese betrachten Tasks und Prozessoren
in einer bestimmten Reihenfolge und sie unterscheiden sich in der Reihenfolge,
die sie nutzen. Lopez et al. [356] haben verschiedene Heuristiken verglichen. Sie
beschränken sich auf sogenannte vernünftige Zuordnungsalgorithmen.
Definition 6.16: Ein vernünftiger Zuordnungsalgorithmus (engl. reasonable allocation (RA) algorithm) ist ein Algorithmus, der nur dann einer Task keinen Prozessor
zuordnet, wenn die Task auf keinen der Prozessoren der Plattform passt.
Definition 6.17: Ein vernünftiger abnehmender Zuordnungsalgorithmus (engl. reasonable allocation decreasing (RAD) algorithm) ist ein RA-Algorithmus, der Tasks
in nicht-aufsteigender Reihenfolge der Auslastung betrachtet.
Die von Lopez et al. untersuchten Algorithmen kombinieren alle möglichen Kombinationen von zwei Eigenschaften:
1. Die Reihenfolge, in der Tasks betrachtet werden: Tasks können in absteigender
Reihenfolge der Auslastung (bezeichnet als D), aufsteigender Reihenfolge der
Auslastung (bezeichnet als I) und in beliebiger Reihenfolge (bezeichnet durch
keinen Buchstaben) betrachtet werden.
2. Die Suchstrategie der Prozessorzuordnung. Wir nehmen an, dass die Prozessoren
in einer bestimmten Weise geordnet sind. Die first fit-Strategie (bezeichnet als
FF) wird dann eine Task dem ersten Prozessor zuordnen, auf den sie passt. Die
worst fit-Strategie (bezeichnet als WF) wird dann eine Task dem Prozessor mit
der größten verbleibenden Kapazität zuordnen. Die best fit-Strategie (bezeichnet
als BF) wird dann eine Task dem Prozessor mit der kleinsten noch ausreichenden
verbleibenden Kapazität zuordnen.
Es gibt insgesamt neun Kombinationen. Alle können effizient realisiert werden.
Beispielsweise sieht der Algorithmus FFD wie folgt aus:
6 Abbildung von Anwendungen
∀k :
i,a:i→k
c i ≤ κ k .
(6.18)
Das Problem der Auswahl einer Teilmenge von Objekten derart, dass der Gesamtprofit
i b i für die Objekte in den Rucksäcken maximiert wird, heißt 0-1-MultipleKnapsack-Problem (MKP).
Unter Ausnutzung eines Algorithmus für das MKP können wir Jobs m Prozessoren zuordnen. Dabei würden wir evtl. nicht alle Jobs wirklich einem Prozessor
zuordnen können. Bei identischen Prozessoren wären alle Kapazitäten gleich. Für
uniforme Prozessoren können wir die Kapazität benutzen, um die Geschwindigkeiten bzw. die Performanz der Prozessoren zu modellieren. Das MKP ist ebenfalls
NP-hart.
Aufgrund der Komplexität des Schedulings für synchrone Ankunftszeiten gibt es
keine Hoffnung auf effiziente optimale Algorithmen für das allgemeine Problem. In
der Praxis werden daher Heuristiken benutzt. Diese betrachten Tasks und Prozessoren
in einer bestimmten Reihenfolge und sie unterscheiden sich in der Reihenfolge,
die sie nutzen. Lopez et al. [356] haben verschiedene Heuristiken verglichen. Sie
beschränken sich auf sogenannte vernünftige Zuordnungsalgorithmen.
Definition 6.16: Ein vernünftiger Zuordnungsalgorithmus (engl. reasonable allocation (RA) algorithm) ist ein Algorithmus, der nur dann einer Task keinen Prozessor
zuordnet, wenn die Task auf keinen der Prozessoren der Plattform passt.
Definition 6.17: Ein vernünftiger abnehmender Zuordnungsalgorithmus (engl. reasonable allocation decreasing (RAD) algorithm) ist ein RA-Algorithmus, der Tasks
in nicht-aufsteigender Reihenfolge der Auslastung betrachtet.
Die von Lopez et al. untersuchten Algorithmen kombinieren alle möglichen Kombinationen von zwei Eigenschaften:
1. Die Reihenfolge, in der Tasks betrachtet werden: Tasks können in absteigender
Reihenfolge der Auslastung (bezeichnet als D), aufsteigender Reihenfolge der
Auslastung (bezeichnet als I) und in beliebiger Reihenfolge (bezeichnet durch
keinen Buchstaben) betrachtet werden.
2. Die Suchstrategie der Prozessorzuordnung. Wir nehmen an, dass die Prozessoren
in einer bestimmten Weise geordnet sind. Die first fit-Strategie (bezeichnet als
FF) wird dann eine Task dem ersten Prozessor zuordnen, auf den sie passt. Die
worst fit-Strategie (bezeichnet als WF) wird dann eine Task dem Prozessor mit
der größten verbleibenden Kapazität zuordnen. Die best fit-Strategie (bezeichnet
als BF) wird dann eine Task dem Prozessor mit der kleinsten noch ausreichenden
verbleibenden Kapazität zuordnen.
Es gibt insgesamt neun Kombinationen. Alle können effizient realisiert werden.
Beispielsweise sieht der Algorithmus FFD wie folgt aus: