ご指摘のとおり、これは負荷分散の問題です。何も最小化しようとしていないため (合計時間、同時ワーカー数など)、実際にはスケジューリングの問題ではありません。特別な制約 (ジョブ期間、時間の衝突、一致するスキル セットなど) はありません。したがって、実際の問題は、適切な重み付け関数を選択することになります。
ユーザーの重み付けが近すぎるなど、回避したい状況がいくつかあるとおっしゃっています。詳細を教えていただけますか？たとえば、割り当ての可能性を現在のワークロードに比例させ、他のワーカーのワークロードによって正規化することの何が問題になっているのでしょうか? これは、異なる長さの一連のブロック (タスク) として視覚化できます。一連のビン (ワーカー) にパックされ、ビンの合計の高さを可能な限り均一に保とうとしています。
より多くの情報があれば、私たちはあなたのために働くことができる機能の具体的な推奨をすることができます.
編集:負荷分散関数の例
あなたのコメントに基づいて、さまざまなバランス動作を提供できる単純な関数の例をいくつか示します。基本的な質問は、決定論的または確率論的な動作が必要かどうかです。それぞれの例をいくつか紹介します。
質問の例を使用すると、現在 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 に何もすることがないからといって、新しい仕事が与えられることが保証されているわけではありません (可能性が高いだけです)。
0 と 1 の間の乱数rを生成し、それをこれらの境界と比較することで、choice 関数を簡単に実装できます。したがって、rが < 0.25 の場合、A が仕事を獲得し、0.25< r < 0.45 の場合、B が仕事を獲得します。
4) 非線形正規化。(線形減算の代わりに) 対数関数を使用して数値に重みを付けると、非線形正規化を取得する簡単な方法になります。これを使用して、確率を歪めることができます。たとえば、多くの仕事を持たない労働者により多くの仕事が与えられる可能性が高くなります。
ポイントは、これを行う方法の数は実質的に無制限だということです。使用する重み関数は、有効にしようとしている特定の動作によって異なります。うまくいけば、出発点として使用できるいくつかのアイデアが得られます.