我的倾向是不提前想好如何分配任务，而是将它们全部扔进一个共同的工作队列中。任何没有其他任务要做的工作线程都会从队列中获取下一个任务并完成工作，然后检查队列是否有下一个任务。
最简单的方法是按p_i降序排序作业（但这是O(n log n)），并执行以下操作：
该算法应该给出最佳结果，但时间复杂度为O(NM)，其中N是任务数，M是线程数。解决方案的总成本为O(N log N + NM)，因此对于M << N为O(N log N)，对于M接近N为O(n^2)。
在O(N)中，这似乎很容易。
给每个线程一些“点数”。设p_i为分配给线程T_i的点数。对于每个任务，选择具有最高p_i的线程，并从p_i中减去任务成本。然后，您只需要跟踪按得分排序的线程，在O(N)时间内是微不足道的，并且可以使用平衡树在O(log N)内轻松完成。
对于连续操作，p_i没有最小值。如果要避免得分朝着-inf走向狂野，请定期向所有得分添加任意数量P（所有得分相同）。
编辑：我弄错了N。上面，N是线程数，与所提出的问题相反。当N =任务数，T =线程数时，这导致O(N*log T)成本。如果T“较小”，则接近O(N)。
编辑2： 如果所有任务和线程数量都已知，则我认为计算最佳调度类似于背包问题，并且在所有情况下都是NP完全的（因此您将在某些地方得到指数级）。正如我上面所描述的那样，简单的基于成本的分析将为您提供相对较好的近似值，只要所有单个任务与分配给每个线程的总成本相比具有较小的成本。
虽然关于背包问题的建议很有帮助，但你说你正在尝试最小化执行的净时间。采用背包方法需要不断增加背包的大小，直到获得可行解-效率不高。
如果并行工作的所有线程中最长完成时间限制了执行的净时间，我想分配任务以使所有线程的最大工作时间最小化。这样做可能会导致一个或多个线程没有做太多的工作，因此我们并没有真正“平衡”工作量。如果您想平衡工作量，那么这就是不同的目标函数。例如，您可能希望最小化线程之间的工作差异。
请查看作业车间调度领域。如果您只偶尔这样做，我建议使用遗传算法-如果您需要经常进行自动化处理，则建议进行一些确定性算法的文献搜索。希望这可以帮助。
