网络计划的优化资源优化.pptx

《网络计划的优化资源优化.pptx》由会员分享，可在线阅读，更多相关《网络计划的优化资源优化.pptx（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1网络计划的优化资源优化网络计划的优化资源优化第一节第一节第一节第一节 工期工期工期工期-资源优化资源优化资源优化资源优化内容：根据资源情况对网络计划进行调整，在规定工期和内容：根据资源情况对网络计划进行调整，在规定工期和资源供应之间寻求相互协调和相互适应。资源供应之间寻求相互协调和相互适应。(1)“(1)“资源有限，工期最短资源有限，工期最短”优化优化在资源供应有限制的条件下，寻求计划的最短工期在资源供应有限制的条件下，寻求计划的最短工期(2)“(2)“工期固定，资源均衡工期固定，资源均衡”优化优化在工期规定的条件下，力求资源消耗均衡。在工期规定的条件下，力求资源消耗均衡。优化前提：优

2、化前提：(1)(1)网络计划一经制定，在优化过程中不得改变各工序的持网络计划一经制定，在优化过程中不得改变各工序的持续时间；续时间；(2)(2)各工序每天的资源需要是均衡的，合理的，优化过程中各工序每天的资源需要是均衡的，合理的，优化过程中不予改变；不予改变；(3)(3)除规定可以中断的工序外，其它工序均应连续作业。除规定可以中断的工序外，其它工序均应连续作业。(4)(4)优化过程中不得改变网络计划各工序间的逻辑关系。优化过程中不得改变网络计划各工序间的逻辑关系。第1页/共49页时段与工序的关系：时段与工序的关系：网络计划的每日资源需要量曲线是资源优化的初始状态。网络计划的每日资源需要量曲线是

3、资源优化的初始状态。每日资源需要量曲线的每一变化都说明有工序在该时每日资源需要量曲线的每一变化都说明有工序在该时间点开始或结束。每日资源需要量不变且连续的一段间点开始或结束。每日资源需要量不变且连续的一段时间，称为时段，用时间，称为时段，用t ta a表示时段开始时间，表示时段开始时间，t tb b表示时表示时段完成时间，可用段完成时间，可用t ta a,t,tb b 表示这个时段。表示这个时段。第2页/共49页一、资源有限，工期最短优化一、资源有限，工期最短优化设某工程项目需要设某工程项目需要S S种不同的资源，已知每天可能供应的种不同的资源，已知每天可能供应的资源数量分别为资源数量分别为R

4、 R1 1(t)(t)、R R2 2(t)(t)、R Rs s(t)(t)，完成每一，完成每一个工序只需其中一种资源，设为第个工序只需其中一种资源，设为第K K种资源，单位时种资源，单位时间资源需要量间资源需要量(强度强度)以表示，并假定为常数，在资源以表示，并假定为常数，在资源供应满足的条件下，完成工序供应满足的条件下，完成工序i-ji-j持续时间为持续时间为t tij ij，对资源，对资源有限，工期最短优化，可按照极差原理确定其最优方有限，工期最短优化，可按照极差原理确定其最优方案，即网络计划资源动态曲线中任何资源时段案，即网络计划资源动态曲线中任何资源时段t ta a,t,tb b 内每

5、天的资源消耗量总和内每天的资源消耗量总和RkRk均应小于或等于该计划每均应小于或等于该计划每天的资源限定量天的资源限定量RtRt，即满足，即满足 RkRtRkRt第3页/共49页(一一)时差、资源分析法时差、资源分析法1 1、分析步骤、分析步骤(1)(1)根据网络的逻辑关系和各工序作业持续时间，绘出相应根据网络的逻辑关系和各工序作业持续时间，绘出相应于各工序最早开始的时标网络图及资源需要量动态图。于各工序最早开始的时标网络图及资源需要量动态图。(2)(2)逐个时段对资源总需要量进行检查，若不满足供应限量逐个时段对资源总需要量进行检查，若不满足供应限量的要求时，则就需要对计划进行调整。直到所有内

