algorithm - 如何将一组相关步骤分成组

Question

我有一组要执行的步骤，每个步骤都有一个时间(以分钟为单位)。

我还有一组依赖项(即第 7 步必须在第 5 步之后)。

假设没有循环，将它们分组的正确算法是什么，其中每个组的总时间少于一定数量。

显然，除非依赖项给出线性顺序，否则有多种安排步骤的方法，是否容易/可能得出最佳(即，需要最少的组)。

目前我的步骤和依赖项都在 SQL 中，但我很乐意使用另一种语言来解决。

Answer 1

当没有依赖关系时，这就是 NP-hard 装箱问题。 Bin packing 有一些聪明的精确算法，但我不确定如何调整它们，而且它们很难实现。这是非常好的 First Fit Decreasing approximation 的模拟(原始版本的 11/9 渐近近似比率；不知道新版本是否好)。

首先从数据库中转储所有任务及其依赖项。使用 Kahn's algorithm 的变体对任务进行拓扑排序其中，在之前已经选择了所有依赖关系的所有任务中，选择最长的作为下一个。将此任务安排在第一组中，它既适合又不在依赖项之前。