运筹学讲义 §12.2统筹图中有关参数的计算 关键路线( critical path):统筹图中从总开工事项顶点到总完工事项顶点的最长的有向路 华罗庚先生称关键路线为主要矛盾线 关键路线的长度:关键路线上各工序时间之和 关键工序:关键路线上的工序 如对统筹图 d 3 从总开工事项顶点①到总完工事项顶点O的各有向路及长度分别为 有向路 长度 ①→②→⑤→⑦ 2+5+5=12 ①→②→①→⑤→⑦|2+6+3+5=16 ①→@→④→⑥→⑦ 2+6+4+6=18 ①→④→⑤→⑦ 2+3+5=10 ①→④→⑥→⑦ 2+4+6=12 ①→③→④→⑤→⑦ +5+3+5=18 ①→→④→⑥→05+5+4+6=20° ①→③→⑥→⑦ 5+9+6=20 易见,①→⑧→④→⑥→①和①→③→)⑥→⑦都是关键路线 显然,关键路线的长度就是生产过程的完工期或最早可能完工期. 在关键路线上,一个(关键)工序的开工事项即为其紧前工序的完工事项.关键工序完工事项的 延长或缩短必将导致生产过程的完工期的推迟和提前 在非关键路线上,工序的开工可在其紧前工序完工后的一定时间范围内推迟,而不影响生产过程 的完工期 统筹方法的根本任务就是本着“向关键路线要时间,向非关键路线要资源”的指导思想,作出最 优或最满意的生产计划 关键路线的求解: 标号法:设统筹图中各顶点分别编号为①,②,…, 步骤:
运 筹 学 讲 义 1 §12.2 统筹图中有关参数的计算 关键路线（critical path）：统筹图中从总开工事项顶点到总完工事项顶点的最长的有向路. 华罗庚先生称关键路线为主要矛盾线. 关键路线的长度：关键路线上各工序时间之和. 关键工序：关键路线上的工序. 如对统筹图 从总开工事项顶点○1 到总完工事项顶点○7 的各有向路及长度分别为 有向路 长度 ○1 → ○2 → ○5 → ○7 ○1 → ○2 → ○4 → ○5 → ○7 ○1 → ○2 → ○4 → ○6 → ○7 ○1 → ○4 → ○5 → ○7 ○1 → ○4 → ○6 → ○7 ○1 → ○3 → ○4 → ○5 → ○7 ○1 → ○3 → ○4 → ○6 → ○7 ○1 → ○3 → ○6 → ○7 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 → ○3 → ○4 → ○6 → ○7 和○1 → ○3 → ○6 → ○7 都是关键路线. 显然，关键路线的长度就是生产过程的完工期或最早可能完工期. 在关键路线上，一个（关键）工序的开工事项即为其紧前工序的完工事项.关键工序完工事项的 延长或缩短必将导致生产过程的完工期的推迟和提前. 在非关键路线上，工序的开工可在其紧前工序完工后的一定时间范围内推迟，而不影响生产过程 的完工期. 统筹方法的根本任务就是本着“向关键路线要时间，向非关键路线要资源”的指导思想，作出最 优或最满意的生产计划. 关键路线的求解： 标号法：设统筹图中各顶点分别编号为○1 ，○2 ，…，○n . 步骤：
运筹学讲义 1.给顶点①以标号t(1)=0 2按照统筹图中各顶点的编号顺序,依次给顶点回,…,回以标号1(2)…,(n) 其中()=max{t(k)+w(k,i)},i=2,3,…,n,w(k,是弧(k,i)的长度,并 将取最大值的弧(k,)改为粗线 3.当顶点○被标号时,即得一条关键路线,且其长度为r(n) 注:顶点O的标号(i)恰是以顶点①为开工事项的工序的最早可能开工时间特别地,t(m)是生 产过程的完工期. 求统筹图的关键路线的标号法与求解最短路问题的 Di jkstra算法既有所类似,又有根本区别 (1)标号法是求最长路,而 Di jkstra算法是求最短路;(2)对标号法,下一个待标号的顶点是在计 算前按照各顶点的编号顺序依次确定下来的,而对 Dijkstra算法,下一个待标号的顶点是在上一个 顶点被标号后,对尚未被标号的顶点通过搜索确定的 例1求下面统筹图的一个关键路 解:利用标号法,得 0(1 关键路线有两条,分别为①→③→④→>⑥→⑦和①→③→⑥→⑦,其长度均为20.L 统筹图中有关参数的计算:
运 筹 学 讲 义 2 1.给顶点○1 以标号 t(1) = 0. 2.按照统筹图中各顶点的编号顺序，依次给顶点○2 ，…，○n 以标号 t(2), ,t(n) ， 其中 t(i) max{t(k) w(k,i)} k i = + ，i = 2,3, ,n，w(k,i) 是弧 (k,i) 的长度，并 将取最大值的弧 (k,i) 改为粗线. 3.当顶点○n 被标号时，即得一条关键路线，且其长度为 t(n) . 注：顶点○i 的标号 t(i) 恰是以顶点○i 为开工事项的工序的最早可能开工时间.特别地， t(n) 是生 产过程的完工期. 求统筹图的关键路线的标号法与求解最短路问题的 Dijkstra 算法既有所类似，又有根本区别： （1）标号法是求最长路，而 Dijkstra 算法是求最短路；（2）对标号法，下一个待标号的顶点是在计 算前按照各顶点的编号顺序依次确定下来的，而对 Dijkstra 算法，下一个待标号的顶点是在上一个 顶点被标号后，对尚未被标号的顶点通过搜索确定的. 例 1 求下面统筹图的一个关键路线： 解：利用标号法，得 关键路线有两条，分别为○1 → ○3 → ○4 → ○6 → ○7 和○1 → ○3 → ○6 → ○7 ，其长度均为 20.▍ 统筹图中有关参数的计算：
运筹学讲义 1.工序的最早可能开(完)工时间 一个工序(,j)必须在其所有紧前工序都完工后才能开工,此时刻称为其最早可能开工时间 ( probably earliest starting time),记作:ts(,j 由标号法知,tgs(,八)=1(l) 工序(的最早可能完工时间( probably earliest finishing time):tg(i,j) 显然,tg(,)=lEs(,j)+w(,)=1(1)+(,j 2.工序的最晚必须开(完)工时间 一个工序(i,)可能有若干个紧后工序.为不影响其紧后工序的如期开工,工序(i,)应有一个晚 必须开工的时刻,此时刻称为工序(,) 在其所有紧前工序都完工后才能开工,此时刻称为其最晚必须开工时间( required latest starting time),记作:t1s(,) 工序(的最晚必须完工时间( required latest finishing time):tls(i,j) 显然,tF(ij=ls(,j)+w(,j 最晚必须开工时间的计算: 基本思想:(倒退计算)利用标号法求解关键路线,得生产过程的完工期t(m):再从顶点ω开始, 依次倒退地算出以每一顶点为完工事项的工序的最晚必须完工时间,从而求出工序的最晚必须开工时 算法步骤: 1.利用标号法求解关键路线 2给顶点回以标号l(m)=1(n) 3按照统筹图中各顶点的编号的反向顺序,依次给顶点D ①以标号l(n-1)…,l(1), 其中I()=mn{(k)-w(,k)},j=n-1…1,w(,k)是弧(jk)的长度 3.当顶点①被标号时,即得各工序(,刀)的最晚必须完工时间,从而得最晚必须完工时间
运 筹 学 讲 义 3 1.工序的最早可能开（完）工时间 一个工序 (i, j) 必须在其所有紧前工序都完工后才能开工，此时刻称为其最早可能开工时间 （probably earliest starting time），记作： t (i, j) ES . 由标号法知， t (i, j) t(i) ES = . 工序 (i, j) 的最早可能完工时间（probably earliest finishing time）： t (i, j) EF . 显然， t (i, j) t (i, j) w(i, j) t(i) w(i, j) EF = ES + = + . 2.工序的最晚必须开（完）工时间 一个工序 (i, j) 可能有若干个紧后工序.为不影响其紧后工序的如期开工，工序 (i, j) 应有一个晚 必须开工的时刻，此时刻称为工序 (i, j) 在其所有紧前工序都完工后才能开工，此时刻称为其最晚必须开工时间（required latest starting time），记作： t (i, j) LS . 工序 (i, j) 的最晚必须完工时间（required latest finishing time）： t (i, j) LF . 显然， t (i, j) t (i, j) w(i, j) LF = LS + . 最晚必须开工时间的计算： 基本思想：（倒退计算）利用标号法求解关键路线，得生产过程的完工期 t(n) ；再从顶点○n 开始， 依次倒退地算出以每一顶点为完工事项的工序的最晚必须完工时间，从而求出工序的最晚必须开工时 间. 算法步骤： 1.利用标号法求解关键路线. 2.给顶点○n 以标号 l(n) = t(n) . 3.按照统筹图中各顶点的编号的反向顺序，依次给顶点 ，…，○1 以标号 l(n −1), ,l(1) ， 其中 l( j) min{l(k) w( j,k)} k j = − ， j = n −1, ,1， w( j, k) 是弧 ( j, k) 的长度. 3.当顶点○1 被标号时，即得各工序 (i, j) 的最晚必须完工时间，从而得最晚必须完工时间
运筹学讲义 由上述算法知,顶点①的标号l(j)恰是以顶点④为完工事项的工序(i,j)的最晚必须完工时间 特别地,(n)是生产过程的完工期,即生产过程的最晚必须完工时间.于是,t1(ij)=l(), IIS(iD=LLF(,D-w(i,J=10)-w(i,J) 例1(续)求下面统筹图中的各工序的一个关键路线: ③ d 3 解:利用标号法,得 ⑦20> 20 10 20 一般地,可将两个标号在同一个统筹图中标出来
运 筹 学 讲 义 4 由上述算法知，顶点○j 的标号 l( j) 恰是以顶点○j 为完工事项的工序 (i, j) 的最晚必须完工时间. 特别地， t(n) 是生产过程的完工期，即生产过程的最晚必须完工时间.于是， t (i, j) l( j) LF = ， t (i, j) t (i, j) w(i, j) l( j) w(i, j) LS = LF − = − . 例 1（续）求下面统筹图中的各工序的一个关键路线： 解：利用标号法，得 一般地，可将两个标号在同一个统筹图中标出来：
运筹学讲义 13.15 最早可能 开工时间 10,102.20 最晚必须 时间 5,5 14.14 3.工序的机动时间():最晚必须开工时间与最早必须开工时间之差,即 R(,j=ts(,J)-tEs(i,j) 工序的机动时间表示在不影响生产过程的总完工期的前提下,该工序的完工期可能推迟的最长时 间.显然,关键工序的机动时间为0(∵关键工序必须按期完工) 利用统筹方法计算出有关数据,有利于管理人员掌握全局,抓住关键,处理生产过程中出现的各 种问题,科学地组织整个生产过程
运 筹 学 讲 义 5 ▍ 3.工序的机动时间（）：最晚必须开工时间与最早必须开工时间之差，即 R(i, j) t (i, j) t (i, j) = LS − ES . 工序的机动时间表示在不影响生产过程的总完工期的前提下，该工序的完工期可能推迟的最长时 间.显然，关键工序的机动时间为 0（ 关键工序必须按期完工）. 利用统筹方法计算出有关数据，有利于管理人员掌握全局，抓住关键，处理生产过程中出现的各 种问题，科学地组织整个生产过程