Die gewichteten, Load-Balancing-Ressource-Scheduling-Algorithmus

Question

Eine Software-Anwendung, die ich auf Bedürfnisse gerade arbeite der Lage sein, Aufgaben auf, wie viele Aufgaben an eine Gruppe von Benutzern sie derzeit haben zuzuweisen, wo die Benutzer mit den wenigsten Aufgaben am ehesten bekommen die nächste Aufgabe sind. Allerdings sollte die aktuelle Aufgabe Last als Gewichtungs behandelt werden, anstatt eine absolute Ordnung Definition. IOW, ich brauche eine gewichtete, Load-Balancing-Algorithmus zu implementieren.

Nehmen wir an, es gibt fünf Benutzer mit der folgenden Reihe von Aufgaben:

A: 4 B: 5 C: 0 D: 7 E: 9

Ich mag die Benutzer für die nächste Aufgabe in der Reihenfolge CABDE priorisieren, wobei C am ehesten die Zuordnung und E, die am wenigsten wahrscheinlich zu bekommen. Es gibt zwei wichtige Dinge zu beachten hier:

• Die Anzahl der Benutzer kann von 2 bis dutzende variieren.
• Die Anzahl der Aufgaben, die jedem Benutzer zugeordnet sind, können von 1 bis Hunderte variieren.

Für den Moment können wir alle Aufgaben als gleich behandeln, obwohl ich nicht schwierig als Variable einschließlich Aufgabe kümmern würde, dass ich in Zukunft nutzen kann -. Aber das ist rein Tüpfelchen auf dem i

Die Ideen, die ich mit so weit habe kommen sind nicht sehr gut in einigen Situationen. Sie könnten Benutzer Gewicht zu eng zusammen, wenn es eine große Anzahl von Benutzern sind, oder sie könnten verpuffen, wenn ein Benutzer keine aktuellen Aufgaben hat, oder ....

Ich habe versucht, um die Web-Stossen, haben aber nicht viel Glück gehabt. Kann mir jemand eine kurze Zusammenfassung eines Algorithmus geben, die gut funktionieren würde? Ich habe nicht eine tatsächliche Implementierung brauchen - ich werde diesen Teil tun - nur eine gute Beschreibung. Alternativ gibt es eine gute Website, die frei zugänglich ist?

Auch wenn ich sicherlich Qualität zu schätzen weiß, ist dies nicht statistisch perfekt. Also, wenn Sie von einer guten, aber nicht großartiger Technik denken können, ich bin interessiert!

Answer 1

Wie Sie weisen darauf hin, das ist ein Load-Balancing-Problem. Es ist nicht wirklich ein Planungsproblem, da Sie nicht sind zu versuchen, etwas (Gesamtzeit, die Anzahl der gleichzeitigen Arbeiter, etc.) zu minimieren. Es gibt keine besonderen Einschränkungen (Auftragsdauer, Zeit Auseinandersetzungen, Fähigkeiten usw. entsprechen) Also wirklich Ihr Problem kocht eine geeignete Gewichtungsfunktion um die Auswahl nach unten.

Sie sagen, es gibt einige Situationen, die Sie, wie Benutzer Gewichtungen vermeiden möchten, die zu nahe beieinander sind. Können Sie weitere Informationen zur Verfügung stellen? Zum Beispiel, was mit der Herstellung der Möglichkeit der Zuweisung falsch ist nur proportional zu der aktuellen Arbeitsbelastung durch die Arbeitsbelastung der anderen Arbeiter normalisiert? Sie können dies als eine Folge von Blöcken unterschiedlicher Länge (die Aufgaben) sichtbar zu machen, in eine Reihe von Behältern verpackt (die Arbeiter), wo Sie versuchen, die Gesamthöhe der Behälter zu halten, so gleichmäßig wie möglich.

Mit mehr Informationen konnten wir konkrete Empfehlungen von Funktionen machen, die für Sie arbeiten könnten.

Edit: Beispiel Load-Balancing-Funktionen

