ここに割り当ての問題がありますhttp://en.wikipedia.org/wiki/Generalized_assignment_problem
同様のタスクがありますが、アルゴリズムが見つかりません。m 個のタスク、n 人の労働者、m>n があります。タスクが完了すると、労働者は次のタスクを取ります (空いているタスクがある場合)。ある労働者が仕事を引き受ければ、他の誰もそれを引き受けることはできません。各労働者には独自の速度 V1..Vn があり、各タスクには独自の「ボリューム」 - W1..Wm があります。したがって、すべてのタスクを実行する時間を最小限に抑えることを目標に、労働者間でタスクを分散する必要があります。
アルゴリズムまたはこの問題の命名方法を見つけるのを手伝ってください。)
This problem is scheduling jobs on parallel, uniformly related machines so as to minimize the makespan. There's a polynomial-time approximation scheme due to Hochbaum and Shmoys (Using dual approximation algorithms for scheduling problems: Theoretical and practical results, 1988). btilly is right that the bin-packing problem is closely related; the analyses of both Hochbaum--Shmoys and the previous best approximation MULTIFIT are based on techniques pioneered for bin packing.
これは、 http://en.wikipedia.org/wiki/Bin_packing_problemの np-complete バリエーションのようです。したがって、正確なアルゴリズムについては心配しません。
タスクが独立していると仮定すると、私の最初の試みは貪欲なヒューリスティックになります。終了時間の見積もりが与えられたら、その終了時間までに終了できる最長のタスクをすべてのポイントで各ワーカーに割り当てます。ここで二分探索を行って、回避できる最短の終了時間を見つけます。最初の上限時間は、最速のワーカーがすべてを実行する時間です。最初の低い時間は、すべてのワーカーが同時に作業している場合に、すべてのワーカーがその量の作業を完了するための時間です。
これが常に完全に最適であるとは限らないことは明らかです。しかし、それはかなりうまくいくはずです。