计算计划相关任务的完成时间

Question

我试图计算一个项目进度表的最小完成时间，它有n个任务，每个任务可以有一个依赖性任务。你知道吗

示例

Task ID    Duration Days    Dependent ID
1          10               0
2          3                0
3          6                1
4          5                2
5          10               1

没有依赖关系的任务被称为依赖ID 0

根据上述任务表，项目工期应按20天计算。你知道吗

应该用什么算法来计算这个？你知道吗

Answer 1

这个问题可以用一种称为PERT图的技术来解决，PERT图只是一个有向图，其中节点表示“事件”，即“活动”或活动组的完成。您需要一个开始事件和一个结束事件，示例中的其他事件将是每个任务的完成。图的边缘是箭头，表示从先决条件事件到结果的任务，权重等于完成任务的时间。所以有一个箭头，从10的开始到1，从3的开始到2，从6的1到3，从10的1到5，从5的2到4，从3，4，5到0的结尾。你知道吗

然后你从头到尾地工作，填写到达每个事件节点的时间。到达起点的时间是0，到达1的时间是10，到达2的时间是3，到达3的时间是16（将到达1的时间加到重量6中），到达4的时间是3+5=8，到达5的时间是10+10=20，到达终点的时间是max（16+0,8+0,20+0）=20。填充到达图节点的时间是动态规划的一个应用。节点可以按照拓扑排序图所给出的顺序填充。你知道吗