python - 具有可变数量 worker 的任务的最佳调度

Question

我有其持续时间已知整数长度的任务。任务之间也有依赖关系。我还有任意数量的工作人员可以安排这些任务。

我想为他们找到一个最佳时间表，首先我将所有任务的总执行时间最小化，其次我想将任务安排在一个已经运行了大部分先前依赖项的工作人员上之前，第三，我想尽量减少所需的 worker 数量。

所以如果task有依赖A，B，C，worker1运行A和B，worker2运行C，那么我更希望新的task被添加到worker1。

我正在为程序执行流程制作可视化，任务实际上是函数调用(具有已知数量的操作)，依赖项是数据依赖项。而不是一个长的线性表示，我想并行地可视化独立调用。我认为这个问题类似于我上面描述的任务调度问题。

在我的第一个简单方法中，我设法优化了整体执行的长度，但如果任务没有事先依赖，它会将它们添加到它们自己的 worker 中。即使现有 worker 中有未使用的孔。所以我不确定如何优化长度优先和 worker 数量。在我花更多时间在这上面之前，我想知道是否有一些已知的算法可以解决这个问题，即使是一个库，我也可以使用。

这个问题不是 this one 的重复问题因为:

• 任务没有截止日期，但有依赖性。
• 我想将任务安排在之前安排依赖项的同一个工作人员上。
• 可能有多个额外的 worker ，而不仅仅是一个。

Answer 1

首先，制作依赖图；有关可能的详细工作，请参见拓扑排序]( https://en.wikipedia.org/wiki/Topological_sorting )。

申请Dijkstra's algorithm翻转比较，这将找到最长的路径。这为您提供了最短执行时间和关键路径。有了这个，将该关键路径分配给一个 worker 。

现在，查找包含多个依赖项的依赖项子路径的时间不超过它们替换的依赖项的时间。例如，如果您有 D 需要的任务 A、B、C 的时间线，并且 B 和 C 总计的时间少于 A，您将从以下开始:

crit   AAAAAADDDDD
other  BBBCC

你可以把双任务弧和任务A互换，给你一个新的优先分配:

worker1 BBBCC-DDDDD
worker2 AAAAAA-----

这让你开始了吗？