§12.2统筹图中有关参数的计算
关键路线（critical path）：统筹图中从总开工事项顶点到总完工事项顶点的最长的有向路.
华罗庚先生称关键路线为主要矛盾线.
关键路线的长度：关键路线上各工序时间之和.
关键工序：关键路线上的工序.
如对统筹图
从总开工事项顶点到总完工事项顶点的各有向路及长度分别为有向路
长度
2+5+5=12
2+6+3+5=16
2+6+4+6=18
2+3+5=10
2+4+6=12
5+5+3+5=18
5+5+4+6=20*
5+9+6=20
易见，和都是关键路线.
显然，关键路线的长度就是生产过程的完工期或最早可能完工期.
在关键路线上，一个（关键）工序的开工事项即为其紧前工序的完工事项.关键工序完工事项的延长或缩短必将导致生产过程的完工期的推迟和提前.
在非关键路线上，工序的开工可在其紧前工序完工后的一定时间范围内推迟，而不影响生产过程的完工期.
统筹方法的根本任务就是本着“向关键路线要时间，向非关键路线要资源”的指导思想，作出最优或最满意的生产计划.
关键路线的求解：
标号法：设统筹图中各顶点分别编号为，，…，.
步骤：
1.给顶点以标号.
2.按照统筹图中各顶点的编号顺序，依次给顶点，…，以标号，其中，，是弧的长度，并将取最大值的弧改为粗线.
3.当顶点被标号时，即得一条关键路线，且其长度为.
注：顶点的标号恰是以顶点为开工事项的工序的最早可能开工时间.特别地，是生产过程的完工期.
求统筹图的关键路线的标号法与求解最短路问题的Dijkstra算法既有所类似，又有根本区别：（1）标号法是求最长路，而Dijkstra算法是求最短路；（2）对标号法，下一个待标号的顶点是在计算前按照各顶点的编号顺序依次确定下来的，而对Dijkstra算法，下一个待标号的顶点是在上一个顶点被标号后，对尚未被标号的顶点通过搜索确定的.
例1求下面统筹图的一个关键路线：
解：利用标号法，得
关键路线有两条，分别为和，其长度均为20.▍
统筹图中有关参数的计算：
1.工序的最早可能开（完）工时间一个工序必须在其所有紧前工序都完工后才能开工，此时刻称为其最早可能开工时间（probably earliest starting time），记作：.
由标号法知，.
工序的最早可能完工时间（probably earliest finishing time）：.
显然，.
2.工序的最晚必须开（完）工时间一个工序可能有若干个紧后工序.为不影响其紧后工序的如期开工，工序应有一个晚必须开工的时刻，此时刻称为工序
在其所有紧前工序都完工后才能开工，此时刻称为其最晚必须开工时间（required latest starting time），记作：.
工序的最晚必须完工时间（required latest finishing time）：.
显然，.
最晚必须开工时间的计算：
基本思想：（倒退计算）利用标号法求解关键路线，得生产过程的完工期；再从顶点开始，依次倒退地算出以每一顶点为完工事项的工序的最晚必须完工时间，从而求出工序的最晚必须开工时间.
算法步骤：
1.利用标号法求解关键路线.
2.给顶点以标号.
3.按照统筹图中各顶点的编号的反向顺序，依次给顶点，…，以标号，其中，，是弧的长度.
3.当顶点被标号时，即得各工序的最晚必须完工时间，从而得最晚必须完工时间.
由上述算法知，顶点的标号恰是以顶点为完工事项的工序的最晚必须完工时间.特别地，是生产过程的完工期，即生产过程的最晚必须完工时间.于是，，.
例1（续）求下面统筹图中的各工序的一个关键路线：
解：利用标号法，得
一般地，可将两个标号在同一个统筹图中标出来：
▍
3.工序的机动时间（）：最晚必须开工时间与最早必须开工时间之差，即
.
工序的机动时间表示在不影响生产过程的总完工期的前提下，该工序的完工期可能推迟的最长时间.显然，关键工序的机动时间为0（关键工序必须按期完工）.
利用统筹方法计算出有关数据，有利于管理人员掌握全局，抓住关键，处理生产过程中出现的各种问题，科学地组织整个生产过程.
关键路线（critical path）：统筹图中从总开工事项顶点到总完工事项顶点的最长的有向路.
华罗庚先生称关键路线为主要矛盾线.
关键路线的长度：关键路线上各工序时间之和.
关键工序：关键路线上的工序.
如对统筹图
从总开工事项顶点到总完工事项顶点的各有向路及长度分别为有向路
长度
2+5+5=12
2+6+3+5=16
2+6+4+6=18
2+3+5=10
2+4+6=12
5+5+3+5=18
5+5+4+6=20*
5+9+6=20
易见，和都是关键路线.
显然，关键路线的长度就是生产过程的完工期或最早可能完工期.
在关键路线上，一个（关键）工序的开工事项即为其紧前工序的完工事项.关键工序完工事项的延长或缩短必将导致生产过程的完工期的推迟和提前.
在非关键路线上，工序的开工可在其紧前工序完工后的一定时间范围内推迟，而不影响生产过程的完工期.
统筹方法的根本任务就是本着“向关键路线要时间，向非关键路线要资源”的指导思想，作出最优或最满意的生产计划.
关键路线的求解：
标号法：设统筹图中各顶点分别编号为，，…，.
步骤：
1.给顶点以标号.
2.按照统筹图中各顶点的编号顺序，依次给顶点，…，以标号，其中，，是弧的长度，并将取最大值的弧改为粗线.
3.当顶点被标号时，即得一条关键路线，且其长度为.
注：顶点的标号恰是以顶点为开工事项的工序的最早可能开工时间.特别地，是生产过程的完工期.
求统筹图的关键路线的标号法与求解最短路问题的Dijkstra算法既有所类似，又有根本区别：（1）标号法是求最长路，而Dijkstra算法是求最短路；（2）对标号法，下一个待标号的顶点是在计算前按照各顶点的编号顺序依次确定下来的，而对Dijkstra算法，下一个待标号的顶点是在上一个顶点被标号后，对尚未被标号的顶点通过搜索确定的.
例1求下面统筹图的一个关键路线：
解：利用标号法，得
关键路线有两条，分别为和，其长度均为20.▍
统筹图中有关参数的计算：
1.工序的最早可能开（完）工时间一个工序必须在其所有紧前工序都完工后才能开工，此时刻称为其最早可能开工时间（probably earliest starting time），记作：.
由标号法知，.
工序的最早可能完工时间（probably earliest finishing time）：.
显然，.
2.工序的最晚必须开（完）工时间一个工序可能有若干个紧后工序.为不影响其紧后工序的如期开工，工序应有一个晚必须开工的时刻，此时刻称为工序
在其所有紧前工序都完工后才能开工，此时刻称为其最晚必须开工时间（required latest starting time），记作：.
工序的最晚必须完工时间（required latest finishing time）：.
显然，.
最晚必须开工时间的计算：
基本思想：（倒退计算）利用标号法求解关键路线，得生产过程的完工期；再从顶点开始，依次倒退地算出以每一顶点为完工事项的工序的最晚必须完工时间，从而求出工序的最晚必须开工时间.
算法步骤：
1.利用标号法求解关键路线.
2.给顶点以标号.
3.按照统筹图中各顶点的编号的反向顺序，依次给顶点，…，以标号，其中，，是弧的长度.
3.当顶点被标号时，即得各工序的最晚必须完工时间，从而得最晚必须完工时间.
由上述算法知，顶点的标号恰是以顶点为完工事项的工序的最晚必须完工时间.特别地，是生产过程的完工期，即生产过程的最晚必须完工时间.于是，，.
例1（续）求下面统筹图中的各工序的一个关键路线：
解：利用标号法，得
一般地，可将两个标号在同一个统筹图中标出来：
▍
3.工序的机动时间（）：最晚必须开工时间与最早必须开工时间之差，即
.
工序的机动时间表示在不影响生产过程的总完工期的前提下，该工序的完工期可能推迟的最长时间.显然，关键工序的机动时间为0（关键工序必须按期完工）.
利用统筹方法计算出有关数据，有利于管理人员掌握全局，抓住关键，处理生产过程中出现的各种问题，科学地组织整个生产过程.