6、资源的要求时，则就需要对计划进行调整。直到所有内资源总需要量都满足供应限量的要求为止。总需要量都满足供应限量的要求为止。2 2、各时段内资源分析及工序计划调整的原则。、各时段内资源分析及工序计划调整的原则。(1)(1)第一时段，假定在时段第一时段，假定在时段t t0 0,t,t1 1 内，当资源总需要量不满内，当资源总需要量不满足限量要求时：足限量要求时：先对位于关键线路上的工序进行编号，其次对位于非关先对位于关键线路上的工序进行编号，其次对位于非关键线路上的工序按其总时差递增顺序进行编号，如总时键线路上的工序按其总时差递增顺序进行编号，如总时差相等，则按工序每天资源需要量递减的顺序编号。差相

7、等，则按工序每天资源需要量递减的顺序编号。把位于本时段内的工序，按编号由小到大顺序依次分配把位于本时段内的工序，按编号由小到大顺序依次分配每天所需资源，以不超过可能供应的数量为限，余下的每天所需资源，以不超过可能供应的数量为限，余下的工序分配不到资源就右移到工序分配不到资源就右移到t t1 1开始。开始。第4页/共49页(2)其它时段，假定已计算至K步，在时段t0,tk内的工序 每天资源需要量之和没有超过供应的限量时，则就继续计算第K+1步。先绘出前一步工序 右移后的新的时标网络图及资源需要量动态图；其次检查时段tk,tk+1内资源总需要量是否超过供应的限量，若超过就对tk,tk+1内的工序，

8、根据以下原则调整：对于各工序内部不允许中断时：先对tk之前开始而在tk之后结束的工序，根据新的总时差与其开始时间至tk+1的距离之差的递增顺序编号，对上述差值相等的工序，按其每天资源量递减的顺序编号。第5页/共49页例：某工程网络计划初始方案如下，资源限定时Rk=8(单位/天)，假设各工序的资源相互通用，每项工序开始后就不得中断，试进行资源有限、工期最短优化。1246735(3)(4)23(4)23(5)(3)3(4)(3)42(4)0 06 78 82 22 59 9解：(1)根据各项工序持续时间tij,计算节点时间参数TEi和TLi,如图5-1所示。第6页/共49页(2)(2)按节点最早时

9、间按节点最早时间TEiTEi绘制时标网络图，图中箭线数字为绘制时标网络图，图中箭线数字为该工序资源需要量，并该图下方绘出资源动态曲线。该工序资源需要量，并该图下方绘出资源动态曲线。施工进度计划(天)12345678935443434811674(3)从图5-2看出，第一个超过资源资源供应限额的资源高峰时段为2,5时段，需进行调整。第7页/共49页(4)(4)资源时段资源时段2,52,5调整。该时段内有调整。该时段内有2-42-4、2-52-5、3-63-6三道工三道工序。根据资源分配规则，将其排序，并分配资源，如序。根据资源分配规则，将其排序，并分配资源，如下表所示。下表所示。第8页/共49页

10、二、工期固定、资源均衡优化二、工期固定、资源均衡优化(一一)用用“使方差值最小使方差值最小”方法均衡资源方法均衡资源设设R(t)R(t)为时间为时间t t所需要的资源量，所需要的资源量，T T为规定工期，为规定工期，为资源为资源需要量的平均值，则方差需要量的平均值，则方差 为为第9页/共49页由于施工网络计划资源需要量曲线是阶梯形曲线，假定第i天资源量为Ri，则此时，要使得方差最小，即要使：最小第10页/共49页1 1、网络计划调整的条件、网络计划调整的条件为了使目标函数为了使目标函数 减少，可以利用网络中有时差的各项工减少，可以利用网络中有时差的各项工序进行计划的调整，调整应当满足以下条件。

11、序进行计划的调整，调整应当满足以下条件。(1)(1)为了不改变总工期，每项工序的调整只能在工序为了不改变总工期，每项工序的调整只能在工序活动许可的范围内进行。活动许可的范围内进行。(2)(2)调整的结果应使调整的结果应使 减小，资源计划较为均衡。减小，资源计划较为均衡。(3)(3)要求双代号网络图的编号自始至终由小到大顺序排列。要求双代号网络图的编号自始至终由小到大顺序排列。2 2、调整各项工序的顺序、调整各项工序的顺序资源均衡是在编制网络计划之后进行的。通过非关键线资源均衡是在编制网络计划之后进行的。通过非关键线路上的非关键工序，在时差范围内进行调整，必须按工路上的非关键工序，在时差范围内进

