Lastverteilung. Warum nicht vorrangige Warteschlangen verwenden?

Question

Ich habe kürzlich verschiedene randomisierte Algorithmen für den Lastausgleich erfahren. Das Modell ist immer, dass es $ M $ Bälle und $ n $ Bins und die Bälle nacheinander ankommen. Die Aufgabe besteht darin, die maximale Belastung eines Behälters zu minimieren. Es gibt jedoch etwas, das ich nicht verstehe.

Warum nicht einfach eine vorrangige Warteschlange der Lasten der Behälter behalten und einen neuen Ball mit der niedrigsten Stromlast für den Mülleimer zuweisen? Dies scheint Ihnen die optimale Last ohne Komplikationen zu geben.

Answer 1

Sie haben Recht, dass die Verwendung einer Prioritätswarteschlange eine gute Idee ist. Es gibt jedoch keine optimale Antwort. (Angenommen, das, was Sie zu optimieren versuchen, ist die Zeit, in der der letzte Prozessor den letzten Job ausführt.) Dieses Planungsproblem ist NP-Complete, und die vorrangige Warteschlangenbasis gibt eine Antwort, die innerhalb eines Faktors 2 von Optimal liegt. Siehe zum Beispiel, http://www.cs.princeton.edu/courses/archive/spr05/cos423/lectures/11approx-alg.pdf. Das Wikipedia -Seite zur Planung von Job Shop gibt auch einige Informationen.