我要执行一组步骤，每个步骤都有一个时间（以分钟为单位）。
我也有一组依赖项（即，步骤7必须在步骤5之后）。
假设没有循环，将它们分组的正确算法是什么，其中每个组的总时间少于一定的时间。
显然，除非相关性给出线性顺序，否则存在各种安排步骤的方法，这是容易/可行的，可以得出最佳结果（即，需要最少的组）。
目前，我的步骤和依赖项是使用SQL编写的，但是我很乐意用另一种语言提供解决方案。
当没有依赖关系时，这就是NP硬装箱问题。Bin打包有一些聪明的精确算法，但是我不确定如何适应它们，而且无论如何也很难实现它们。这是一个很好的First Fit Decreasing近似值（原始值的11/9渐近近似值；不知道新版本是否很好）的类似物。
首先，将所有任务及其依赖项转储到数据库之外。使用Kahn算法的变体对任务进行拓扑排序，其中，在先前已全部选择依赖项的所有任务中，选择最长的任务作为下一个。将该任务安排在既适合又不在依赖之前的第一组中。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句