2024-09-28 17:19:24 发布
网友
我试图计算一个项目进度表的最小完成时间,它有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天计算。你知道吗
应该用什么算法来计算这个?你知道吗
这个问题可以用一种称为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。填充到达图节点的时间是动态规划的一个应用。节点可以按照拓扑排序图所给出的顺序填充。你知道吗
假设任务0在第0天完成。你知道吗
在表中添加一个新列“完成日期”。你知道吗
在任务列表中,将当前任务的持续时间添加到它所依赖的任务的完成日期。将其存储为当前任务的完成日期。你知道吗
找到最大完成日。你知道吗
这个问题可以用一种称为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。填充到达图节点的时间是动态规划的一个应用。节点可以按照拓扑排序图所给出的顺序填充。你知道吗
假设任务0在第0天完成。你知道吗
在表中添加一个新列“完成日期”。你知道吗
在任务列表中,将当前任务的持续时间添加到它所依赖的任务的完成日期。将其存储为当前任务的完成日期。你知道吗
找到最大完成日。你知道吗
相关问题 更多 >
编程相关推荐