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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,网络计划优化,资源优化专题,第一节 工期,-,资源优化,内容：根据资源情况对网络计划进行调整，在规定工期和资源供应之间寻求相互协调和相互适应。,(1)“,资源有限，工期最短”优化,在资源供应有限制的条件下，寻求计划的最短工期,(2)“,工期固定，资源均衡”优化,在工期规定的条件下，力求资源消耗均衡。,优化前提：,(1),网络计划一经制定，在优化过程中不得改变各工序的持续时间；,(2),各工序每天的资源需要是均衡的，合理的，优化过程中不予改变；,(3),除规定可以中断的工序外，其它工序均应连续作业。,(4),优化过程中不得改变网络计划各工序间的逻辑关系。,时段与,工序的关系：,网络计划的每日资源需要量曲线是资源优化的初始状态。每日资源需要量曲线的每一变化都说明有工序在该时间点开始或结束。每日资源需要量不变且连续的一段时间，称为时段，用,t,a,表示时段开始时间，,t,b,表示时段完成时间，可用,t,a,t,b,表示这个时段。,一、资源有限，工期最短优化,设某工程项目需要,S,种不同的资源，已知每天可能供应的资源数量分别为,R,1,(t),、,R,2,(t),、,R,s,(t,),，,完成每一个工序只需其中一种资源，设为第,K,种资源，单位时间资源需要量,(,强度,),以表示，并假定为常数，在资源供应满足的条件下，完成工序,i-j,持续时间为,t,ij,，,对资源有限，工期最短优化，可按照极差原理确定其最优方案，即网络计划资源动态曲线中任何资源时段,t,a,t,b,内,每天的资源消耗量总和,Rk,均应小于或等于该计划每天的资源限定量,Rt,，,即满足,RkRt,(,一,),时差、资源分析法,1,、分析步骤,(1),根据网络的逻辑关系和各工序作业持续时间，绘出相应于各工序最早开始的时标网络图及资源需要量动态图。,(2),逐个时段对资源总需要量进行检查，若不满足供应限量的要求时，则就需要对计划进行调整。直到所有内资源总需要量都满足供应限量的要求为止。,2,、,各时段内资源分析及工序计划调整的原则。,(1),第一时段，假定在时段,t,0,t,1,内，当资源总需要量不满足限量要求时：,先对位于关键线路上的工序进行编号，其次对位于非关键线路上的工序按其总时差递增顺序进行编号，如总时差相等，则按工序每天资源需要量递减的顺序编号。,把位于本时段内的工序，按编号由小到大顺序依次分配每天所需资源，以不超过可能供应的数量为限，余下的工序分配不到资源就右移到,t,1,开始。,(2),其它时段，假定已计算至,K,步，在时段,t,0,t,k,内的工序 每天资源需要量之和没有超过供应的限量时，则就继续计算第,K+1,步。,先绘出前一步工序 右移后的新的时标网络图及资源需要量动态图；,其次检查时段,t,k,t,k+1,内资源总需要量是否超过供应的限量，若超过就对,t,k,t,k+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,绘制时标网络图，图中箭线数字为该工序资源需要量，并该图下方绘出资源动态曲线。,施工进度计划,(,天,),1,2,3,4,5,6,7,8,9,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),单一工作右移几个时间单位,在工序时差范围内逐一试算是否可一次右移一至多个时间单位。,如果以,T,1,记录一次右移的时间，以,L,表示该工序能右移的最大时间，现已移动了,L,1,个时间单位，则,T,1,L-L,1,若,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,2,3,4,5,6,7,8,9,10,11,12,13,14,15,7,7,8,10,9,9,8,8,8,5,2,2,2,2,2,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=4,R(10+1)-R(3+1)+R,5,，,7,=2-10+4=-40,，,可右移一天。若,5-7,工序再右移,1d,，,根据式,5-2,有：,R(10+2)-R(3+2)+R,5,，,7,=2-9+4=-30,，,可以右移,1,天，共,2,天。,R(10+3)-R(3+3)+R,5,，,7,=2-9+4=-30,，可再右移,1,天，共,3,天。,R(10+4)-R(3+4)+R,5,，,7,=-20,，可再右移,1,天，共,4,天。,R(10+5)-R(3+5)+R,5,，,7,=-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)+R,3,，,5,=6-8+2=0,，,可右移,1,天。,R(3+2)-R(2+2)+R,3,，,5,=5-8+2=-10,，,可再右移,1,天。,3-5,工序共右移,5,天。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,7,7,6,8,5,5,4,4,8,5,6,6,6,6,6,7,7,6,6,7,5,4,4,8,5,6,6,6,6,6,1,3,5,4,6,2,7,1,2,2,1,4,3,2,4,3-5,工序右移,5,天后的网络图。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,7,7,6,6,5,5,4,6,8,5,6,6,6,6,6,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,2,3,4,5,6,7,8,9,10,11,12,13,14,15,6,6,6,6,5,6,5,6,8,5,6,6,6,6,6,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,2,3,4,5,6,7,8,9,10,11,12,13,14,15,7,7,8,10,9,9,8,8,8,5,2,2,2,2,2,1,3,5,4,6,2,7,1,2,2,1,4,3,2,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,7,7,8,10,9,9,8,8,8,5,2,2,2,2,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,2,3,4,5,6,7,8,9,10,11,12,13,14,15,7,7,8,10,9,9,8,8,8,5,2,2,2,2,2,1,3,5,4,6,2,7,1,2,2,1,4,3,2,(4),注意：式中第,10,天与初始网络图中的第,10,天的资源量不一致。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,7,7,8,10,9,9,8,8,8,5,2,2,2,2,2,1,3,5,4,6,2,7,1,2,2,1,4,3,2,工序右移的判别公式：本次调整的累计右移时间为,L,1,，,，,单一工序一次右移一个时间单位,：,当,L,1,tij,时，,当,L,1,tij,时，,若满足上两式，则可将该工序右移,1,个时间单位。,单一工序一次右移,T,1,个时间单位,当,L,1,tij,时，,当,L,1,tij,时，,注：上述公式中的资源量均是该本次调整前的网络图中的资源量。不必移动一次工序，就对资源量进行重新计算。,例：以图,5-11,为例,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,7,7,8,10,9,9,8,8,8,5,2,2,2,2,2,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,2,3,4,5,6,7,8,9,10,11,12,13,14,15,7,7,8,6,5,5,4,4,8,5,6,6,6,6,6,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,此时，,L,1,=1=t=1,以下计算,L,1,将大于,t,应用公式,(5-6),。,可再右移,1d,，共,2d,可,推导,3-5,可右移共,5,天。,问题：直接应用公式,5-8,推导,3-5,能否右移,5,天。,调整后见下图。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,7,7,6,6,5,5,4,6,8,5,6,6,6,6,6,1,3,5,4,6,2,7,1,2,2,1,4,3,2,4,节点：非关键工序,1-3,，,可推导，,1-3,可右移,5,天，第一次调整结束。,第二次调整，无工序可调整，过程结束。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,6,6,6,6,5,6,5,6,8,5,6,6,6,6,6,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,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,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,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,5,5,5,7,9,8,8,6,6,8,8,8,7,7,4,4,4,4,4,5,5,5,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,天。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,5,5,5,4,6,11,11,6,6,8,8,8,7,7,4,4,4,4,4,5,5,5,第,8,9,两天资源数量超过,R=8,，,此时段中有工序,2-4,、,3-6,、,3-10,，计算时间差值：,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,5,5,5,4,6,8,8,9,9,8,8,8,7,7,4,4,4,4,4,5,5,5,得：,将,3-10,优先调整，向右移动,4,天，见下表。,第,10,至,13,天资源数量超过,R=8,，,时段内有工序,5-7,、,4-6,、,3-10,、,6-9,。,将,3-10,向后移动,4,天，计算每日资源数量后，第,14,天仍超过，将其再后移,1,天，满足,R=8,，,第二次调整完成。画出时标网络图。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,5,5,5,4,6,6,6,7,7,10,10,10,9,7,4,4,4,4,4,5,5,5,第二次调整后的时标网络计划,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,5,5,5,4,6,6,6,7,7,8,8,8,7,7,6,6,6,6,4,5,5,5,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,一起移动。资源量见下表,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,5,5,5,4,6,6,6,7,7,5,5,5,10,10,9,8,8,6,4,5,5,5,第,13,至,17,天超过,R=7,，,有工序,5-7,、,4-6,、,6-9,、,7-8,、,3-10,，先考虑,13,至,14,天的资源冲突，只有工序,4-6,5-7,，,向后移动,4-6 2,天，工序也称移动,2,天。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,5,5,5,4,6,6,6,7,7,5,5,5,7,7,9,9,9,8,6,5,5,5,第,15,天至,18,天资源数量还超过,R=7,，,有工序,7-8,、,4-6,、,3-10,，分别计算后，将工序,3-10,调整，向右移动,4,天，计算资源数量。此时第,19,天资源超过,R=7,，,但所有工序已不能右移。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,5,5,5,4,6,6,6,7,7,5,5,5,5,5,7,7,7,6,8,7,7,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,天以后开始，即可满足资源数量上限要求。绘制时标网络图。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,5,5,5,4,6,6,6,7,7,5,7,7,7,7,7,7,7,6,6,5,5,5,2,4,5,6,7,9,8,10,3,(4),(1),(3),(2),(4),(2),(5),(3),(4),(2),(2),(3),1,