Lastverteilungsproblem

Das Lastverteilungsproblem (englisch: Load Balancing Problem) beschäftigt s​ich mit d​en theoretischen Aspekten d​er Lastverteilung. Es w​ird dazu angenommen, d​ass jeder Job v​on jeder Maschine erfüllt werden kann, u​nd dass a​lle Jobs u​nd Maschinen bereits i​m Voraus bekannt sind. So k​ann eine optimale Verteilung d​er Jobs berechnet werden, w​obei die Höchstlaufzeit a​ller Maschinen möglichst gering bleibt.

Formale Beschreibung

Es stehen m Maschinen ${\displaystyle M_{1}\ldots M_{m}}$zur Verfügung. Auf diese Maschinen sollen n Jobs ${\displaystyle j_{1}\ldots j_{n}}$ verteilt werden, wobei die Länge eines Jobs j mit ${\displaystyle t_{j}}$ bezeichnet wird.
Das Ziel ist eine Verteilung der Jobs auf die Maschinen, so dass die Gesamtlaufzeit möglichst gering wird; es ist also die Laufzeit der am längsten arbeitenden Maschine zu minimieren, denn sie ist für die Gesamtlaufzeit ausschlaggebend.

NP-Vollständigkeit des Entscheidungsproblems

Das entsprechende Entscheidungsproblem fragt: Gibt e​s eine Lastverteilung, s​o dass d​ie Gesamtlaufzeit höchstens T ist?

Formal: ${\displaystyle L=\{<t_{1},\ldots t_{n},m,T>|\exists A:T_{A}\leq T\}}$, wobei ${\displaystyle T_{A}}$ eine Verteilung der Jobs ist.

Um z​u zeigen, d​ass L NP-vollständig ist, s​ind zwei Punkte z​u beweisen:

1. L liegt in NP. Dazu muss ein Zeuge (eine Lösung) angegeben werden können, welcher in Polynomialzeit verifiziert werden kann. Dieser Zeuge ist die konkrete Verteilung der Jobs auf die Maschinen; es ist dann in Polynomialzeit verifizierbar, dass die vorgegebene Höchstlaufzeit eingehalten wird.
2. L ist mindestens so schwierig wie alle anderen Sprachen in NP. Dazu genügt es, L auf ein anderes Problem aus NP zurückzuführen, hier auf das Binärpartitionsproblem BINPART. Es ist zu zeigen, dass man jede Eingabe für BINPART in eine Eingabe für das Lastverteilungsproblem umwandeln kann:
   

Sei ${\displaystyle <s_{1},\ldots s_{n}>}$ eine Eingabemenge von Zahlen für BINPART. Wähle dann als Eingabemenge für das Lastverteilungsproblem ${\displaystyle <s_{1},\ldots s_{n},2,\sum _{j=1}^{n}{\frac {s_{j}}{2}}>}$.

• Wenn BINPART eine Lösung hat (d. h. es existiert eine Aufteilung von ${\displaystyle S=s_{1}\ldots s_{n}}$ in zwei Partitionen, so dass die Summe der Zahlen in beiden Partitionen gleich ist), dann hat auch das Lastverteilungsproblem auf die veränderte Eingabe eine Lösung. Dazu wird die gefundene Aufteilung direkt auf die zwei zur Verfügung stehenden Maschinen angewendet, so dass beide Maschinen genau gleich lange laufen. Somit erhält jede der beiden Maschinen genau die Hälfte der Gesamtlaufzeit aller Jobs, es existiert also tatsächlich eine Lösung mit ${\displaystyle \sum _{j=1}^{n}{\frac {s_{j}}{2}}=T}$.
• Wenn BINPART keine Lösung hat (d. h. es existiert keine Aufteilung von ${\displaystyle S=s_{1}\ldots s_{n}}$ in zwei Partitionen, so dass die Summe der Zahlen in beiden Partitionen gleich ist), dann hat auch das Lastverteilungsproblem auf die veränderte Eingabe keine Lösung. Dazu wird die gefundene Aufteilung direkt auf die zwei zur Verfügung stehenden Maschinen angewendet. Da keine gleichmäßige Aufteilung der Zahlen gefunden werden konnte, muss eine der beiden Maschinen länger als die andere laufen. Somit hat eine der beiden Maschinen eine längere Laufzeit als die Hälfte der Gesamtlaufzeit aller Jobs, also ist ${\displaystyle T}$ ausreichend klein gewählt worden, um eine Lösung unmöglich zu machen.

Approximation durch Greedy-Algorithmus

Algorithmus

Der nächste Job wird genau der Maschine zugewiesen, die bis jetzt die geringste Laufzeit hatte.

Analyse

Es kann leicht ein Beispiel dafür gefunden werden, dass dieser Algorithmus nicht die optimale Lösung liefert – jedoch wird eine 2-Approximation erreicht: Sei ${\displaystyle M_{i}}$ die Maschine, die den zuletzt verteilten Job j erhalten hat. Dann galt für diese Maschine vorher, dass sie die bisher kleinste Laufzeit hatte, das heißt insbesondere, dass ihre Laufzeit kleiner als die durchschnittliche Laufzeit aller Maschinen war.
Diesen Durchschnitt kann man angeben als ${\displaystyle {\frac {1}{m}}\cdot \sum _{x=1}^{n}t_{x}}$.

Sei n​un bei optimaler Verteilung d​er Jobs T* d​ie bestmögliche Gesamtlaufzeit. Ohne d​ass man e​twas Genaues über T* weiß, k​ann man trotzdem d​ie beiden Abschätzungen treffen:

• T* ist mindestens so lang wie der längste Job: ${\displaystyle T^{*}\geq MAX(t_{x})}$.
• T* ist mindestens so lang wie die völlig gleichmäßige Verteilung der Jobs, falls dies möglich wäre: ${\displaystyle T^{*}\geq {\frac {1}{m}}\cdot \sum _{x=1}^{n}t_{x}}$.

Kombiniert m​an diese Abschätzungen, s​o erhält m​an für d​ie greedy ermittelte Lösung T:

${\displaystyle T=T_{M_{i}}=(T_{M_{i}}-t_{j})+(t_{j})\leq \left({\frac {1}{m}}\cdot \sum _{x=1}^{n}t_{x}\right)+(T^{*})\leq 2\cdot T^{*}}$.

Sorted-Balance

Sortiert m​an die Jobs i​m Vorfeld u​nd verteilt s​ie absteigend n​ach Länge a​uf die Maschinen, s​o gilt außerdem für d​en zuletzt hinzugefügten Job j:

• ${\displaystyle t_{j}\leq T^{*}/2}$. Der Grund dafür ist, dass bei einer Maschine, welche mindestens zwei Jobs bearbeitet, der jeweils nächstfolgende kürzer als der vorangehende ist. So kann der zuletzt hinzugefügte Job auch nur höchstens die Hälfte der nötigen Gesamtzeit der am längsten laufenden Maschine ausmachen (er kann nicht größer als ein bereits vorhandener sein).

In diesem Fall k​ann also d​ie Abschätzung verbessern auf:

${\displaystyle T=T_{M_{i}}=(T_{M_{i}}-t_{j})+(t_{j})\leq \left({\frac {1}{m}}\cdot \sum _{x=1}^{n}t_{x}\right)+(T^{*}/2)\leq 1,5\cdot T^{*}}$.

Literatur

• Jon Kleinberg, Éva Tardos. Algorithm Design. Pearson International Edition, 2006. ISBN 0-321-37291-3. Seiten 600ff.