后单时差的特性优化之道

本书把后单时差的主要特性总结为以下几个定理。

前主链定理 任意节点与源点之间最长路线段的路长，等于该节点的最早开始时间，这条最长路线段称为该节点的前主链。该节点前主链的路长减去该节点与源点之间的任意路线段的路长之差，等于该任意路线段上各工序的后单时差之和。

证明：设任意节点（i）与源点（1）之间的任意路线段为

根据后单时差的定义

在CPM网络中，ES1=0。同时，T1a+Tab+Tbc+…+Tef+Tfg+Tgi=|μ（1，i）|，其中Tij表示工序（i，j）的工期，μ（1，i）表示从源点（1）到节点（i）之间任意一条路线段，|μ（1，i）|表示路线段μ（1，i）的路长。所以

即

当=0时，|μ（1，i）|取得最大值，由前主链定义得

由式（3-1）、式（3-2）得

即

由式（3-1）～式（3-3）可知，该定理得证。

证毕。

由此可得出寻找任意节点的前主链的方法，即从该节点开始依次向前寻找后单时差为零的工序，直至源点所得到的路线段。

路线后单时差与路长的关系定理　CPM网络中任意一条路线上，各工序的后单时差之和等于关键路线与该路线的路长之差。

证明：在前主链定理的证明中，令（i）=（w），（w）表示汇点，由式（3-1）得(www.xing528.com)

其中，μ是表示从源点到汇点的任意一条路线。

在CPM网络中

ESw=|μ∇|

所以

其中，μ∇表示从源点到汇点的最长路线，即关键路线。

证毕。

后单时差定理　设工序（i，j）为节点（j）的任意紧前工序，设节点（j）与源点（1）之间的最长路线段为，工序（i，j）与源点（1）之间的最长路线段为，二者路长之差||-||等于该工序（i，j）的后单时差，即

证明：由前主链定理得

所以

而

所以

即

证毕。