节点时差特性的优化措施

节点时差的特性可总结为以下几个定理及推论。

工序间节点时差特性定理　节点时差是两个相邻工序的共用时差，设工序（i，j）和（j，k）为两相邻工序，则

证明：因为

所以

即

又因为

ΔFFjk=LFk-LFj-Tjk=LFk-Tjk-ESj+ESj-LFj

=[LFk-(ESj+Tjk)]-(LFj-ESj)

=[LFjk-(ESjk+Tjk)]-(LFj-ESj)

=(LFjk-EFjk)-(LFj-ESj)

所以

即

TFj=TFjk-ΔFFjk

证毕。

路线段节点时差特性定理　CPM网络中任意两个节点的节点时差之差等于这两个节点间任意路线段的前单时差与后单时差之差。

证明：设任意节点（i）和（j）之间的任意一条路线段为

则

所以

又因为

ΔFFμ(i,j)=ΔFFia+ΔFFab+ΔFFbc+…+ΔFFef+ΔFFfg+ΔFFgj

=(LFa-LFi-Tia)+(LFb-LFa-Tab)+(LFc-LFb-Tbc)+…

+(LFf-LFe-Tef)+(LFg-LFf-Tfg)+(LFj-LFg-Tgj)

=LFj-LFi-(Tia+Tab+Tbc+…+Tef+Tfg+Tgj)

即

所以

即

证毕。

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

推论3.2　任意节点与源点之间的任意路线段的前单时差大于等于后单时差；任意节点与汇点之间的任意路线段的后单时差大于等于前单时差。

证明：在上述定理的证明中，令（i）=（1），在CPM网络中TF1=0，由式（3-22）得

因为TFj≥0，所以

同理，令节点（j）为汇点，即（j）=（w），在CPM网络中TFw=0，由式（3-22）得

因为TFi≥0，所以

证毕。

推论3.3　任意节点的节点时差，等于该节点与源点之间最长路线段的前单时差（即前主链的前单时差），也等于该节点与汇点之间最长路线段的后单时差（即后主链的后单时差）。

证明：在推论3.2证明中，令（i）=（1），则TFi=TF1=0。再令=0，由前主链定义得(www.xing528.com)

再由式（3-22）得

同理，在推论3.2证明中，令（j）=（w），则TFj=TFw=0，再令ΔFFμ（i，w）=0，由后主链定义得

再由式（3-22）得

证毕。

路线节点时差的特性定理 经过任意节点（k）的最长路线与关键路线的路长之差等于该节点的节点时差，这条最长路线就是该节点的特征路线，记为，即

证明：根据前主链定理和后主链定理得

对于经过节点（k）的任意路线μk，有|μk|=|μ（1，k）|+|μ（k，w）|。由式（3-28）得

所以

再由式（3-28）得

所以

证毕。

最小节点时差分布定理　节点时差最小的非关键节点，必定全部分布在与关键节点相连的节点时差最小的节点的特征路线上，且它们的节点时差相等。

证明：用反证法证明。令Ω表示所有关键节点的集合，即Ω={（i）|TFi=0}，则就表示网络中所有非关键节点的集合，即={（i）|TFi＞0}。

设节点（j）是网络中节点时差最小的非关键节点，即TFj=min{TFk|（k）∈}。同时，假设节点（j）不在与关键节点相连的节点时差最小的非关键节点的特征路线上，则必定可以找到节点（j）的特征路线，设其为

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

TFa≤TFb≤TFc≤…≤TFg≤TFj

1）若TFa＞0，由于TFj=min{TFk|（k）∈}，所以

由工序间节点时差特性得

因为μ（a，j）⊂，所以

由式（3-31）得TFa=TFj，所以

因为μ（j，w）⊂，所以

ΔFFμ(j,w)=0

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

由后主链定义得

因为μ（1，a）⊂，所以

由前主链定义得

由式（3-32）和式（3-33）可知，也是节点（a）的特征路线，即=。而节点（a）与源点（1）相连，且TFa=min{TFk|（k）∈}，即节点（j）在与关键节点相连的节点时差最小的非关键节点（a）的特征路线上，与原假设矛盾。

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

依此类推，在TFc＞0，…，TFg＞0的各个情况下，其结论都与原假设矛盾。

3）若TFa=TFb=TFc=…=TFg=0，则节点（l），…，（r），（s），（t）是关键节点，就是与关键节点相连的节点时差最小的非关键节点（j）的特征路线，与原假设矛盾。

（2）对于后主链，同理可证，在TFt＞0，TFs＞0，TFr＞0，…，TFl＞0的各个情况下，其结论也都与原假设矛盾。

而若TFt=TFs=TFr=…=TFl=0，则节点（l），…，（r），（s），（t）是关键节点，就是与关键节点相连的节点时差最小的非关键节点（j）的特征路线，也与原假设矛盾。

由此可见，原假设不成立。

所以节点时差最小的非关键节点，必定分布在与关键节点相连的节点时差最小的节点的特征路线上，并且它们的节点时差都等于网络中的最小节点时差。因此寻找整个网络中节点时差最小的非关键节点，只需要在关键节点的紧前节点和紧后节点中寻找出节点时差最小的非关键节点，并找出其特征路线，则所有节点时差最小的非关键节点都必定在这些特征路线上。

证毕。