12、行调整，必须按工序的逻辑关系逆序进行。当同一时间有多个工序序的逻辑关系逆序进行。当同一时间有多个工序 拥有自拥有自由时差时，应按单位时间资源由大到小的顺序逐一进行。由时差时，应按单位时间资源由大到小的顺序逐一进行。第11页/共49页3、调整方法(一)(1)单一工序右移一个时间单位将计划中的某一工序向右移动一个时间单位，假设该工序原来最早开始时间为a，最早结束时间为b，资源需要量为Rij,若向右移一个时间单位，则：第a+1天资源需要量将减少为R(a+1)-Rij第b+1天资源需要量将增加为R(b+1)+Rij要使 缩小，则移动工序后必须：上式简化得当为平衡资源而调整工序时，若能满足不等式(5-2

13、)，则资源需要量趋向均衡，则可令该工序右移一个时间单位。(5-2)第12页/共49页(2)(2)单一工作右移几个时间单位单一工作右移几个时间单位在工序时差范围内逐一试算是否可一次右移一至多个时在工序时差范围内逐一试算是否可一次右移一至多个时间单位间单位 。如果以如果以T T1 1记录一次右移的时间，以记录一次右移的时间，以L L表示该工序能右移表示该工序能右移的最大时间，现已移动了的最大时间，现已移动了L L1 1个时间单位，则个时间单位，则T T1 1L-LL-L1 1若若T1=2T1=2，即一次右移二个时间单位：，即一次右移二个时间单位：则可由式则可由式(5-2)(5-2)推出下式：推出下

14、式：R(b+1)-R(a+1)+Rij+R(b+2)-R(b+1)-R(a+1)+Rij+R(b+2)-R(a+2)+Rij0 (5-3)R(a+2)+Rij0 (5-3)当一次右移当一次右移T1T1天时，式天时，式(5-3)(5-3)则为：则为：第13页/共49页例：某工程网络计划如图所示，时间单位为天。试确定工例：某工程网络计划如图所示，时间单位为天。试确定工期固定、资源均衡的方案。期固定、资源均衡的方案。解：解：(1)(1)计算计算TEiTEi、TLijTLij、TFijTFij、FFijFFij填入图中填入图中3145672606(4)5 00 02(1)4(2)3(3)1(2)6(1

15、)7(4)5(2)0 00 05 5660 06 122 74 43 810 1015 15第14页/共49页(2)(2)绘制绘制ES-EFES-EF时标网络图，计算出资源动态数列时标网络图，计算出资源动态数列123456789101112131415778109988852222213546271221432第15页/共49页第一次调整。第一次调整。节点节点7 7：以节点：以节点7 7为结束节点的工序有为结束节点的工序有2-72-7、5-75-7、6-76-7，6-76-7为关键工序，故只考虑为关键工序，故只考虑2-72-7和和5-75-7工序。工序。1)1)先考虑先考虑5-75-7：a=3

16、,b=10,TF=FF5,R=4a=3,b=10,TF=FF5,R=4R(10+1)-R(3+1)+RR(10+1)-R(3+1)+R5 5，7 7=2-10+4=-40=2-10+4=-40，可右移一天。若，可右移一天。若5-75-7工序再右移工序再右移1d1d，根据式，根据式5-25-2有：有：R(10+2)-R(3+2)+RR(10+2)-R(3+2)+R5 5，7 7=2-9+4=-30=2-9+4=-30，可以右移，可以右移1 1天，共天，共2 2天。天。R(10+3)-R(3+3)+RR(10+3)-R(3+3)+R5 5，7 7=2-9+4=-30=2-9+4=-30，可再右移，

17、可再右移1 1天，共天，共3 3天。天。R(10+4)-R(3+4)+RR(10+4)-R(3+4)+R5 5，7 7=-20=-20，可再右移，可再右移1 1天，共天，共4 4天。天。R(10+5)-R(3+5)+RR(10+5)-R(3+5)+R5 5，7 7=-20=-20,不能右移1天。R(9+1)-R(6+1)+R2，7+R(9+2)-R(6+2)+R2，7=4+6-4+3=90，不能右移2天，同理，2-7工序不能右移。节点5：以节点5为结束节点的工序只有3-5工序。a=2，b=3,TF=5,R=2.根据公式5-2：R(3+1)-R(2+1)+R3，5=6-8+2=0，可右移1 天。

18、R(3+2)-R(2+2)+R3，5=5-8+2=-10，可再右移1 天。第19页/共49页3-53-5工序共右移工序共右移5 5天。天。123456789101112131415776855448566666776675448566666135462712214324第20页/共49页3-53-5工序右移工序右移5 5天后的网络图。天后的网络图。123456789101112131415776655468566666135462712214324节点3：a=0,b=2,TF=5,据式5-2，1-3工序可右移5天。如下图第21页/共49页1234567891011121314156666565

19、68566666135462712214324第22页/共49页调整方法调整方法(二二)方法一的缺点：在运用判别式时，必须工序每移动一次，就要对网方法一的缺点：在运用判别式时，必须工序每移动一次，就要对网络计划的工序进行调整，重新计算资源量，作图和计算工作量大。络计划的工序进行调整，重新计算资源量，作图和计算工作量大。对下图中工序对下图中工序2-72-7分析分析第23页/共49页(1)(1)根据式根据式(5-2)(5-2)2-72-7可右移可右移1d1d，如圆点所示，如圆点所示,8,9,8,9两天资源量无变化，只考虑两天资源量无变化，只考虑7,107,10两天两天123456789101112

20、131415778109988852222213546271221432第24页/共49页123456789101112131415778109988852222213546271221432(2)2-7可再右移1d，如点划线所示，与圆点相比较，8,11两天资源量有变化。第25页/共49页(3)(3)工序可再右移工序可再右移1d1d，如虚线所示，与点划线比较，如虚线所示，与点划线比较，9,129,12两天资源量变化。两天资源量变化。123456789101112131415778109988852222213546271221432第26页/共49页(4)(4)注意：式中第注意：式中第1010

21、天与初始网络图中的第天与初始网络图中的第1010天的资源量天的资源量不一致。不一致。123456789101112131415778109988852222213546271221432第27页/共49页工序右移的判别公式：本次调整的累计右移时间为工序右移的判别公式：本次调整的累计右移时间为L L1 1，单一工序一次右移一个时间单位单一工序一次右移一个时间单位单一工序一次右移一个时间单位单一工序一次右移一个时间单位：当当L L1 1tijtij时，时，当当L L1 1tijtij时，时，若满足上两式，则可将该工序右移若满足上两式，则可将该工序右移1 1个时间单位。个时间单位。单一工序一次右移单

22、一工序一次右移T T1 1个时间单位个时间单位当当L L1 1tijtij时，时，当当L L1 1tijtij时，时，注：上述公式中的资源量均是该本次调整前的网络图中的注：上述公式中的资源量均是该本次调整前的网络图中的资源量。不必移动一次工序，就对资源量进行重新计资源量。不必移动一次工序，就对资源量进行重新计算。算。第28页/共49页例：以图例：以图5-115-11为例为例1234567891011121314157781099888522222135462712214324第29页/共49页第一次调整：第一次调整：节点节点：以：以为结束节点的非关键工序有为结束节点的非关键工序有2-72-7和

23、和5-75-7。(1)(1)先考虑先考虑5-75-7工序：工序：a=3,b=10,TF=FF=5,R=4,t=7a=3,b=10,TF=FF=5,R=4,t=7应用公式应用公式(5-5)(5-5)，以初始网络图为基础：，以初始网络图为基础：可右移可右移1d1d 可右移可右移1d1d，共，共2d2d 可右移可右移1d1d，共，共3d3d 可右移可右移1d1d，共，共4d 4d 可右移可右移1d1d，共，共4d4d 可右移可右移1d1d，共，共5d5d右移后的时标网络图及每资源需要量如下图右移后的时标网络图及每资源需要量如下图第30页/共49页123456789101112131415778655

24、448566666135462712214324第31页/共49页以上图为基础，考虑工序以上图为基础，考虑工序2-72-7：a=6,b=9,TF=FF=6,R=3,t=3a=6,b=9,TF=FF=6,R=3,t=3应用式应用式(5-5)(5-5)不能右移不能右移1d 1d 应用式应用式(5-7)(5-7)不能右移不能右移2 2天。天。应用式应用式(5-8)(5-8)不能右移不能右移4 4天，同理，可推导天，同理，可推导2-72-7不能移动不能移动第32页/共49页节点节点：只有非关键工序：只有非关键工序3-53-5，a=2,b=3,TF=5,R=2,t=1a=2,b=3,TF=5,R=2,t

25、=1 可右移可右移1 d 1 d 此时，此时，L L1 1=1=t=1,=1=t=1,以下计算以下计算L L1 1将大于将大于t,t,应用公式应用公式(5-6)(5-6)。可再右移可再右移1d1d，共，共2d2d 可推导可推导3-53-5可右移共可右移共5 5天。天。问题：直接应用公式问题：直接应用公式5-85-8推导推导3-53-5能否右移能否右移5 5天。天。调整后见下图。调整后见下图。第33页/共49页123456789101112131415776655468566666135462712214324第34页/共49页节点：非关键工序1-3，可推导，1-3可右移5天，第一次调整结束。第

26、二次调整，无工序可调整，过程结束。123456789101112131415666656568566666135462712214324第35页/共49页(二二)用用“使极差值为最小使极差值为最小”方法均衡资源方法均衡资源极差值为：极差值为：资源平均值为常数，因此欲使极差值最小，应使资源平均值为常数，因此欲使极差值最小，应使 最小，即使每天资源的最大用量为最低，最小，即使每天资源的最大用量为最低，常用常用“削高峰法削高峰法”。利用时差将高峰的某些工序后移以逐步降低峰值，每利用时差将高峰的某些工序后移以逐步降低峰值，每次削去高峰的一个资源计量单位，反复进行直到不次削去高峰的一个资源计量单位，反复

27、进行直到不能再削为止。能再削为止。第36页/共49页例：某工程网络计划如下图。例：某工程网络计划如下图。12346910578(4)4(1)3(3)2(2)4(3)3(4)5(2)3(5)5(4)5(3)3(2)3(2)2解：第一步：按最早开始时间绘制时标网络计划，计算每日资源需要量动态数列 第二步：确定资源数量上限(动态数列中的最大 值减去它的一个计量单位，本例中第37页/共49页在本例中，最大值是第在本例中，最大值是第5 5天的天的1111，则削峰目标为：，则削峰目标为：R=11-1=10R=11-1=10第三步：分析资源限值的高峰并调整。第三步：分析资源限值的高峰并调整。如时段内的资源量

28、超过限值用正式判断能否调整：如时段内的资源量超过限值用正式判断能否调整：1234567891011121314151617181920212212456798103(4)(1)(3)(2)(4)(2)(5)(3)(4)(2)(2)(3)第38页/共49页如时段内的资源量超过限值用正式判断能否调整：如时段内的资源量超过限值用正式判断能否调整：若不等式成立，则该可以向右移动至高峰值之后，即移若不等式成立，则该可以向右移动至高峰值之后，即移 个时间单位；不等不成立，则不能移动。个时间单位；不等不成立，则不能移动。当在需要调整的时段内不止一个工序可使不等成立时，就按时间差当在需要调整的时段内不止一个工

29、序可使不等成立时，就按时间差值的大小顺序移动。如时间差值相同，就使资源数量小的优先值的大小顺序移动。如时间差值相同，就使资源数量小的优先移动。移动。在本例中，第在本例中，第5 5天资源数量为天资源数量为1111，超过，超过R=10R=10的规定，这个时段内的规定，这个时段内2-52-5、2-42-4、3-63-6、3-103-10四个工序，分别计算它们的时间差值。四个工序，分别计算它们的时间差值。将将3-103-10向右移动向右移动2 2天。见下图天。见下图第39页/共49页123456789101112131415161718192021225557988668887744444555124

30、56798103(4)(1)(3)(2)(4)(2)(5)(3)(4)(2)(2)(3)经调整后，没有时段资源超过10，第一次调整结束。第二次调整：从上图，现资源数量最大 值为9，故资源数量上限为9-1=8，检查可知第5天资源数量超过了限量，此时段内有工序2-4、3-6、2-5、计算时间差值。调整3-6，将其向右移动2天。资源数量见下表。第40页/共49页第第6,76,7两资源数量超过两资源数量超过R=8R=8，此时段中有工序，此时段中有工序2-5.2-42-5.2-4、3-63-6、3-103-10计算时间差值：计算时间差值：如是选择如是选择3-103-10，但其资源数量为，但其资源数量为2

31、 2，移动后仍不能解决资源，移动后仍不能解决资源冲突，故移动冲突，故移动3-63-6，将其右移，将其右移2 2天。天。12345678910111213141516171819202122555461111668887744444555第41页/共49页第第8,98,9两天资源数量超过两天资源数量超过R=8R=8，此时段中有工序，此时段中有工序2-42-4、3-63-6、3-103-10，计算时间差值：，计算时间差值：123456789101112131415161718192021225554688998887744444555第42页/共49页得：得：将将3-103-10优先调整，向右移动

32、优先调整，向右移动 4 4天，见下表。天，见下表。第第1010至至1313天资源数量超过天资源数量超过R=8R=8，时段内有工序，时段内有工序5-75-7、4-64-6、3-103-10、6-96-9。将将3-103-10向后移动向后移动 4 4天，计算每日资源数量后，第天，计算每日资源数量后，第1414天仍天仍超过，将其再后移超过，将其再后移1 1天，满足天，满足R=8R=8，第二次调整完成。，第二次调整完成。画出时标网络图。画出时标网络图。123456789101112131415161718192021225554666771010109744444555第43页/共49页第二次调整后的

33、时标网络计划第二次调整后的时标网络计划12345678910111213141516171819202122555466677888776666455512456798103(4)(1)(3)(2)(4)(2)(5)(3)(4)(2)(2)(3)第44页/共49页第三次调整，资源数量上限定为第三次调整，资源数量上限定为R=8-1=7R=8-1=7第第1010天、第天、第1212天资源数量超过天资源数量超过R=7R=7，工序有，工序有4-64-6、5-75-7计算：计算：选择选择4-64-6调整，向右移动调整，向右移动3 3天，因工序天，因工序4-64-6没有自由时差，须没有自由时差，须与与6-

34、96-9一起移动。资源量见下表一起移动。资源量见下表12345678910111213141516171819202122555466677555101098864555第45页/共49页第第1313至至1717天超过天超过R=7R=7，有工序，有工序5-75-7、4-64-6、6-96-9、7-87-8、3-103-10，先考虑先考虑1313至至1414天的资源冲突，只有工序天的资源冲突，只有工序4-6,5-74-6,5-7，向后移动向后移动4-6 24-6 2天，工序也称移动天，工序也称移动2 2天。天。1234567891011121314151617181920212255546667

35、75557799986555第46页/共49页第第1515天至天至1818天资源数量还超过天资源数量还超过R=7R=7，有工序，有工序7-87-8、4-64-6、3-103-10，分别，分别计算后，将工序计算后，将工序3-103-10调整，向右移动调整，向右移动4 4天，计算资源数量。此天，计算资源数量。此时第时第1919天资源超过天资源超过R=7R=7，但所有工序已不能右移。，但所有工序已不能右移。12345678910111213141516171819202122555466677555557776877712456798103(4)(1)(3)(2)(4)(2)(5)(3)(4)(2)

36、(2)(3)第47页/共49页第四步：当所有工序不能右移时，应考虑将工序左移。工序第四步：当所有工序不能右移时，应考虑将工序左移。工序3-103-10最早最早开始时间在第开始时间在第3 3天，在第天，在第3 3天至第天至第1818天时间段中，第天时间段中，第1010至至1414天资源天资源数量为数量为5 5，可将该工序左移至第，可将该工序左移至第1010天以后开始，即可满足资源数天以后开始，即可满足资源数量上限要求。绘制时标网络图。量上限要求。绘制时标网络图。1234567891011121314151617181920212255546667757777777665552456798103(4)(1)(3)(2)(4)(2)(5)(3)(4)(2)(2)(3)1第48页/共49页