重み付けされた負荷分散リソーススケジューリングアルゴリズム

Question

私が取り組んでいるソフトウェアアプリケーションは、現在持っているタスクの数に基づいてユーザーのグループにタスクを割り当てることができる必要があります。タスクが最も少ないユーザーが次のタスクを取得する可能性が最も高くなります。ただし、現在のタスクの負荷は、絶対的な順序の定義ではなく、重みとして扱う必要があります。 IOW、重み付けされた負荷分散アルゴリズムを実装する必要があります。

5人のユーザーがいて、次のタスク数があるとします：

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

CABDEの順序で次のタスクのユーザーに優先順位を付けます。Cが割り当てを取得する可能性が最も高く、Eが最も低いです。ここで注意すべき重要な点が2つあります：

• ユーザー数は2から数十人までさまざまです。
• 各ユーザーに割り当てられるタスクの数は、1から数百までさまざまです。

現時点では、すべてのタスクを平等に扱うことができますが、将来使用できる変数として難しいタスクを含めることは構いませんが、これは純粋にケーキに着氷しているだけです。

これまでに思いついたアイデアは、状況によってはあまり良くありません。多数のユーザーがいる場合は、ユーザーの重みを厳しくしすぎたり、ユーザーに現在のタスクがない場合は横ばいになったり、...

ウェブをいじってみましたが、あまり運がありませんでした。誰でもうまくいくアルゴリズムの簡単な概要を教えてもらえますか？実際の実装は必要ありません-その部分を行います-ちょうど良い説明です。あるいは、自由にアクセスできる優れたWebサイトはありますか？

また、私は確かに品質を高く評価していますが、これは統計的に完璧である必要はありません。したがって、優れた手法ではなく優れた手法を考えることができるなら、私は興味があります！

Answer 1

指摘したように、これは負荷分散の問題です。何も最小化しようとしていないので、実際にはスケジューリングの問題ではありません（合計時間、同時ワーカーの数など）。特別な制約（ジョブの期間、時間の衝突、一致するスキルセットなど）はありません。したがって、実際には問題は適切な重み付け関数の選択に帰着します。

ユーザーの重み付けが近すぎるなど、避けたい状況があると言います。詳細を教えてください。たとえば、他のワーカーのワークロードによって正規化された現在のワークロードにちょうど比例して割り当ての機会を作ることの何が問題になっていますか？これをさまざまな長さのブロックのシーケンス（タスク）として視覚化し、一連のビン（ワーカー）に詰め込み、ビンの合計の高さをできるだけ均一にしようとしています。

詳細については、お客様に役立つ機能の具体的な推奨事項を作成できます。

編集：負荷分散関数の例

コメントに基づいて、さまざまなバランス調整動作を提供できる単純な関数の例を次に示します。基本的な質問は、決定的な振る舞いをするか、確率的な振る舞いをするかです。それぞれの例をいくつか挙げます。

質問の例を使用するには、4 + 5 + 0 + 7 + 9 = 25個のジョブが現在割り当てられています。誰がジョブ26を取得するかを選択します。

1）シンプルなタスクファーム。ジョブごとに、現在保留中のジョブが最も少ないワーカーを常に選択します。速い労働者はもっとやることができますが、全員がほぼ同時に終了します。

2）公平なワークロードを保証します。作業者が異なる速度で作業し、他の作業よりも多くの作業を行いたくない場合は、各作業者の完了+保留中のジョブの数を追跡します。次のジョブを割り当てて、この数が均等に広がるようにします（高速ワーカーは無料で休憩できます）。

3）基本的な線形正規化。各ワーカーが持つことができるジョブの最大数を選択します。各ワーカーのワークロードは、その数に正規化されます。たとえば、ジョブ/ワーカーの最大数が15の場合、容量に達する前にさらに50個のジョブを追加できます。したがって、各ワーカーの次のジョブが割り当てられる確率は

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

特定の最大しきい値を使用したくない場合は、現在の保留ジョブの最大数を持つワーカーを制限として使用できます。この場合、それはワーカーEなので、確率は次のようになります

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

この場合、正規化により、ワーカーEにジョブを割り当てることができなくなります-すでに限界に達しています。また、Cが何もすることがないからといって、Cが新しい仕事を与えられることを保証されるわけではありません（それはより可能性が高いです）。

0〜1の乱数 r を生成し、これらの境界と比較することにより、choice関数を簡単に実装できます。したがって、 r が<！> ltの場合、 0.25、Aがジョブを取得、0.25 <！> lt; r <！> lt; 0.45、Bは仕事を取得します。

4）非線形正規化。（線形減算の代わりに）対数関数を使用して数値に重みを付けると、非線形正規化を簡単に取得できます。これを使用して、確率を歪めることができます。多くの仕事を持たない労働者がより多く与えられる可能性を高めるために。

ポイントは、これを行う方法の数は事実上無制限であるということです。使用する重み関数は、有効にしようとしている特定の動作によって異なります。これが出発点として使用できるアイデアを提供してくれることを願っています。