Auf der Basis Ihrer Kommentare, hier sind einige Beispiele von einfachen Funktionen, die Ihnen unterschiedliche Bilanz Verhalten geben können. Eine grundlegende Frage ist, ob Sie deterministische oder probabilistische Verhalten wollen. Ich werde ein paar Beispiele für jeden geben.

Um das Beispiel in der Frage zu verwenden - es gibt 4 + 5 + 0 + 7 + 9 = 25 Arbeitsplätze zur Zeit zugeordnet. Sie wollen wählen, den Job bekommt 26.

1) Einfache Aufgabe Bauernhof. Für jeden Auftrag, wählt immer die Arbeiter mit den am wenigsten Arbeitsplätzen derzeit anhängig. Schnelle Arbeiter bekommen mehr zu tun, aber jeder endet in etwa zur gleichen Zeit.

2) faire Arbeitsbelastung garantieren. Wenn die Arbeiter mit unterschiedlichen Geschwindigkeiten arbeiten, und Sie wollen nicht, einige mehr als andere tun, dann verfolgt die Anzahl der abgeschlossenen + anstehende Aufträge für jeden Arbeitnehmer. Weisen Sie den nächsten Auftrag, diese Zahl zu halten gleichmäßig verteilt (schnelle Arbeiter frei Pausen bekommen).

3) Grund lineare Normalisierung. Wählen Sie eine maximale Anzahl von Aufträgen kann jeder Arbeitnehmer hat. Jede Arbeitsbelastung des Arbeitnehmers ist auf diese Zahl normalisiert. Wenn beispielsweise die maximale Anzahl der Arbeitsplätze / Arbeiter 15, dann 50 weitere Arbeitsplätze können hinzugefügt werden, bevor Sie Kapazität erreichen. Also für jeden Arbeitnehmer die Wahrscheinlichkeit, den nächsten Auftrag vergeben wird, ist

P(A) = (15 - 4)/50 = 0.22  
P(B) = (15 - 5)/50 = 0.2  
P(C) = (15 - 0)/50 = 0.3  
P(D) = (15 - 7)/50 = 0.16  
P(E) = (15 - 9)/50 = 0.12

Wenn Sie nicht über einen bestimmten maximalen Grenzwert verwenden mögen, können Sie den Arbeiter mit der höchsten aktuellen Anzahl der anstehenden Aufträge als Grenzwert verwenden. In diesem Fall, das ist Arbeiter E, so wären die Wahrscheinlichkeiten

P(A) = (9 - 4)/20 = 0.25  
P(B) = (9 - 5)/20 = 0.2  
P(C) = (9 - 0)/20 = 0.45 
P(D) = (9 - 7)/20 = 0.1  
P(E) = (9 - 9)/20 = 0

Beachten Sie, dass in diesem Fall die Normalisierung Arbeitnehmer gewährleistet E keine Jobs zugeordnet werden kann - er ist schon an der Grenze. Auch, weil C hat nichts zu tun, bedeutet nicht, er ist garantiert, einen neuen Job zu erhalten (es ist nur wahrscheinlicher).

Sie können einfach die Wahl Funktion implementieren, indem eine Zufallszahl r zwischen 0 und 1 und sie an diese Grenzen zu vergleichen. Also, wenn r <0,25 ist, A bekommt den Job, 0,25 < r <0,45, B bekommt den Job, etc.

4) Nicht-lineare Normalisierung. , um eine Log-Funktion (statt die lineare Subtraktion verwenden), um Ihre Zahlen zu gewichten ist eine einfache Möglichkeit, eine nicht-lineare Normalisierung zu erhalten. Sie können diese verwenden, um die Wahrscheinlichkeiten zu neigen, z.B. es viel wahrscheinlicher, dass die Arbeitnehmer ohne viele Arbeitsplätze zu machen sind mehr gegeben.

Der Punkt ist, dies die Anzahl der Möglichkeiten zu tun, ist praktisch unbegrenzt. Welche Gewichtungsfunktion verwendet wird, hängt von dem spezifischen Verhalten, damit Sie versuchen. Hoffentlich haben Sie einige Ideen, die Sie als Ausgangspunkt verwenden können.