如何最小化并行计算的运行时间？

Question

假设有一个函数f决定了一组计算结果，并在找到最后一个问题的答案后立即终止。每个n进程都花费一些不可忽略的时间量，并且在计算过程中花费的时间和在该计算过程中完成的工作之间存在完美的线性相关性。

在更多的数学-Y而言，每i个并行的子问题n_i需要时间t_i终止，并且每个t_i是唯一的每个并行的子问题。

给出这些条件和无限数量的处理器，很容易发现算法的总运行时间正好是max(t)。然而，人们计算机上的计算机具有有限数量的处理器p，之后引入更多的子进程压倒了真实的系统，并且实际上增加了总运行时间f。

我的问题是 - 鉴于这种实际情况下，其中的子进程的数目由p界 - 什么是决定如何最佳调度集跨越p处理器并行子问题n，以总减少最快的算法函数的运行时间f？

Answer 1

感谢stark对bin装箱问题的评论，我发现这个问题其实有个名字！它的名称非常明智，即Multiprocessor Scheduling Problem。正如我怀疑的那样，它在NP中，这意味着没有有效的算法来解决它。在目前编程的应用程序中，这是一个非常不幸的消息，但仍然有用！