当前位置: 首页 > 工具软件 > DAG-Runner > 使用案例 >

DAG任务

籍弘伟
2023-12-01

有向无环图任务调度算法

DAG ----- 图论中,如果有向图中任意一个顶点从该点出发经过任意边都无法回到该点,那么这个图称为有向无环图。

DAG常常用于多个任务的调度,各个任务之间可能存在依赖关系。

所以一个工程划分为不同的任务, 有开始任务和结束任务,通过合理规划执行小任务的顺序,确保总工期最短。



在DAG中,顶点表示事件,顶点之间的连线表示活动,权值表示时间。

设x为源点,y为汇点,v为其中一个事件,

v最早可发生时间ve(v)即x到v的最长路径。

vl(v)即v最晚发生时间即ve(y)- max(vy)

当ve(v) = vl(v) ,v为关键路径。


 类似资料: