运筹学chap7 网络计划1

PERT网络图网络图时间参数的计算关键路线和网络计划的优化网络计划(ProgramEvaluationandReviewTechnique)网络计划技术被广泛应用于建筑施工和新产品的研制计划、计算机系统的安装调试及各种大型复杂工程的控制管理。基本原理：首先是把所要做的工作，哪项工作先做，哪项工作后做，各占用多少时间，以及各项工作之间的相互关系等运用网络图的形式表达出来；其次是通过简单的计算，找出哪些工作是关键的，哪些工作不是关键的，并在原来计划方案的基础上，进行计划的优化。第1节网络计划图网络计划图的基本思想是，首先应用网络计划图来表示工程项目中计划要完成的各项工作，完成各项工作必然存在先后顺序及其相互依赖的逻辑关系；这些关系用节点和箭线来构成网络图。第1节网络计划图1.1基本术语网络图又称箭线图，是由箭线和节点组成的，用来表示工作流程的有向、有序的网状图形。网络计划图是在网络图上标注时标和时间参数的进度计划图，实质上是有时序的有向赋权图。表述关键路线法(CPM)和计划评审技术(PERT)的网络计划图并无本质的区别。下面介绍PRET网络图。1.1基本术语1、绘图符号和术语(1)工作（活动、工序、作业）任何一项计划，都包含许多项待完成的工作。在网络图中，工作用箭线(弧)表示。箭尾表示工作的开始，箭头表示工作的完成。箭头的方向表示工作的前进方向（从左向右）。工作的名称或内容写在箭线的上面，持续时间写在箭线的下面：工作名称持续时间ij双代号网络计划图1.1基本术语（2）节点节点表示工作之间的联结。在时间上它表示指向某节点的工作全部完成后，该节点后面的工作才能开始。节点用圆圈表示，圆圈中编上整数号码。对于某项工作来说，紧接在其箭尾节点前面的工作，是其紧前工作，紧接在其箭头节点后面的工作是其紧后工作；和它同时进行的工作称为平行工作。1.1基本术语（3）虚工作虚工作仅仅表示工作之间的先后顺序，用虚线箭线表示，它的持续时间0。1.1基本术语2、各项工作之间的关系以及各项工作在网络图上的表达方式（1）工作a结束后才可以开始b和c。1.1基本术语（2）工作c在a和b均结束后才能开始。1.1基本术语（3）a和b两作工序均结束后才可以开始c和d。1.1基本术语（4）工作c在a结束后即可进行，但工作d必须同时在a和b结束后才能开始。←虚工序第1节网络计划图1.2双代号网络计划图１、绘图规则（1）起点和终点为了表示工程的开始和结束，网络图只能有一个起点和一个终点。（2）方向与节点网络图是有向图，按照工艺流程的顺序，规定工作从左向右排列。1.2双代号网络计划图（3）虚工作用虚线箭线表示。它表示工时为零，不消耗任何资源的虚构工作。其作用只是为了正确表示工作间的先后次序关系。（4）两个节点之间不能有两道或两道以上的工作。即两个节点只能表示一道工序，否则将造成逻辑上的混乱。123abc12abc43×√1.2双代号网络计划图（5）网络图中不能有缺口和回路。有缺口，将使某些工作失去与其紧前或紧后工作应有的联系；有回路，将使组成回路的工作永远不能结束，工程永远不能完工。×1.2双代号网络计划图(6)平行作业为缩短工程的完工时间，在条件允许的情况下，某些工作可以同时进行，即可采用平行作业的方式。如下图中的工作b，c，d。1.2双代号网络计划图（7）交叉作业对需要较长时间才能完成的一些工作，在工艺流程与生产组织条件允许的情况下，可以不必等待该工作全部结束后再转入其紧后工序，而是分期分批的转入。这种方式称为交叉作业。交叉作业可以缩短工程的完工时间。如工作A与工作B分别为挖沟和埋水管，可以挖一段埋一段，不必等沟全部挖好后再埋。这种关系可以用交叉作业来表示，如果把这两项工作各分为三段，则A=a1+a2+a3，B=b1+b2+b3，如下图所示。1.2双代号网络计划图123a1b14567a3a2b3b2交叉作业1.2双代号网络计划图（8）网络图布局网络图中尽可能将关键路线布置在中心位置，将联系紧密的工作布置在相近的位置。为了使网络图清楚和便于在图上填写有关数据，箭线尽量用水平线或具有一段水平线的折线(什么是关键路线？后面介绍)。1.2双代号网络计划图2、绘图步骤（1）将一个任务分解成若干个工作（工序）；（2）分析这些工作之间的关系；（3）在前两步的基础上，遵循前边的绘图规则作出网络图。1.2双代号网络计划图3、实例例1某项建筑工程的部分工作与所需时间以及它们之间的关系如下表所示。工作工作代号所需时间（周）紧前工作详细设计a3/材料采购b4a招聘工人c1a主体工程d6c上顶e4b,d1.2双代号网络计划图步骤1、2可用上表表示。根据表所示的工作及它们之间的关系可作出网络图。12acb45de3341641.2双代号网络计划图例2某项研制新产品工程的各个工作与所需时间及它们之间的相互关系见下表。作出该项工程的网络计划图。工作代号时间紧后产品设计A60B,C,D,E外购配套件B45L下料、锻件C10F工装制造1D20G,H木模、铸件E40H工作代号时间紧后机械加工1F18L工装制造2G30K机械加工2H15L机械加工3K25L装配调试L35/1.2双代号网络计划图网络图中的虚工作④⑤表示在D工作结束后H工作才能开始。工作代号时间紧后产品设计A60B,C,D,E外购配套件B45L下料、锻件C10F工装制造1D20G,H木模、铸件E40H工作代号时间紧后机械加工1F18L工装制造2G30K机械加工2H15L机械加工3K25L装配调试L35/第2节网络计划图的时间参数计算定义：在网络图中，从始点开始，按照各个工序的顺序，连续不断地到达终点的一条路称为路线。而这样的路线往往有多条，称其中时间最长的路线为关键路线（CP），关键路线上的工作称为关键工作。*整个工程所需的最短时间就等于关键路线所需的时间，因此关键工序完工时间的提前或拖延就直接影响了整个工程的完工时间。2.1工作持续时间D计算工作持续时间通常有两种方法，所用到的数据也有所不同。1、单时估计法（定额法）根据工作的工作量、劳动定额资料以及投入的人力多少等，计算各工作的持续时间。nSRQD其中，Q---工作的工作量；R---可投入的人力和设备的数量；S---每人或每台设备每工作班能完成的工作量；n---每天正常工作班数。使用条件：具有类似工作的持续时间的历史统计资料。2、三时估计法不具有类似工作的持续时间的历史统计资料时，对工作进行估计三种时间值，然后计算其平均值。64bmaD其中，乐观时间a---在一切都顺利时，完成工作所需的最小时间；最可能时间m---在正常条件下，完成工作所需的最小时间；悲观时间b---在一切都顺利时，完成工作所需的最小时间。22)6(ab方差根据大量统计，它服从分布，其三个节点时间参数节点最早时间TE节点的最迟时间TL节点时差R（i）2.2节点时间参数计算关系式节点的时间参数计算：节点最早时间TE：节点i的最早时间TEi是以i节点开始的各项工序最早可以开工时间。它等于从始点开始到该节点的最长路线的时间。计算公式：TE1=0TEj=max[TEi+Di-j]节点的最迟时间TL：节点i的最迟时间TLj是以j节点结束的各项工序最迟必须结束的，否则就会延误整个工期。它等于总周期减去该节点到终点的最长路线的时间。计算公式：TLn=TEnTLi=min[TLj-Di-j]节点时差Ri：该节点最迟时间和最早时间之差。计算公式：Ri=TLi-TEiB(3)D(8)G(4)2915A(3)84C(3)E(5)F(4)36710H(2)I(2)B(3)D(8)G(4)2915A(3)84C(3)E(5)F(4)36710H(2)I(2)036661114111820039961414161820工作的六个时间参数ESi-j(EarliestStartingTime)EFi-j(EarliestFinishingTime)LSi-j(LatestStartingTime)LFi-j(LatestFinishingTime)TFi-j(TotalFloatTime)FFi-j(FreeFloatTime)2.3工作时间参数计算关系式最早时间参数ESi-j和EFi-j最早开始时间等于其所有的紧前工作最早结束时间中的最大值：ESi-j=max[EFh-i]=max[ESh-i+Dh-i]最早结束时间是它的最早开始时间加上该工作的持续时间之和：EFi-j=ESi-j+Di-j12345610545101010ES1-2=0EF1-2=ES1-2+D1-2=0+10=10ES1-3=0EF1-3=ES1-3+D1-3=0+5=5ES3-5=max[EF1-3]=5EF3-5=ES3-5+D3-5=5+4=9ES2-5=max[EF1-2]=10EF2-5=ES2-5+D2-5=10+5=15ES2-4=max[EF1-2]=10EF2-4=ES2-4+D2-4=10+10=20ES4-5=max[EF2-4]=20EF4-5=ES4-5+D4-5=20+10=30ES5-6=max[EF3-5,EF2-5,EF4-5]=max[9,15,30]=30EF5-6=ES5-6+D5-6=30+10=40最迟时间参数LSi-j和LFi-j最迟结束时间等于其所有紧后工作的最迟开始时间中的最小值：LFi-j=min[LSj-k]=min[LFj-k–Dj-k]最迟开始时间是它的最迟结束时间减去该工作的持续时间之差：LSi-j=LFi-j–Di-j12345610545101010LS5-6=LF5-6-D5-6=40-10=30LF5-6=40LS3-5=LF3-5-D3-5=30-4=26LF3-5=min[LS5-6]=30LS2-5=LF2-5-D2-5=30-5=25LF2-5=min[LS5-6]=30LS4-5=LF4-5-D4-5=30-10=20LF4-5=min[LS5-6]=30LS2-4=LF2-4-D2-4=20-10=10LF2-4=min[LS4-5]=20LS1-3=LF1-3-D1-3=26-5=21LF1-3=min[LS3-5]=26LS1-2=LF1-2-D1-2=10-10=0LF1-2=min[LS2-5,LS2-4]=min[25,10]=10总时差TFi-j在不影响工期的前提下，工作所具有的机动时间：jijijijijijiEFLFTFESLSTF或;若干项工作共同拥有的机动时间。自由时差FFi-j在不影响其紧后工作最早开始的前提下，工作所具有的机动时间：jikjjiEFESFF某项工作单独拥有的机动时间，其大小不受其它工作机动时间的影响关键路线是由总时差为0的工序所组成的路线。关键路线上的各工序开始时间和结束时间没有一点机动的余地。网络图制成以后，把时差为0的工序连接起来得到的一条路线就是关键路线。关键路线的特点：(1)关键路线上的工序，时差等于0。(2)关键路线是从网络计划开始点到结束点之间持续时间最长的路线。(3)关键路线在网络计划中不一定只有一条，有时存在两条以上。第3节网络计划的优化绘制网络图、计算时间参数和确定关键路线得到的只是一个初始的计划方案。为了得到一个较(最)好的方案通常还需要从工期、费用、资源利用等方面对初始计划方案进行调整和改善，这一过程就是网络计划的优化。资源优化成本优化工期优化网络计划优化3.1工期优化若网络计划图的计算工期大于要求的工期，必须根据要求计划的进度，缩短工程项目的完工工期。主要采用以下措施，增加对关键工作的投入，以便缩短关键工作的持续时间，实现工期的缩短。在确定需缩短持续时间的关键工序时，应注意以下几个方面：1.缩短持续时间对质量和安全影响不大的工序；2.有充足备用资源的工序；3.缩短持续时间所需增加的工人或材料最少的工序；4.缩短持续时间所需增加的费用最少的工序。网络计划的工期优化步骤1.计算并找出网络计划的计算工期、关键线路及关键工序。2.按计划工期，计算出工期应缩短的时间目标ΔT：ΔT＝Tc－T