16-L.02 作业网络和关键路径

离散数学基础
2017-11-19
•单元内容提示
−作业网络
−关键路径
−求关键路径的标号法
•定义. 作业网络。

−设有向连通网络 (G, w)：
(1)G 的无回路假设 (DAG: Directed Acyclic Graph 有向无环图)；
(2)网络中有且只有一个结点的入度为0，称为源点或任务开始点；有且只有一个
结点的出度为0，称为汇点或任务完成点。

(3)每一条有向边表示一个作业（工序），其所带的非负实数权是完成该作业所
需时间（或耗散值）；
(4)每一个结点表示其负关联作业的结束和正关联作业的开始；
(5)作业开始条件：该作业起始点的所有负关联作业全部完成；
•定义. 关键路径
−关键路径是作业网络中从源点到汇点的一条最长路径
−处于关键路径上的作业称为关键作业
−关键路径不一定是唯一的
−关键路径的长度为完成任务所需的必要时间 T，也称为任务完成的预期时间 T −任务在源点的开始时刻通常定义为 0，则结束时刻至少是 T
•定义. 作业最早开始时间
−设作业 a = (v i, v i)，从源点到作业 a 的始点 v i 的最长路径长度 t i 称为作业
a 的最早开始时间。

•定义. 作业最晚开始时间
−设作业 a = (v i, v i)，从作业 a 的始点 v i 到汇点的最长路径长度 t′i 称为作业
a 的最晚开始时间。

−作业 a 最晚可开始于 (T‐t′i) 时刻而不会影响任务完成的预期时间 T。

•定义. 缓冲时间
−不影响任务完成的预期时间 T 的前提下，作业 a = (v i, v j) 的缓冲时间为 b i= (T‐t′i) ‐ t i 。

•引理2.
−有向无环图 (DAG) 中至少有一个结点的入度为 0。

−证明：从一个入度不为0的结点逆向构造一条有向初等道路，对于有穷图，上述构造过程必在一个入度为0的结点上结束。

•定理2.
−设图 G =(V, A) 为有向无环图，则可将其结点适当编号为 v1 , v2 , … , v n , 使得对任意 i<j，有 (v j , v i)∉A。

−证明：构造法（拓扑排序算法）
−在 G 中选入度为0的顶点，令为 v1；余图 G‐{v1} 仍为 DAG，在其中选一入度为0的顶点，令为v2；余图 G‐{v1, v2} 也为DAG，在其中选一入度为0的顶点，令为v3；…… ；G‐{v1, v2, .., v n‐1} 的余下顶点令为 v n；
−由上述过程，对任意 (v j, v i)∈A，只有先选中 v j 后，v i 才有可能在随后的余图中因入度为0而被选中编号，故 j<i。

因此上述编号为所求。

•定理3.
−按上述结点编号构造实数序列 u1, u2, …, u n，其中 u1=0，u j = max{u l+w lj| 1≤l <j}，w ij 为 (v i , v j)∈A 时的边的非负实权，规定 (v i , v j)∉A时 w ij = ‐∞。

则 u j 为 v1 到 v j 的最长路径长度。

−证明：对 j 归纳。

−归纳基始：j=2 时，u2=w12。

由编号法，只有 v1 能到达 v2，所以 w12 为 v1 到 v2 的最长路径长度。

−归纳假设：设 j<k 时结论成立。

−归纳过程：j=k 时，由编号法只有 v1, v2, … , v k−1 才能到达 v k，而 {u l+w l k|1≤l≤k‐1} 中的每一项对应于上述一种可能走法的最长路经长度，最大值 u k=
max{u l+w lj|1≤l<j} 即为 v1 到 v k 的最长路径长度。

综上得证。

•标号法.
−设有作业网络 (G, w)， w ij 为 (v i , v j)∈A 时的边的非负实权，规定 (v i , v j)∉A时
w ij = ‐∞。

邻接矩阵 C=(c ij)n×n；源点 deg‐(v1)=0，求源点到汇点的关键路径。

0. 初始化：u1(1) ←0, u j(1)←w1j,
d j(1) ←c2j+c3j+…+c nj, (j=2..n)；S(1) ← {v1}, m ←1；
1. 选固定标号：在 V‐S(m) 中求 v k，使得 d k(m) =0。

2. 判结束：令 S(m+1) ← S(m) ∪{v k}；若 m = n‐1，结束。

3. 修改临时标号：对所有 v j∈V‐S(m+1)，令
u j(m+1) =max{u j(m), u k(m)+w kj}，d j(m+1) ← d j(m) ‐ c kj ；
m ←m+1，转1。

•讨论1.
−标号法是将 [定理2] 证明中的拓扑排序过程和 [定理3]证明中的归纳过程相结合的结果。

•讨论2.
−比较标号法和 Dijkstra 算法。

•结论.
−算法的结果得到标记各作业最早开始时间的向量
U =(u1, u2, …, u n)
其中 u n 的值为关键路径长度 T。

−记录 u j 的迭代过程，可获得一条最长路径编号。

−将 G 的弧全部反向，得到作业网络 N′，按标号法得到的 U 向量即为原网络中各点到汇点的最长路径，记为 U′。

各点的缓冲时间由向量 (T‐U′)‐U 表出。

•例：下图是一个作业网络，v1 是源，v8 是汇。

求源点到汇点的关键路径。

−解：用绿色表示S中的结点。

−结果 U = ( 0, 8, 5, 6, 17, 13, 15, 22 )，这是从 v1 到达各点的最长路径长度，关键路径长度 T = u8 =22。

•例：
−将原图反向，求得 U′ = ( 22, 14, 17, 5, 5, 9, 3, 0 ) 为原图各点到汇点的最长路经长度。

在保持 T 不变的条件下，各点的缓冲时间向量
(T ‐ U′ ) ‐ U = ( 0, 0, 0, 11, 0, 0, 4, 0 )
•下一单元内容提示
−TSP 问题；求解 TSP 问题的近似算法。