作业分配问题

Question

我有n个人，需要做n个任务，每个任务需要(x人日)，任务具有依赖性，如任务A必须在任务B完成后开始。我该怎么安排呢?非常感谢!

我为这个问题设置了4条规则:

1. 一个任务可以设置最多的人来做它(如5)
2. 任务之间存在逻辑依赖
3. 一项任务将花费确定的工时
4. 每天同时工作的人数不能超过当前人数(n)

规则在上面，但是我不知道如何计算最小总时间。请告诉我一个解决的方法或者一些启发，非常感谢!

Answer 1

进行拓扑排序。

现在你有一系列的事件(time;作业开始/作业结束)

在工作开始时分配一个人，如果有空闲工人，否则等待。

在作业结束时释放一个工人，如果存在，将其分配到等待作业。

Answer 2

这个问题是众所周知的np完全问题。即使是没有依赖关系的简单版本，每个作业只有一个工人，也是np完全的。

所以你可能需要接受一个合理的启发式。

从不依赖于其他作业的作业开始进行广度优先搜索，计算出每个作业从开始到完成的最小时钟时间(该作业上的最大工人数，以及与之相关的所有内容，即使实际上不可能)。

现在你从顶部开始。总是按照以下规则给工人分配工作:

1. 第一个完成的最长时钟时间。
2. 打破关系，支持最长的工作。
3. 打破关系，支持最少最多工人的工作。

换句话说，你正在优先安排人们在关键路径和任何缓慢的工作上工作。