运筹学chap7 网络计划

PERT网络图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节网络计划图的时间参数计算*整个工程所需的最短时间就等于关键路线所需的时间，因此关键工序完工时间的提前或拖延就直接影响了整个工程的完工时间。第2节网络计划图的时间参数计算绘制出网络图后，通过时间参数计算即可找出关键路线时间参数计算：工作持续时间（D）工作最早开始时间（ES）工作最早完成时间（EF）工作最迟开始时间（LS）工作最迟完成时间（LF）工作总时差（TF）工作自由时差（FF）第2节网络计划图的时间参数计算2.1工作持续时间D计算工作持续时间通常有两种方法，所用到的数据也有所不同。1、单时估计法（定额法）根据工作的工作量、劳动定额资料以及投入的人力多少等，计算各工作的持续时间。2.1工作持续时间DnSRQD其中，D---工作的工作量；R---可投入的人力和设备的数量；S---每人或每台设备每工作班能完成的工作量；n---每天正常工作班数。使用条件：具有类似工作的持续时间的历史统计资料。2.1工作持续时间D2、三时估计法不具有类似工作的持续时间的历史统计资料时，对工作进行估计三种时间值，然后计算其平均值。2.1工作持续时间D64bmaD其中，乐观时间a---在一切都顺利时，完成工作所需的最小时间；最可能时间m---在正常条件下，完成工作所需的最小时间；悲观时间b---在一切都顺利时，完成工作所需的最小时间。22)6(ab方差第2节网络计划图的时间参数计算2.2计算关系式（1）计算各工作的持续时间（2）按网络图箭头的方向，从起始工作开始，计算各工作的ES和EF；（3）从网络图终点节点开始，按逆箭头的方向，推算工作的LS和LF；计算步骤：2.2计算关系式（4）确定关键路线（CP);（5）计算TF和FF；（6）平衡资源。2.2计算关系式时间参数关系2.2计算关系式1、工作最早开始时间ES和工作最早完成时间EF由于任一工作只能在其所有的紧前工作结束之后开始，所以任一工作的最早开始时间等于其所有的紧前工作最早完成时间中的最大值。最早开始时间的计算应从网络的始点开始，按顺序计算各个工作的值。最早完成时间是它的最早开始时间加上该工作的持续时间之和。2.2计算关系式从起始点开始，按网络图箭头的方向，计算各工作的ES和EF。第一项工作的最早开始时间为0，记为ESi-j=0（起始点i=1）。第一项工作的最早完成时间为EF1-j=ES1-j+D1-j。第一项工作完成后，其紧后工作才能开始。前一项工作的最早完成时间EF就是其紧后工作最早开始时间ES。本工作的持续时间为D。表示为：EFi-j=ESi-j+Di-j2.2计算关系式如果某项工作有多项紧前工作，则只有在这些紧前工作都完成后，本项工作才能开始。因此本项工作的最早开始时间是：ES=max（紧前工作的EF）。其中，EF=ES+工作持续时间D。表示为：ESi-j=maxh(EFh-j)=maxh(ESh-j+Dh-j)参见p216表8-3。2.2计算关系式2、工作最迟开始时间LS和工作最迟完成时间LF在不影响整个工程的最早完工时间的条件下，任一工作的最迟完成时间等于其所有紧后工作的最迟开始时间中的最早时间。最迟完成时间的计算从网络的终点开始，从右向左反向进行。最迟开始时间是它的最迟完成时间减去该工作的持续时间之差。2.2计算关系式网络图中最后一项工作(i-j)(j=n)的最迟完成时间应由工程的计划工期确定。如果没有给定，则可以令其等于最早完成时间，即LFi-n=EFi-n。而EFi-n的结果已经出来了，并且应当小于或等于计划工期规定的时间Tr。LF=min(紧后工作的LS)，LS=LF-工作持续时间D2.2计算关系式其它工作的最迟开始时间LSi-j=LFi-j-Di-j；当有多个紧前工作时，最迟完成时间LF=min(紧后工作的LS)，或表示为：LFi-j=mink(LFj-k-Dj-k)参见p217表8-4。2.2计算关系式3、工作时差工作时差是指工作有机动时间。常用的有两种时差：工作总时差和工作自由时差。（1）工作总时差TFi-jTFi-j是指在不影响工期的前提下，工作所具有的机动时间，按工作计算法计算。参见p217表8-4中⑦=⑥-③的数据。jijijijijijijijijiEFLFTFESLSDESEFTF或;2.2计算关系式注意：工作总时差往往为若干项工作共同拥有的机动时间。2.2计算关系式（2）工作自由时差FF工作自由时差是指：在不影响其紧后工作最早开始的前提下，工作所具有的机动时间。工作自由时差是某项工作单独拥有的机动时间，其大小不受其它工作机动时间的影响。jikjjijijikjjiEFESFFDESESFF或;参见p217表8-4中⑧和p215图8-7。2.2计算关系式关键路线的特征：在线路上从起点到终点都是由关键工作组成。在确定型网络计划中是指线路中工作总持续时间最长的线路。在关键线路上无机动时间，工作的总时差为零。在非确定网络计划中是指估计工期完成可能性最小的线路。第8章网络计划第3节时标网络计划图时间坐标简称为时标。时标在网络计划图的上方或下方，用以表示工程进度的坐标轴。根据需要规定时间单位为：小时、天、周、月或季。标注有时间坐标的网络计划图称为时标网络计划图。在该图上箭头的长度就表示工作持续时间的长度。在图中可以用实粗箭头表示关键工作和关键路线。并且可用不同的线型表示出工作的总时差和自由时差。第3节时标网络计划图例2(p211例1)的时标网络计划图。第8章网络计划第4节网络计划的优化绘制网络图、计算时间参数和确定关键路线得到的只是一个初始的计划方案。为了得到一个较(最)好的方案通常还需要从工期、费用、资源利用等方面对初始计划方案进行调整和改善，这一过程就是网络计划的优化。第4节网络计划的优化4.1工期优化若网络计划图的计算工期大于要求的工期，必须根据要求计划的进度，缩短工程项目的完工工期。主要采用以下措施，增加对关键工作的投入，以便缩短关键工作的持续时间，实现工期的缩短。（1）采取技术措施，提高工效，缩短关键工作的持续时间，使关键路线的时间缩短。（2）采取组织措施，充分利用非关键工作的总时差，合理调配人力、物力和资金等资源。第4节网络计划的优化4.2资源优化由于实际工程项目包括了众多工作，涉