《网络计划技术》全套PPT电子课件教案-第5章优化.ppt

网络计划技术,中国石油大学建筑工程系,第五章 网络计划的优化,高福聚,博士 副教授,网络计划的优化,计算出网络计划的全部时间参数后，我们就得到了一个初始的网络计划，但是这种网络计划不一定是最优的；甚至可能是不可行的网络计划。比如，,时间方面，它可能超过了规定的工期； 资源方面，它可能在某些时段，资源的需求量超过了实际可能的资源供应量，而在另一些时段，资源的需求量又大大少于资源的供应量；或者尽管在所有时段，资源的需要量都低于实际可能的供应量，但是资源的实际需求量波动很大。也会给生产组织带来很大的不方便或者造成浪费。 成本方面，它可能不是一个总成本最低的网络计划，或者不是一个令人满意的费用水平的网络计划。,总之，初始的网络计划中可能存在着一些矛盾和不足。如何使初始的网络计划变成一个可行网络计划，或者变成一个理想的网络计划，这便是网络计划优化的任务。,所谓网络计划优化，就是在满足既定条件下，按一定的衡量指标寻求最优的网络计划的过程。 理想的衡量指标应综合工期、资源、成本等因素。但是目前还没有一个这样的综合的数学模型。对于具体的问题，只能确定优先原则，按照某一衡量指标来寻优。,时间优化,资源优化,成本优化,时间优化,时间优化的目的是使工期尽可能短，保证工程在规定的工期内完成或提前完成。 由于工期由关键线路决定，因此，如何压缩关键路线，是网络计划时间优化的核心内容。 关键线路是由关键工作（活动）组成的，从根本上说，缩短关键线路途径有二： 一、将关键活动进行分解，组织平行生产或平行交叉生产 1. 将串联活动改为并行活动 2. 将串联活动改为并行交叉活动 二、压缩关键活动的持续时间 1. 缩短关键活动的方法 2. 压缩活动的选择,将关键活动进行分解，组织平行生产或平行交叉生产,1. 将串联活动改为并行活动,洗菜,5,炒菜,淘米,蒸饭,15,2,20,t=42分,洗菜,5,炒菜,淘米,蒸饭,15,2,20,t=27分,洗菜,5,炒菜,淘米,蒸饭,15,2,20,t=22分,将串联活动改为并行活动的原则：,1. 仅仅出于对资源的考虑，将工艺上并无先后要求的活动安排成串联活动的改为并行活动；,2. 原来主观安排成串联活动的改为并行活动。,2. 将串联活动改为并行交叉活动,将串联的关键活动改为并行活动，虽然优化效果最大，但是由于工艺要求的限制，可以作这种改动的活动并不多见。然而将串联活动改为并行交叉活动的情形确是很普遍的。因此，组织平行交叉生产便成为时间优化的最有效的方法。,这种方法的特点是：不改变活动之间的逻辑关系，不缩短各活动总的持续时间，只是将串联进行的关键活动各自细分为几段，然后进行并行交叉作业。（分段流水施工）,加工构件a 9件,构件ab安装,加工构件b 12件,27,30,48,t=78,加工构件a 3件,9,加工构件a 3件,9,加工构件a 3件,9,加工构件b 4件,16,加工构件b 4件,16,加工构件b 4件,16,构件安装1,10,构件安装2,10,构件安装3,10,t=58,合并虚活动，整理网络图,加工构件a 3件,9,加工构件a 3件,9,加工构件a 3件,9,加工构件b 4件,16,加工构件b 4件,16,加工构件b 4件,16,构件安装1,10,构件安装2,10,构件安装3,10,t=58,压缩关键活动的持续时间,1. 缩短关键活动的方法,2. 压缩活动的选择,通常可以从下列几个方面采取措施来缩短关键活动的时间：,1）从资源上采取措施 （1）推迟非关键活动的开始时间，调出资源支援关键活动。 （2）延长非关键活动的持续时间，调出部分资源支援关键活动。 （3）从计划外抽调资源给关键活动，用以缩短关键活动的持续时间。,2）从组织上采取措施：承包责任制、加班等；,3）从技术上采取措施,1）公共活动（瓶颈活动）原则,2）潜力最大原则,3）费用率最小原则,3,a,b,c,d,e,f,g,h,i,j,k,7,4,5,8,4,6,4,3,6,6,2,资源优化,任何一个网络计划的完成，都离不开人力、物力、资金等资源。但对于一个具体的企业单位来说，它拥有资源总量总是有限的。,一、在资源有限的条件下，应当如何作计划才能使得工期最短；也就是有限资源下的工期优化问题，或有限资源的合理分配问题。,网络计划技术中资源优化所要解决的两类问题：,二、在工期一定的条件下，应当如何作计划才能使得所需的资源比较均衡；亦即规定工期下的资源均衡问题，或资源平衡问题。,这两类资源优化问题都可以用分析法或启发式方法求解。,1）分析法就是通过建立精确的数学模型来求解最优解的方法。但一个规模很小的网络计划，却可以构造成规模很大的数学模型，要花费很多的时间和精力才能求得答案，有时甚至根本不能求解；,2）启发式方法则是一种近似解法，其着眼点并不在于得到数学含义上的最优解，而是在一定范围内的满意解。这个满意解可能是最优解，也可能是近似最优解，而且经常是近似最优解。但是，启发式方法的求解工作量比分析法要少得多。,我们主要介绍启发式方法。,有限资源下的工期优化,解决有限资源下的工期优化问题启发式方法比较多，常见的有最小时差法（mintf法）（以最小总时差为准则的优化方法）、rsm法、负荷均衡法等，其中以最小时差法应用最为普遍。,当可能供应的资源量为一定值时，根据最小时差法可以推出两种更简便的方法： 1）以最小最迟开始时间ls为准则的优化法（minls法） 2）以最大最早开始时间ef为准则的优化法（maxef法）,我们主要介绍mintf法、 minls法和maxef法。,mintf,minls,maxef,最小时差法,最小时差法就是当某一时段的资源需要量超过了资源的供应量的时候，对在该时段内进行的活动，优先安排总时差最小的活动；若总时差相等时，资源需要量大者或持续时间小者优先。,最小时差法的具体步骤： 为了简便起见，假定所有活动需要同一种资源，资源的可供应量为lr=常数。,第一步：绘制各个活动在最早开始时间的时间坐标网络图，计算相应的资源需要总量，必要时把资源需要总量绘制成阶梯曲线；检查各个时段有无资源需求超过限量。,第二步：对超限时段tk，tk+1内的各个活动进行优先级编号（排队）。 编号（排队）原则，分两种情况： 1. 各个活动不允许中断， 1） 对tk之前已经开始的活动，根据tfi-j（ tk+1 esi-j）的递增顺序由小到大进行编号（排队）； 若此差值相等，则按照资源需求量由大到小进行编号（排队）；编号分别为1，2， ，m； 2）时段内其余活动，按照总时差由小到大进行编号（排队）；若总时差相等，则按照资源需求量由大到小进行编号（排队）；编号分别为m1， m 2， ；,活动新的总时差与开始到tk+1的距离之差,2. 某些活动允许中断 以tk时刻为界，将活动一分为二，对tk之后部分，按照不允许中断情形2）处理。,第三步：对时段tk，tk+1内的各个活动，按照优先顺序进行资源累加，直到资源需求量欲将超限，其余活动后移到tk+1开始。,第四步：继续检查和调整 tk+1之后各时段的资源超限情况，直至各时段均满足要求为止，,最小时差法也适用于解决多种资源的优化问题。,最早开始时间的时间坐标网络图,最小时差法流程图,计算相应的资源需要总量,无超限时段,某些活动允许中断,所有活动不允许中断,已经开始的活动,尚未开始的活动,以tk为界一分为二,1）tfi-j（ tk+1 esi-j）由小到大排队 2）按资源需求量由大到小进行排队,1）按总时差tf由小到大排队 2）按资源需求量由大到小进行排队,有超限时段,未开始部分,结束,各个活动排队,1,2,3,4,5,6,7,3,2,4,5,4,8,例，如图所示网络计划，箭线上方黄色方框内为各活动的资源需求量，本例假定各个活动不允许中断，最大资源量lr11。,2,2,4,3,4,6,4,5,3,4,4,4,5,5,3,2,1. 绘制各活动在最早开始时间的时间坐标网络图，计算出每天的资源需求总量rs,1,3,2,4,5,6,7,6,3,4,5,3,2,4,4,4,5,4,3,4,5,5,3,4,4,14,14,17,15,10,10,6,6,15,15,12,13,5,5,5,2,8,2,2,在时段0，2内进行的活动有三个，即12，13和14，它们的总时差和资源需求量如下表所示。,2. 在时段0，2内资源需求量rs超过了供应量lr，故需要进行调整。,1,2,3, r（13）+ r（12）63911=lr, 将活动14后移到时刻t=2开始,时间坐标网络图和资源变动见下页。,时间坐标网络图和资源变动1,1,3,2,4,5,6,7,6,3,4,5,3,2,4,4,4,5,4,3,4,5,5,3,4,4,9,9,17,15,15,15,6,6,15,15,12,13,5,5,5,8,2,2,2,在时段2，3内进行的活动有四个，即13，14，24和27，它们的总时差和资源需求量如下表所示。,3. 在时段2，3内资源需求量rs=17，超过了供应量lr=11，故需要进行调整。,1,2,3, r（13）+ r（14）6511lr r（13）+ r（14） + r（24） 6541511=lr, 将活动24和23后移到时刻t=3开始,时间坐标网络图和资源变动见下页。,4,活动13已经开始，首先安排，编为1号； 活动14和24的总时差相等，按照资源需求量由大到小优先排列，分别变为2号和3号； 活动27相应编为4号。,时间坐标网络图和资源变动2,1,3,2,4,5,6,7,6,3,4,5,3,2,4,4,4,5,4,3,4,5,5,3,4,4,9,9,11,15,15,15,10,6,15,15,14,13,5,5,5,8,2,2,2,在时段2，3内进行的活动有四个，即14，34，24和27，它们的总时差和资源需求量如下表所示。,4. 在时段3，6内资源需求量rs=15，超过了供应量lr=11，故需要进行调整。,1,2,3, r（14）+ r（34）54911=lr, 将活动24和27后移到时刻t=6开始。,时间坐标网络图和资源变动见下页。,4,活动14已经开始，首先安排，编为1号； 活动34总时差tf=0，编为2号； 活动24编为3号； 活动27相应编为4号。,又活动24的总时差tf=13,总工期因为活动24的后移，需要增加2天。,时间坐标网络图和资源变动3,1,3,2,4,5,6,7,6,3,4,5,3,2,4,4,4,5,4,3,4,5,5,3,4,4,9,9,11,9,9,9,10,6,6,15,15,14,5,5,5,8,2,2,2,10,15,在时段2，3内进行的活动有四个，即45，46，47和27，它们的总时差和资源需求量如下表所示。,5. 在时段11，12内资源需求量rs=15，超过了供应量lr=11，故需要进行调整。,1,2,3,时间坐标网络图和资源变动见下页。,4,活动27已经开始，首先安排，编为1号； 活动46总时差tf=0，编为2号； 活动47编为3号； 活动45相应编为4号。, r（27）+ r（46） + r（47） 24511lr r（27）+ r（46） + r（47）+ r（45）2454 1511=lr, 将活动45后移到时刻t=12开始。,时间坐标网络图和资源变动4,1,3,2,4,5,6,7,6,3,4,5,3,2,4,4,4,5,4,3,4,5,5,3,4,4,9,9,11,9,9,9,10,6,6,11,11,15,8,8,5,8,2,2,2,10,16,在时段13，13内进行的活动有四个，即45，46，47和27，它们的总时差和资源需求量如下表所示。,6. 在时段13，13内资源需求量rs=15，超过了供应量lr=11，故需要进行调整。,1,2,3,时间坐标网络图和资源变动见下页。,4,活动27、活动46和活动47均是已经开始的活动，优先安排； 只有将活动45再行后移，移到时刻t=13后开始。,时间坐标网络图和资源变动5,1,3,2,4,5,6,7,6,3,4,5,3,2,4,4,4,5,4,3,4,5,5,3,4,4,9,9,11,9,9,9,10,6,6,11,11,11,9,8,8,8,2,2,2,10,16,在时段14，14内进行的活动有四个，即27，45，47和67，它们的总时差和资源需求量如下表所示。,7. 在时段14，14内资源需求量rs=16，超过了供应量lr=11，故需要进行调整。,1,3,时间坐标网络图和资源变动见下页。,4,活动27、活动47均是已经开始的活动，优先安排； 将活动67编号为3；活动45编号为4。,2, r（27）+ r（47） + r（67）24511lr r（27）+ r（47） + r（67）+ r（45）2454 1511=lr, 将活动45后移到时刻t=14开始。,又活动45的总时差tf=0；,总工期因为活动24的后移，需要增加1天。,时间坐标网络图和资源变动6,1,3,2,4,5,6,7,6,3,4,5,3,2,4,4,4,5,4,3,4,5,5,3,4,4,9,9,11,9,9,9,10,6,6,11,11,11,9,8,8,8,2,2,2,10,12,9,时间坐标网络图（工期t=18天，比初始网络计划延长了3天，每天的资源需求量均低于供应量。,1,3,2,4,5,6,7,6,3,4,5,3,2,4,4,4,5,4,3,4,5,5,3,4,4,9,9,11,9,9,9,10,6,6,11,11,11,9,8,8,8,2,2,2,10,12,9,最小ls法,在最小时差法中，在时段tk，tk+1内进行的各活动可以分为两类：,已排活动：活动在tk之前已经开始，如果资源量有限，则可以肯定这些活动的资源需求量之和不会大于供应量，而且也必须优先安排它们进行；所以在研究时段tk，tk+1内的活动时，不必再多加考虑。,待排活动：这些活动在tk时刻开始，最小时差法对它们按照总时差由小到大的顺序排队。,tfi-j=lsi-jtk,对同一组待排活动来说，tk是相同的。,最小时差法对它们按照总时差由小到大的顺序排队，完全等价于按最迟开始时间ls进行排队。,使用最小时差法进行优化，当某活动需要后移时，若后移的时间小于或等于其总时差，则所有未排活动的最迟结束和最迟开始时间都没有变化；若后移的时间比其总时差t ，则所有未排活动的最迟结束和最迟开始时间都增大了t。,显然，这种变化并没有改变各个活动最迟开始时间ls的大小顺序。因此，按照后移的ls进行编号排队完全等价于按照后移前的ls进行编号排队。,这样，在整个调整过程中，活动的编号排队可以根据初始网络计划进行。,调整开始时，我们可不绘制各活动在最早开始时间的时间坐标网络图，而绘制最迟开始时间的时间坐标网络图。,最小ls法的步骤,第一步：绘制各个活动的在最迟开始时间的时间坐标网络图，计算各单位时间的资源需求总量。若在某个时段资源需求超限，则需要进行调整。,若在时段t，t1内，rs值不变，而rs(t1+1)rs(t1)，则令t=t1，将紧前活动都在t或t之前结束的未排活动作为新的未排活动，转第三步 。,第二步：假定用t表示待排活动最早可能开始的时刻，调整开始时t=0；用rs(t)表示已排活动在第t单位时间的资源需求量之和，调整开始时，rs(1)=0。将紧前活动数为0的活动作为第一组待排活动。,第三步： 对待排活动，按照最迟开始时间ls由小到大的顺序进行编号排队；若ls相等，则按照资源需求量由大到小的顺序排队。 按照排队顺序，以rs(t+1)为基数，进行资源需求量累加，直到其和要超过资源供应量为止。 将已经累加的活动安排在t开始，其他活动继续待排，并计算新的rs值。,第四步：如果全部活动都已经安排，则调整结束；否则继续调整。,注意：如果某活动的开始时间为t，持续时间是t， 其资源需求量计入从（t+1）(t+t),如果某些活动允许中断，则以t为界，一分为二，作为两个活动处理。,最小ls法也适用于解决多种资源的优化问题。,1,2,3,4,5,6,7,3,2,4,5,4,8,例，如图所示网络计划，箭线上方黄色方框内为各活动的资源需求量，本例假定各个活动不允许中断，最大资源量lr11。,2,2,4,3,4,6,4,5,3,4,4,4,5,5,3,2,1. 绘制各活动在最迟开始时间的时间坐标网络图，计算出每天的资源需求总量rs,1,3,2,4,5,6,7,6,3,4,5,3,2,4,4,4,5,4,3,4,5,5,3,4,4,6,6,9,7,13,13,13,15,6,6,6,16,16,15,15,2,8,2,2,第一组待排活动有三个，即12，13和14，它们的最迟开始时间和资源需求量如下表所示。,2. 令t=0。是内资源需求量rs超过了供应量lr，故需要进行调整。,1,2,3, r（13）+ r（12）63911=lr, 将活动13 、12安排在t=0开始，已排活动的资源需求量见下表,rs（1） rs（2）9 rs（3）6 rs（2） 故令t=2,时间坐标网络图和资源变动见下页。,时间坐标网络图和资源变动一,1,3,2,4,5,6,7,6,3,4,5,3,2,4,4,4,5,4,3,4,5,5,3,4,4,9,9,6,0,2,8,2,2,活动12和13安排之后，节点2和3之前的活动都已经安排。在t=2，活动12刚好结束，活动13尚未结束，所以以节点2为开始节点的活动都成为待排。这样，第二组待排活动是：14、24和27。,3. t=2。,1,2,3, r（3）+ r（14）6511lr r（3）+ r（14） + r（24） 6541511=lr, 将活动14 安排在t=2开始，已排活动的资源需求量见下表,rs（3） 11，rs（4）5 rs（3） rs（4） 故令t=3,时间坐标网络图和资源变动见下页。,时间坐标网络图和资源变动二,1,3,2,4,5,6,7,6,3,4,5,3,2,4,4,4,5,4,3,4,5,5,3,4,4,11,5,5,5,0,2,8,2,2,活动13刚好结束，所以以节点3为开始节点的活动都成为待排。这样，第三组待排活动是：24、27和34。,4. t=3。,1,2,3, r（4）+ r（34）911=lr, 将活动34 安排在t=3开始，已排活动的资源需求量见下表,rs（4） rs（5） rs（6）9 rs（7）=4 故令t=6,时间坐标网络图和资源变动见下页。,时间坐标网络图和资源变动三,1,3,2,4,5,6,7,6,3,4,5,3,2,4,4,4,5,4,3,4,5,5,3,4,4,9,9,9,4,4,0,2,8,2,2,由于该活动推迟超过了它的总时差天，势必延长工期。,时间坐标网络图和资源变动（整理）,1,3,2,4,5,6,7,6,3,4,5,3,2,4,4,4,5,4,3,4,5,5,3,4,4,2,8,2,2,活动14刚好结束。34已经安排进行，第四组待排活动是： 24和27 。,4. t=6。,1, r（7）+ r（24）448 11lr r（7）+ r（24）+ r（24）44+210 11lr, 将活动24和27 安排在t=6开始，已排活动的资源需求量见下表,rs（7） rs（8）10 rs（9） rs（10）=6 故令t=8,时间坐标网络图和资源变动见下页。,2,又 t=8时，活动34完成， 24和27正进行，活动节点4没有实现，所以没有待派活动。, rs（9） rs（10）6 rs（11）2 故令t=10,时间坐标网络图和资源变动四,1,3,2,4,5,6,7,6,3,4,5,3,2,4,4,4,5,4,3,4,5,5,3,4,4,2,8,2,2,10,10,6,6,2,2,2,2,0,活动24刚好结束，27已经安排进行。节电4实现。第五组待排活动是： 45、 46和47 。,5. t=10。,1, r（10）+ r（46）+ r（47）24511lr r（10）+ r（46）+ r（47）+ r（45）2+45+415 11lr, 将活动46和47 安排在t=10开始，已排活动的资源需求量见下表,rs（11） rs（12） rs（13）11 rs（14）7 故令t=13,时间坐标网络图和资源变动见下页。,2,3,时间坐标网络图和资源变动五,1,3,2,4,5,6,7,6,3,4,5,3,2,4,4,4,5,4,3,4,5,5,3,4,4,2,8,2,2,11,11,11,7,0,活动46刚好结束，27和47已经安排进行。第六组待排活动是： 45和6 7 。,6. t=13。,1, r（14）+ r（67）751211lr 但是 r（14）+ r（45）7411lr, 将活动45安排在t=13开始，或者两者都向后推延（这样不好）,rs（14）11 rs（15）4 故令t=14,时间坐标网络图和资源变动见下页。,2,若将活动45安排在t=13开始已排活动的资源需求量见下表,时间坐标网络图和资源变动六（活动45安排）,1,3,2,4,5,6,7,6,3,4,5,3,2,4,4,4,5,4,3,4,5,5,3,4,4,2,8,2,2,11,由于该活动推迟超过了它的总时差1天，势必延长工期。,4,0,时间坐标网络图和资源变动六（两者都向后推延）,1,3,2,4,5,6,7,6,3,4,5,3,2,4,4,4,5,4,3,4,5,5,3,4,4,2,8,2,2,11,由于该活动推迟超过了它的总时差1天，势必延长工期。,4,0,由于该活动推迟超过了它的总时差1天，势必延长工期。,时间坐标网络图和资源变动六（整理）（活动45安排）,1,3,2,4,5,6,7,6,3,4,5,3,2,4,4,4,5,4,3,4,5,5,3,4,4,2,8,2,2,11,4,0,时间坐标网络图和资源变动六（整理）（两者都向后推延）,1,3,2,4,5,6,7,6,3,4,5,3,2,4,4,4,5,4,3,4,5,5,3,4,4,2,8,2,2,7,0,0,27和47已经结束。活动45已经安排，此时正进行，第七组待排活动是6 7 。,7. t=14。, r（15）+ r（67）45911lr, 将活动67安排在t=14开始,rs（15）9 rs（16）5 故令t=15,时间坐标网络图和资源变动见下页。,第七组待排活动,1,时间坐标网络图和资源变动七（活动45安排）,1,3,2,4,5,6,7,6,3,4,5,3,2,4,4,4,5,4,3,4,5,5,3,4,4,2,8,2,2,11,9,5,5,5,27和47已经结束。活动45没有安排，第七组待排活动是45和6 7 。,r（15）+ r（67）+ r（45）054911lr, r（15）+ r（67） 05511lr, 将活动45和67都安排在t=14开始,1,2,rs（15） rs（16 ）=9 rs（17）5 故令t=16,时间坐标网络图和资源变动七（两者都向后推延）,1,3,2,4,5,6,7,6,3,4,5,3,2,4,4,4,5,4,3,4,5,5,3,4,4,2,8,2,2,7,9,9,5,5,45和67已经安排进行，第七组待排活动是57 。,8. t=15（活动45已经安排）, r（16）+ r（57）53811lr, 将活动57安排在t=15开始,rs（16） rs（17） 8 rs（18）5 故令t=17,时间坐标网络图和资源变动见下页。,rs（18）5 11lr,当t=17时，所有活动安排完毕,结束,时间坐标网络图和资源变动八（活动45安排）,1,3,2,4,5,6,7,6,3,4,5,3,2,4,4,4,5,4,3,4,5,5,3,4,4,2,8,2,2,8,8,t=16 （两者都向后推延）, r（17）+ r（57） 53811lr, 将活动45和67都安排在t=14开始,rs（17） rs（18 ）=8 11lr,。,活动45结束， 67已经安排进行，第八组待排活动是57,1,所有活动安排完毕,结束,时间坐标网络图和资源变动见下页。,时间坐标网络图和资源变动八（两者都向后推延）,1,3,2,4,5,6,7,6,3,4,5,3,2,4,4,4,5,4,3,4,5,5,3,4,4,2,8,2,2,8,8,最小时差法与最小ls法比较,最大ef法,最大ef法是从网络的终节点，由右向左进行优化的一种方法。,最大ef法的具体步骤：,第一步：绘制各个活动在最早开始时间的时间坐标网络图，计算相应的资源需要总量，必要时把资源需要总量绘制成阶梯曲线；检查各个时段有无资源需求超过限量。,第二步：假定用t表示待排活动最早结束的时刻，调整开始时，令t为一个充分大的数。比如令t为初始网络计划计算工期的2倍，总之，要比可能实际工期大。 用rs(t)表示已排活动在时刻t需求量之和，即资源需要总量。 调整开始时，令rs(t)=0，将紧后活动活动数为零的活动作为第一组待排活动。,如果 某些活动允许中断 以tk时刻为界，将活动一分为二，对tk之前作为一个独立的活动处理。,第四步：如果全部活动都已经安排完毕，则调整过程结束；否则要继续进行调整。 若在时段t+1，t内，rs不变，而rs(t) rs(t)，则令t=t，将紧后活动数都在t或t后开始未排的活动，作为新的待排活动，转第三步。,最大ef法也适用于解决多种资源的优化问题。,第三步：对待排活动，按照ef由大到小的顺序排队；若es相等，则按资源需要量由大到小排队。 按照排队顺序，以rs(t)为基数进行资源需要量累加，直到其和将要超过资源供应量lr为止。将资源需要量已累加的活动安排在第t单位时间结束，其余活动继续作为待排活动，重新计算rs值。,1,2,3,4,5,6,7,8,6,3,例，如图所示网络计划，箭线上方黄色方框内为各活动的资源需求量，本例假定各个活动不允许中断，最大资源量lr13。,7,6,2,5,5,6,5,8,6,4,3,2,3,3,3,3,1,2,4,4,6,2,1. 绘制各活动在最早开始时间的时间坐标网络图，计算出每天的资源需求总量rs,1,2,6,4,7,8,7,2,6,3,5,3,5,4,3,2,6,8,4,4,2,13,13,17,11,11,15,15,15,22,17,17,8,4,4,3,6,2,3,5,3,6,3,5,6,1,第一组待排活动有三个，即58，68和78，它们的ef和资源需求量如下表所示。,2. 令t=20。rs(20)=0,1,2,3, r（58）+ r（68）+ r（78）4 6 313lr, 将活动58、68和7 8这三个活动都安排在t=20结束，已排活动的资源需求量见下表,rs（20） rs（19）13 rs（18）3 故令t=18,时间坐标网络图和资源变动见下页。,时间坐标网络图（0），,1,2,6,4,7,8,7,2,6,3,5,3,5,4,3,2,6,8,4,4,2,3,6,2,3,5,3,6,3,5,6,1,时间坐标网络图变动（1），,1,2,6,4,7,8,7,2,6,3,5,3,5,4,3,2,6,8,4,4,2,3,6,2,3,5,3,6,3,5,6,1,13,13,3,3,3,3,0,0,由于活动58和78的开始时刻都为18，且以节点5为开始节点的活动只有58，以节点7为开始节点的活动只有78，所以以节点5和7为结束节点的活动都成为新的待排活动。 这样，第二组待排活动为：35、45、47和67，它们的ef和资源需求量如下表所示。,3. 令t=18。rs(18)=3,1,2,3, r（18）+r（47）11 13 lr, 将活动47安排在t=18结束，已排活动的资源需求量见下表,rs（18）rs（17）rs（16）rs（15）11 rs（14）0 故令t=14,时间坐标网络图和资源变动见下页。,4,时间坐标网络图变动（2），,1,2,6,4,7,8,7,2,6,3,5,3,5,4,3,2,6,8,4,4,2,3,6,2,3,5,3,6,3,5,6,1,11,11,11,11,0,0,活动47和68的开始时刻都为14=t。但是，节点4为结束节点的活动34成为待排活动。 这样，第三组待排活动为：35、45和67，它们的ef和资源需求量如下表所示。,4. 令t=14。rs(14)=0,1,2,3, r（14）+r（45）+r（67）+r（35） 6+5+2= 13 lr, 将活动45、 67和35安排在t=14结束，已排活动的资源需求量见下表,rs（14）13 rs（13）7 故令t=13,时间坐标网络图和资源变动见下页。,时间坐标网络图变动（3），,1,2,6,4,7,8,7,2,6,3,5,3,5,4,3,2,6,8,4,4,2,3,6,2,3,5,3,6,3,5,6,1,13,7,7,5,0,活动67和35已经安排进行。节点4实现，以节点3为结束节点的活动成为待排活动。 这样，第四组待排活动为：34，它们的ef和资源需求量如下表所示。,5. 令t=13。rs(13)=7,1, r（13）+r（34）7+5= 1213 lr, 将活动34安排在t=13结束，已排活动的资源需求量见下表,rs（13） rs（12） 13 rs（11）10 故令t=11,时间坐标网络图和资源变动见下页。,时间坐标网络图变动（4），,1,2,6,4,7,8,7,2,6,3,5,3,5,4,3,2,6,8,4,4,2,3,6,2,3,5,3,6,3,5,6,1,12,12,10,0,活动35完成，67和34正在进行。节点3没有实现，以节点3为结束节点的活动不能成为待排活动。 这样，当t=11时没有待排活动。,6. 令t=11。rs(10)=10, r（10）+r（23）+ r（26） 0+6+5= 1113 lr, 将活动23和26安排在t=10结束，已排活动的资源需求量见下表,rs（10） rs（9） rs（8） 11 rs（7）0 故令t=7,时间坐标网络图和资源变动见下页。,1,2,3,当t=10时，rs(10)=0，活动67和34刚刚开始。节点3和6实现，以节点4和6为结束节点的活动都成为待排活动。 这样，第五组待排活动为：13、23和26，它们的ef和资源需求量如下表所示。,时间坐标网络图变动（5）,1,2,6,4,7,8,7,2,6,3,5,3,5,4,3,2,6,8,4,4,2,3,6,2,3,5,3,6,3,5,6,1,11,11,11,0,活动23，26刚刚开始。节点2实现，以节点2为结束节点的活动成为待排活动。,7. 令t=7。rs(7)=0, r（7）+r（12）+ r（13） 0+7+6= 13 lr, 将活动13和12安排在t=7结束，已排活动的资源需求量见下表,rs（7） rs（6） rs（5）13 rs（4）0,时间坐标网络图和资源变动见下页。,1,2,这样，第六组待排活动为：12、13，它们的ef和资源需求量如下表所示。,全部活动均已安排，调整结束。,结束,时间坐标网络图变动（6）,2,6,4,7,8,7,2,6,3,5,3,5,4,3,2,6,8,4,4,2,3,6,2,3,5,3,6,3,5,6,1,13,1,13,6,0,时标修正,2,6,4,7,8,7,2,6,3,5,3,5,4,3,2,6,8,4,4,2,3,6,2,3,5,3,6,3,5,6,1,1,由以上计算结果可见，整个工程将在第4天开始，在第20天结束，这样工期t=16天。 为了与其算法的结果一致，可将每个活动的开始时间和结束时间都提前4天，使得工程的开始时间为0。,最小时差法与最小ls法、最大ef法比较,在实际工作中，有些活动所需的资源不是一种，而是多种。,多种资源有限时的工期优化,当多种资源有限时，如何制定网络计划，使得工期最短呢？,多种资源有限时的工期优化问题,理论和实践证明，多种资源有限时的工期优化问题仍可采用前述最小时差法（最小ls法和最大ef法）,使用最小时差法求解多种资源有限的优化问题时应当注意：,1）对待排活动进行排队时，总时差（由小到大）， 2）当总时差相等时，可按关键资源由大到小的顺序进行排队，或者按活动持续时间由小到大顺序排队。,关键资源资源需求量较大，而供应量较小的资源,使用最小ls法或最大ef法进行优化时，同样要选择关键资源，当ls或ef值相等时，按照关键资源需求由大到小的顺序进行排队，或者按活动持续时间由小到大顺序排队。,下面举例说明如何使用最小ls法求解多种资源有限的优化问题,1,2,3,4,5,7,6,8,例：如图所示，时间单位为天，活动最多使用3种资源，3种资源的供应量分别为lr14， lr23和lr34。,3,2,2,3,3,2,4,2,3,4,3,1,1,0,2,2,2,0,2,0,3,1,3,2,1,1,2,0,0,0,0,2,1,1,1,2,2,1,3,2,3,0,1,0,我们用r(m,n)表示第m个活动对第n种资源的需求量。活动序号及活动对资源的需求量如下表所示。,本例所用的排队原则：按ls值由小到大的顺序进行排队；若ls值相等，按照关键资源由大到小的顺序进行排队。,本例选择第一种资源为关键资源。,1. 绘制各活动在最迟时间开始的时间坐标网络图，计算每天的资源需要总量。检查发现，3种资源都有超过供应量的情形，故需要进行优化。,1,2,5,3,4,6,8,1,1,0,3,0,0,2,4,0,2,0,2,2,1,1,3,2,2,2,2,3,0,1,0,3,4,2,7,2,1,1,1,3,1,3,3,2,0,0,2,2,1,3,2,3,第一组待排活动有两个：12和14，它们的排队情况如下表所示。,2. t=0。rs(1,n)=0 (n=1,2,3),1,2,r（1，1）+ r（2，1）3lr1=4； r（1，2）+ r（2，2）3=lr2=3； r（1，3）+ r（2，3）2lr3=4, 将活动1和2都安排在t=0开始，已排活动的资源需求量见下图和下表,rs（1,n） rs（2,n） rs（3,n） （n=1,2,3） 故令t=2,时间坐标网络图和资源变动见下页。,2,1,1,0,3,2,2,2,1,2,4,时间坐标网络图变动（一）,1,2,5,3,4,6,8,1,1,0,3,0,0,2,4,0,2,0,2,2,1,1,3,2,2,2,2,3,0,1,0,3,4,2,7,2,1,1,1,3,1,3,3,2,0,0,2,2,1,3,2,3,第二组待排活动有：47，它们的排队情况如下表所示。,3. t=2。,1,rs（3，1）+ r（7，1）4=lr1=4； rs（3，2）+ r（7，2）2lr2=3； rs（3，3）+ r（7，3）3lr3=4, 将活动7（即47）和2都安排在t=2开始，已排活动的资源需求量见下图和下表,rs（3,n） rs（4,n） （n=1,2,3） 故令t=3,时间坐标网络图和资源变动见下页。,2,1,1,0,3,2,2,2,1,2,4,7,3,1,3,3,时间坐标网络图变动（二）,1,2,5,3,4,6,8,1,1,0,3,0,0,2,4,0,2,0,2,2,1,1,3,2,2,2,2,3,0,1,0,3,4,2,7,2,1,1,1,3,1,3,3,2,0,0,2,2,1,3,2,3,第三组待排活动有：23和25，它们的排队情况如下表所示。,4. t=3。,1,rs（4，1）+ r（3，1）3lr1=4, 将活动3（即23）安排在t=3开始，已排活动的资源需求量见下图和下表,rs（4,n）= rs（5,n） rs（6,n） （n=1,2,3） 故令t=5,时间坐标网络图和资源变动见下页。,2,1,1,0,3,2,2,2,1,2,4,7,3,1,3,3,2,3,0,2,0,2,时间坐标网络图变动（三）,1,2,5,3,4,6,8,1,1,0,3,0,0,2,4,0,2,0,2,2,1,1,3,2,2,2,2,3,0,1,0,3,4,2,7,2,1,1,1,3,1,3,3,2,0,0,2,2,1,3,2,3,由于该活动后移，总工期将延长1天,第四组待排活动有：25和36、 37，它们的排队情况如下表所示。,5. t=5。,1,rs（6，1）+ r（4，1）0+2=2lr1=4； rs（6，2）+ r（4，2）0+1=1lr2=3； rs（6，3）+ r（4，3）0+1=1lr3=4 rs（6，1）+ r（4，1） + r（5，1） 2lr1=4 rs（6，2）+ r（4，2） + r（5，2） 1lr2=3 rs（6，3）+ r（4，3） + r（5，3） 3lr2=4 rs（6，1）+ r（4，1） + r（5，1）+ r（6，1）4=lr1=4 rs（6，2）+ r（4，2） + r（5，2）+ r（6，2）1lr2=3 rs（6，3）+ r（4，3） + r（5，3）+ r（6，3）3lr2=4, 将活动4（即23）、5（即36）和6（即37） 2安排在t=5开始，已排活动的资源需求量见下图和下表,rs（6,n）= rs（7,n） rs（8,n） （n=1,2,3） 故令t=7,时间坐标网络图和资源变动见下页。,2,3,时间坐标网络图变动（四）,1,2,5,3,4,6,8,1,1,0,3,0,0,2,4,0,2,0,2,2,1,1,3,2,2,2,2,3,0,1,0,3,4,2,7,2,1,1,1,3,1,3,3,2,0,0,2,2,1,3,2,3,活动37已经完成，活动25和36正在进行。第五组待排活动有：78，情况如下表所示。,6. t=7。,1,rs（8，1）+ r（11，1）2+2=4=lr1=4； rs（8，2）+ r（11，2）1+2=3=lr2=3； rs（8，3）+ r（11，3）3+1=4=lr3=4, 将活动11（即78）安排在t=7开始，已排活动的资源需求量见下图和下表,rs（8,n） rs（9,n） （n=1,2,3） 故令t=8,时间坐标网络图和资源变动见下页。,时间坐标网络图变动（五）,1,2,5,3,4,6,8,1,1,0,