工作人数可变的任务优化调度

Question

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

我想为他们找到一个最佳的时间表，首先我要最小化所有任务执行的总长度，其次我想在一个之前运行过大多数依赖项的工作人员身上安排任务，第三我想最小化所需的工作人员数量。

因此，如果任务具有依赖项A、B和C，并且worker1运行A和B，worker2运行C，那么我更希望将新任务添加到worker1。

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

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

这个问题不是这个问题的重复，因为：

• 任务没有截止日期，但具有相关性
• 我想在安排之前依赖关系的同一个工作进程上安排任务
• 可能会有多个额外的工人，而不仅仅是一个

Answer 1

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

应用Dijkstra算法，翻转比较，将找到最长路径。这将为您提供最短的执行时间和关键路径。有了它，就可以将关键路径分配给一个工人。

现在，寻找包含多个依赖项的依赖子路径，它们的时间不超过它们替换的依赖项。例如，如果你有一个时间线来完成任务A、B、C，而这些任务是D和B需要的

crit   AAAAAADDDDD
other  BBBCC

您可以将两个任务弧与任务A交换，从而获得新的优先分配：

worker1 BBBCC-DDDDD
worker2 AAAAAA-----

这让你开始了吗？