数学相关概念和定理解析

平行工序，前主链和后主链等概念在前面的章节中已经提到，在本节中不再赘述。本节需要用到的其他基本概念如下。

平行工序　不在同一条路线上的工序，因而没有先后顺序关系。

亏值　n个平行工序A1，A2，…，An调整为顺序工序A1→A2→…→An后，网络总工期因此而拖延的时间称为亏值，记为[A1，A2，…，An]。

隔断　当EFAi＜ESAi+1时，称在Ai与Ai+1之间存在一个隔断。

特征路线及其求法　工序A的特征路线是过该工序最大路长的路线，记作：。

，其中i是工序A的开始节点，j是工序A的结束节点，是工序A的前主链，是工序A的后主链，=ESi且=μ∇-LFj，μ∇是指关键路线的路长，ESi是节点i最早开始时间，LFj是节点j的最迟结束时间。

工序链（A1A2…An）的特征路线是过该工序链的最大路长的路线，记作：A2…An。，其中i是工序A1的开始节点，j是工序An 的结束节点。

本节用到的基本定理为最小路长定理。(www.xing528.com)

最小路长定理　将n个可分解的平行工序A1，A2，…，An调整为顺序工序，有无数种调整方式，每种调整方式都经过所有工序的最大路长，所有最大路长的最小值为ESAi+TA1+TA2+…+TAn-LFAj+μ∇，其中Ai表示A1，A2，…，An中ES最小工序，Aj表示A1，A2，…，An中LF最大工序，Ai和Aj可为同一工序。

证明过程如下。

（1）过任意一个顺序工作组的最大路长均大于等于ESAi+TA1+TA2+…+TAn-LFAj+μ∇（Ai表示ES最小工序，Aj表示LF最大工序，Ai和Aj可为同一工序）。由于n个平行工序是任意可分的，不妨设A1可分解为，，…，；A2可以分解为，，…，；An可分解为，，…，，其中是的紧前工序，是的紧前工序，…，是的紧前工序（i=1，2，…，n），并组成顺序工序组→→…→，→→…→，…。以其中一种情况为例证明。

从众多的顺序工序组中任选一个→→…→→→，显然，=ESAh，=LFAm。不妨设工序的开始节点为l，工序的结束节点为k，则有过→→…→→→最大路长：

因为Ai表示ES最小工序，故ESAi≤ESAh，又因为Aj表示LF最大工序，故LFAj≥LFAm，因此：

（2）可否找到这样的顺序工序组，使过其的最大路长为ESAi+TA1+TA2+…+TAn-LFAj+μ∇。显然，→→→…→是符合要求的路线。

（3）综合（1）、（2），定理成立。