网络计划的优化3：资源优化.ppt

网络计划优化,资源优化专题,第一节 工期-资源优化,内容：根据资源情况对网络计划进行调整，在规定工期和资源供应之间寻求相互协调和相互适应。(1)“资源有限，工期最短”优化在资源供应有限制的条件下，寻求计划的最短工期(2)“工期固定，资源均衡”优化在工期规定的条件下，力求资源消耗均衡。优化前提：(1)网络计划一经制定，在优化过程中不得改变各工序的持续时间；(2)各工序每天的资源需要是均衡的，合理的，优化过程中不予改变；(3)除规定可以中断的工序外，其它工序均应连续作业。(4)优化过程中不得改变网络计划各工序间的逻辑关系。,时段与工序的关系：网络计划的每日资源需要量曲线是资源优化的初始状态。每日资源需要量曲线的每一变化都说明有工序在该时间点开始或结束。每日资源需要量不变且连续的一段时间，称为时段，用ta表示时段开始时间，tb表示时段完成时间，可用ta,tb表示这个时段。,一、资源有限，工期最短优化设某工程项目需要S种不同的资源，已知每天可能供应的资源数量分别为R1(t)、R2(t)、Rs(t)，完成每一个工序只需其中一种资源，设为第K种资源，单位时间资源需要量(强度)以表示，并假定为常数，在资源供应满足的条件下，完成工序i-j持续时间为tij，对资源有限，工期最短优化，可按照极差原理确定其最优方案，即网络计划资源动态曲线中任何资源时段ta,tb内每天的资源消耗量总和Rk均应小于或等于该计划每天的资源限定量Rt，即满足 RkRt,(一)时差、资源分析法1、分析步骤(1)根据网络的逻辑关系和各工序作业持续时间，绘出相应于各工序最早开始的时标网络图及资源需要量动态图。(2)逐个时段对资源总需要量进行检查，若不满足供应限量的要求时，则就需要对计划进行调整。直到所有内资源总需要量都满足供应限量的要求为止。2、各时段内资源分析及工序计划调整的原则。(1)第一时段，假定在时段t0,t1内，当资源总需要量不满足限量要求时：先对位于关键线路上的工序进行编号，其次对位于非关键线路上的工序按其总时差递增顺序进行编号，如总时差相等，则按工序每天资源需要量递减的顺序编号。把位于本时段内的工序，按编号由小到大顺序依次分配每天所需资源，以不超过可能供应的数量为限，余下的工序分配不到资源就右移到t1开始。,(2)其它时段，假定已计算至K步，在时段t0,tk内的工序 每天资源需要量之和没有超过供应的限量时，则就继续计算第K+1步。先绘出前一步工序 右移后的新的时标网络图及资源需要量动态图；其次检查时段tk,tk+1内资源总需要量是否超过供应的限量，若超过就对tk,tk+1内的工序，根据以下原则调整：对于各工序内部不允许中断时：先对tk之前开始而在tk之后结束的工序，根据新的总时差与其开始时间至tk+1的距离之差的递增顺序编号，对上述差值相等的工序，按其每天资源量递减的顺序编号。,例：某工程网络计划初始方案如下，资源限定时Rk=8(单位/天)，假设各工序的资源相互通用，每项工序开始后就不得中断，试进行资源有限、工期最短优化。,1,2,4,6,7,3,5,(3),(4),2,3,(4),2,3,(5),(3),3,(4),(3),4,2,(4),0,0,6,7,8,8,2,2,2,5,9,9,解：(1)根据各项工序持续时间tij,计算节点时间参数TEi和TLi,如图5-1所示。,(2)按节点最早时间TEi绘制时标网络图，图中箭线数字为该工序资源需要量，并该图下方绘出资源动态曲线。,3,5,4,4,3,4,3,4,8,11,6,7,4,(3)从图5-2看出，第一个超过资源资源供应限额的资源高峰时段为2,5时段，需进行调整。,(4)资源时段2,5调整。该时段内有2-4、2-5、3-6三道工序。根据资源分配规则，将其排序，并分配资源，如下表所示。,二、工期固定、资源均衡优化(一)用“使方差值最小”方法均衡资源设R(t)为时间t所需要的资源量，T为规定工期，为资源需要量的平均值，则方差 为,由于施工网络计划资源需要量曲线是阶梯形曲线，假定第i天资源量为Ri，则,此时，要使得方差最小，即要使：,最小,1、网络计划调整的条件为了使目标函数 减少，可以利用网络中有时差的各项工序进行计划的调整，调整应当满足以下条件。(1)为了不改变总工期，每项工序的调整只能在工序活动许可的范围内进行。(2)调整的结果应使 减小，资源计划较为均衡。(3)要求双代号网络图的编号自始至终由小到大顺序排列。2、调整各项工序的顺序资源均衡是在编制网络计划之后进行的。通过非关键线路上的非关键工序，在时差范围内进行调整，必须按工序的逻辑关系逆序进行。当同一时间有多个工序 拥有自由时差时，应按单位时间资源由大到小的顺序逐一进行。,3、调整方法(一)(1)单一工序右移一个时间单位将计划中的某一工序向右移动一个时间单位，假设该工序原来最早开始时间为a，最早结束时间为b，资源需要量为Rij,若向右移一个时间单位，则：第a+1天资源需要量将减少为R(a+1)-Rij第b+1天资源需要量将增加为R(b+1)+Rij要使 缩小，则移动工序后必须：,上式简化得当为平衡资源而调整工序时，若能满足不等式(5-2)，则资源需要量趋向均衡，则可令该工序右移一个时间单位。,(5-2),(2)单一工作右移几个时间单位在工序时差范围内逐一试算是否可一次右移一至多个时间单位。如果以T1记录一次右移的时间，以L表示该工序能右移的最大时间，现已移动了L1个时间单位，则T1L-L1若T1=2，即一次右移二个时间单位：则可由式(5-2)推出下式：R(b+1)-R(a+1)+Rij+R(b+2)-R(a+2)+Rij0(5-3)当一次右移T1天时，式(5-3)则为：,例：某工程网络计划如图所示，时间单位为天。试确定工期固定、资源均衡的方案。解：(1)计算TEi、TLij、TFij、FFij填入图中,3,1,4,5,6,7,2,6,0,6,(4),5,0,0,0,2,(1),4,(2),3,(3),1,(2),6,(1),7,(4),5,(2),0,0,0,0,5,5,6,6,0,0,6,12,2,7,4,4,3,8,10,10,15,15,(2)绘制ES-EF时标网络图，计算出资源动态数列,1,3,5,4,6,2,7,1,2,2,1,4,3,2,第一次调整。节点7：以节点7为结束节点的工序有2-7、5-7、6-7，6-7为关键工序，故只考虑2-7和5-7工序。1)先考虑5-7：a=3,b=10,TF=FF5,R=4R(10+1)-R(3+1)+R5，7=2-10+4=-40，可右移一天。若5-7工序再右移1d，根据式5-2有：R(10+2)-R(3+2)+R5，7=2-9+4=-30，可以右移1天，共2天。R(10+3)-R(3+3)+R5，7=2-9+4=-30，可再右移1天，共3天。R(10+4)-R(3+4)+R5，7=-20，可再右移1天，共4天。R(10+5)-R(3+5)+R5，7=-20，可再右移1天，共5天。总时差已用完，故工序5-7不能再右移。,若5-7工序再右移1d，,1,3,5,4,6,2,7,1,2,2,1,4,3,2,4,工序5-7右移5天后的网络图和资源动态数列,1,3,5,4,6,2,7,1,2,2,1,4,3,2,4,2)再考虑工序2-7：a=6,b=9,TF=FF=6,R=3R(9+1)-R(6+1)+R2,7=5-4+3=40,不能右移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 天。R(3+2)-R(2+2)+R3，5=5-8+2=-10，可再右移1 天。,3-5工序共右移5天。,1,3,5,4,6,2,7,1,2,2,1,4,3,2,4,3-5工序右移5天后的网络图。,1,3,5,4,6,2,7,1,2,2,1,4,3,2,4,节点3：a=0,b=2,TF=5,据式5-2，1-3工序可右移5天。如下图,1,3,5,4,6,2,7,1,2,2,1,4,3,2,4,调整方法(二)方法一的缺点：在运用判别式时，必须工序每移动一次，就要对网络计划的工序进行调整，重新计算资源量，作图和计算工作量大。对下图中工序2-7分析,(1)根据式(5-2)2-7可右移1d，如圆点所示,8,9两天资源量无变化，只考虑7,10两天,1,3,5,4,6,2,7,1,2,2,1,4,3,2,1,3,5,4,6,2,7,1,2,2,1,4,3,2,(2)2-7可再右移1d，如点划线所示，与圆点相比较，8,11两天资源量有变化。,(3)工序可再右移1d，如虚线所示，与点划线比较，9,12两天资源量变化。,1,3,5,4,6,2,7,1,2,2,1,4,3,2,(4)注意：式中第10天与初始网络图中的第10天的资源量不一致。,1,3,5,4,6,2,7,1,2,2,1,4,3,2,工序右移的判别公式：本次调整的累计右移时间为L1，单一工序一次右移一个时间单位：当L1tij时，当L1tij时，若满足上两式，则可将该工序右移1个时间单位。单一工序一次右移T1个时间单位当L1tij时，当L1tij时，注：上述公式中的资源量均是该本次调整前的网络图中的资源量。不必移动一次工序，就对资源量进行重新计算。,例：以图5-11为例,1,3,5,4,6,2,7,1,2,2,1,4,3,2,4,第一次调整：节点：以为结束节点的非关键工序有2-7和5-7。(1)先考虑5-7工序：a=3,b=10,TF=FF=5,R=4,t=7应用公式(5-5)，以初始网络图为基础：可右移1d 可右移1d，共2d 可右移1d，共3d 可右移1d，共4d 可右移1d，共4d 可右移1d，共5d右移后的时标网络图及每资源需要量如下图,1,3,5,4,6,2,7,1,2,2,1,4,3,2,4,以上图为基础，考虑工序2-7：a=6,b=9,TF=FF=6,R=3,t=3应用式(5-5)不能右移1d 应用式(5-7)不能右移2天。应用式(5-8)不能右移4天，同理，可推导2-7不能移动,节点：只有非关键工序3-5，a=2,b=3,TF=5,R=2,t=1 可右移1 d 此时，L1=1=t=1,以下计算L1将大于t,应用公式(5-6)。可再右移1d，共2d 可推导3-5可右移共5天。问题：直接应用公式5-8推导3-5能否右移5天。调整后见下图。,1,3,5,4,6,2,7,1,2,2,1,4,3,2,4,节点：非关键工序1-3，可推导，1-3可右移5天，第一次调整结束。第二次调整，无工序可调整，过程结束。,1,3,5,4,6,2,7,1,2,2,1,4,3,2,4,(二)用“使极差值为最小”方法均衡资源极差值为：资源平均值为常数，因此欲使极差值最小，应使 最小，即使每天资源的最大用量为最低，常用“削高峰法”。利用时差将高峰的某些工序后移以逐步降低峰值，每次削去高峰的一个资源计量单位，反复进行直到不能再削为止。,例：某工程网络计划如下图。,1,2,3,4,6,9,10,5,7,8,(4),4,(1),3,(3),2,(2),4,(3),3,(4),5,(2),3,(5),5,(4),5,(3),3,(2),3,(2),2,解：第一步：按最早开始时间绘制时标网络计划，计算每日资源需要量动态数列 第二步：确定资源数量上限(动态数列中的最大 值减去它的一个计量单位，本例中,在本例中，最大值是第5天的11，则削峰目标为：R=11-1=10第三步：分析资源限值的高峰并调整。如时段内的资源量超过限值用正式判断能否调整：,1,2,4,5,6,7,9,8,10,3,(4),(1),(3),(2),(4),(2),(5),(3),(4),(2),(2),(3),如时段内的资源量超过限值用正式判断能否调整：若不等式成立，则该可以向右移动至高峰值之后，即移 个时间单位；不等不成立，则不能移动。当在需要调整的时段内不止一个工序可使不等成立时，就按时间差值的大小顺序移动。如时间差值相同，就使资源数量小的优先移动。在本例中，第5天资源数量为11，超过R=10的规定，这个时段内2-5、2-4、3-6、3-10四个工序，分别计算它们的时间差值。将3-10向右移动2天。见下图,1,2,4,5,6,7,9,8,10,3,(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天。资源数量见下表。,第6,7两资源数量超过R=8，此时段中有工序2-5.2-4、3-6、3-10计算时间差值：如是选择3-10，但其资源数量为2，移动后仍不能解决资源冲突，故移动3-6，将其右移2天。,第8,9两天资源数量超过R=8，此时段中有工序2-4、3-6、3-10，计算时间差值：,得：将3-10优先调整，向右移动 4天，见下表。第10至13天资源数量超过R=8，时段内有工序5-7、4-6、3-10、6-9。将3-10向后移动 4天，计算每日资源数量后，第14天仍超过，将其再后移1天，满足R=8，第二次调整完成。画出时标网络图。,第二次调整后的时标网络计划,1,2,4,5,6,7,9,8,10,3,(4),(1),(3),(2),(4),(2),(5),(3),(4),(2),(2),(3),第三次调整，资源数量上限定为R=8-1=7第10天、第12天资源数量超过R=7，工序有4-6、5-7计算：选择4-6调整，向右移动3天，因工序4-6没有自由时差，须与6-9一起移动。资源量见下表,第13至17天超过R=7，有工序5-7、4-6、6-9、7-8、3-10，先考虑13至14天的资源冲突，只有工序4-6,5-7，向后移动4-6 2天，工序也称移动2天。,第15天至18天资源数量还超过R=7，有工序7-8、4-6、3-10，分别计算后，将工序3-10调整，向右移动4天，计算资源数量。此时第19天资源超过R=7，但所有工序已不能右移。,1,2,4,5,6,7,9,8,10,3,(4),(1),(3),(2),(4),(2),(5),(3),(4),(2),(2),(3),第四步：当所有工序不能右移时，应考虑将工序左移。工序3-10最早开始时间在第3天，在第3天至第18天时间段中，第10至14天资源数量为5，可将该工序左移至第10天以后开始，即可满足资源数量上限要求。绘制时标网络图。,2,4,5,6,7,9,8,10,3,(4),(1),(3),(2),(4),(2),(5),(3),(4),(2),(2),(3),1,