运筹学讲义 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) 的最晚必须完工时间，从而得最晚必须完工时间