总时差特性优化版

总时差定理　通过任意工序（i，j）的路长最大的路线与关键路线的路长之差等于该工序的总时差，这条路长最大的路线称为该工序的特征路线，记为，即

证明：由前主链、后主链和特征路线的定义得

由式（3-1）、式（3-4）可知，为经过工序（i，j）的路长最大的路线，所以

再由式（3-3）、式（3-4）得

所以

证毕。

特征路线定理　在经过工序（i，j）的最长路线（特征路线）上，工序（i，j）的总时差最大。在前主链上，前面工序的总时差都小于等于后面工序的总时差，而且任何工序的总时差都等于该工序结束节点的节点时差；在后主链上，后面工序的总时差都小于等于前面工序的总时差，而且任何工序的总时差都等于该工序开始节点的节点时差。

证明：假设经过工序（i，j）的特征路线为

其中（1）为源点，（w）为汇点。

因为工序（b，c）的总时差TFbc=TFc+，且节点（b），（c）∈，所以

同理可证

又因为TFbc=ΔFFbc+TFb，由式（3-12）得

TFc=ΔFFbc+TFb

所以

TFb≤TFc

同理可证

因为TFij=ΔFFij+TFi，所以

由式（3-12）～式（3-14）得

对于后主链，有

TFst=ΔFFst+TFs

因为节点（s），（t）∈，所以ΔFFst=0，可得TFst=TFs。

同理可证

又因为TFst=TFt+，由式（3-16）得

所以

TFs≥TFt

同理可证

因为TFij=+TFj，所以

由式（3-16）～式（3-18）得

因此所证定理成立。

证毕。

最小非零总时差工序分布定理　CPM网络中总时差最小的非关键工序，必定全部分布在与关键节点相连的总时差最小的非关键工序的特征路线上。

证明：用反证法证明。假设工序（i，j）是网络中总时差最小的非关键工序，即TFij=min{TFmn|TFmn＞0}；同时假设工序（i，j）不在与关键节点相连的总时差最小的非关键工序的特征路线上，则必定可以找到工序（i，j）的特征路线，设为

（1）对于前主链，由特征路线定理得

TF1a≤TFab≤TFbc≤…≤TFgi≤TFij

1）若TF1a＞0，因为TFij=min{TFmn|TFmn＞0}，所以(www.xing528.com)

因为TFab=TFa+ΔFFab，根据特征路线定理

TF1a=TFa

由式（3-20）得

TF1a=TFab

可得

ΔFFab=0

同理可证

ΔFFab=ΔFFbc=…=ΔFFgi=ΔFFij=0

所以

ΔFFμ(a,j)=ΔFFab+ΔFFbc+…+ΔFFgi+ΔFFij=0

因为μ（j，w）⊂，所以ΔFFμ（j，w）=0，可得

ΔFFμ(a,w)=ΔFFμ(a,j)+ΔFFμ(j,w)=0

同理可证

所以也是工序（1，a）的特征路线，即=。

而工序（1，a）与源点（1）相连，（1）为关键节点，且TF1a=min{TFmn|TFmn＞0}，即工序（i，j）在与关键节点相连的总时差最小的非关键工序（1，a）的特征路线上，与原假设矛盾。

2）若TF1a=0，而TFab＞0，同理可证也是工序（a，b）的特征路线，即=。而节点（b）与关键节点（a）相连，且TFab=min{TFmn|TFmn＞0}，与原假设矛盾。

依此类推，TFc＞0，…，TFg＞0，都与原假设矛盾。

3）若TF1a=TFab=TFbc=…=TFgi=0，则节点（a），（b），（c），…，（g），（i）是关键节点，是与关键节点相连的总时差最小的非关键工序（i，j）的特征路线，与原假设矛盾。

（2）对于后主链，同理可证，若TFtw＞0，TFst＞0，TFrs＞0，…，TFjl＞0，与原假设矛盾；若TFtw=TFst=TFrs=…=TFjl=0，也与原假设矛盾。

由此可见原假设不成立。

所以网络中总时差最小的非关键工序，必定全部分布在与关键节点相连的最小总时差的非关键工序的特征路线上。

证毕。

因此寻找整个网络中总时差最小的非关键工序，只需要在关键节点的紧前工序和紧后工序中找出总时差最小的非关键工序，并找出其特征路线即可，所有总时差最小的非关键工序必定都在这些特征路线上。

由该定理所得的推论如下。

推论3.1　只包含一个关键节点的最小总时差非关键工序，其特征路线上必定至少存在另一个最小总时差非关键工序。

证明：假设工序（g0，i）是网络中总时差最小的非关键工序，即

TFg0i=min{TFmn|TFmn＞0}

其中，节点（g0）是关键节点，（i）是非关键节点，则必定可以找到工序（g0，i）的后主链，设为=（i）→（j）→…→（s）→（t）→（w）。因为节点（i）是非关键节点，即TFi＞0，由特征路线定理得

TFij=TFi≤TFg0i

而TFg0i=min{TFmn|TFmn＞0}，所以

TFij=TFg0i=min{TFmn|TFmn＞0}

同理可证，网络中总时差最小的非关键工序（j，l0）的前主链中必然存在至少一个最小总时差非关键工序[其中节点（l0）是关键节点，（j）是非关键节点]。

综上所述可知，该推论成立。

证毕。