《运筹学chap7网络计划1》由会员分享，可在线阅读，更多相关《运筹学chap7网络计划1（63页珍藏版）》请在金锄头文库上搜索。
1、PERT网络图网络图时间参数的计算关键路线和网络计划的优化网络计划(Program Evaluation and Review Technique)网络计划技术被广泛应用于建筑施工和新产 品的研制计划、计算机系统的安装调试及各种 大型复杂工程的控制管理。基本原理：首先是把所要做的工作，哪项工作先做，哪项工作后做，各占用多少时间，以 及各项工作之间的相互关系等运用网络图的形 式表达出来；其次是通过简单的计算，找出哪 些工作是关键的，哪些工作不是关键的，并在 原来计划方案的基础上，进行计划的优化。第1节 网络计划图网络计划图的基本思想是，首先应用网络计划图来表示工程项目中计划要完成的各项工作，完成
2、各项工作必然存在先后顺序及其相互依赖的逻辑关系；这些关系用节点和箭线来构成网络图。第1节 网络计划图1.1 基本术语网络图又称箭线图，是由箭线和节点组成的， 用来表示工作流程的有向、有序的网状图形。网络计划图是在网络图上标注时标和时间参数的进度计划图，实质上是有时序的有向赋权图。 表述关键路线法(CPM)和计划评审技术(PERT) 的网络计划图并无本质的区别。下面介绍PRET网络图。1.1 基本术语1、绘图符号和术语(1) 工作（活动、工序、作业）任何一项计划，都包含许多项待完成的工作。 在网络图中，工作用箭线(弧)表示。箭尾表示工作的开始，箭头表示工作的完成。箭头的方向表示工 作的前进方向（
3、从左向右）。工作的名称或内容写 在箭线的上面，持续时间写在箭线的下面：双代号网络计划图1.1 基本术语（2）节点节点表示工作之间的联结。在时间上它表示指向某节点的工作全部完成后，该节点后面的工作 才能开始。节点用圆圈表示，圆圈中编上整数号码。对于某项工作来说，紧接在其箭尾节点前面的工作，是其紧前工作，紧接在其箭头节点后面的 工作是其紧后工作；和它同时进行的工作称为平 行工作。1.1 基本术语（3）虚工作虚工作仅仅表示工作之间的先后顺序，用虚 线箭线表示，它的持续时间0。1.1 基本术语2、各项工作之间的关系以及各项工作在网络图上的表达方式 （1）工作a 结束后才可以开始b 和c。1.1 基本术
4、语（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）两个节点之间不能有两道或两
5、道以上的工作。即两个节点只能表示一道工序，否则将 造成逻辑上的混乱。1.2 双代号网络计划图（5）网络图中不能有缺口和回路。有缺口，将使某些工作失去与其紧前或紧后工作应有的 联系；有回路，将使组成回路的工作永远不能 结束，工程永远不能完工。1.2 双代号网络计划图(6) 平行作业 为缩短工程的完工时间，在条件允许的情况下，某些工作可以同时进行 ，即可采用平行作业的方式。如下图中的工 作b，c，d。1.2 双代号网络计划图（7）交叉作业 对需要较长时间才能完成的一些工作，在工艺流程与生产组织条件允许的 情况下，可以不必等待该工作全部结束后再转 入其紧后工序，而是分期分批的转入。这种方 式称为交叉
6、作业。交叉作业可以缩短工程的完 工时间。如工作A与工作B分别为挖沟和埋水管，可以挖一段埋一段，不必等沟全部挖好后再 埋。这种关系可以用交叉作业来表示，如果把 这两项工作各分为三段，则A=a1+a2+a3， B=b1+b2+b3，如下图所示。 1.2 双代号网络计划图交叉作业1.2 双代号网络计划图（8）网络图布局 网络图中尽可能将关键路线布置在中心位置，将联系紧密的工作布置在 相近的位置。为了使网络图清楚和便于在图上 填写有关数据，箭线尽量用水平线或具有一段 水平线的折线(什么是关键路线？后面介绍)。1.2 双代号网络计划图2、绘图步骤（1）将一个任务分解成若干个工作（工序）； （2）分析这些
7、工作之间的关系； （3）在前两步的基础上，遵循前边的绘图规则作出网络图。1.2 双代号网络计划图3、实例例1 某项建筑工程的部分工作与所需时间以及它们之间的关系如下表所示。工 作工作代号所需时间时间 （周）紧紧前工作详细设计详细设计a3/材料采购购b4a 招聘工人c1a主体工程d6c上 顶顶e4b,d1.2 双代号网络计划图步骤1、2可用上表表示。 根据表所示的工作及它们之间的关系可作出网络图。1.2 双代号网络计划图例2 某项研制新产品工程的各个工作与所需时间及它们之间的相互关系见下表。作出该项工程的 网络计划图。工 作代 号时时 间间紧紧 后产产品设计设计A60B,C,D,E 外购购配套件
8、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节 网络计划图的时间参数计算定义：在网络图中
9、，从始点开始，按照各个工序的顺序，连续不断地到达终点的一条路称为路线。而这样的路线往往有多条，称其中时间最长的路线为关键路线（CP），关键路线上的工作称为关键工作。*整个工程所需的最短时间就等于关键路线所需的时间，因此关键工序完工时间的提前或拖延就直接影响了整个工程的完工时间。2.1 工作持续时间D计算工作持续时间通常有两种方法，所用到的 数据也有所不同。1、单时估计法（定额法）根据工作的工作量、劳动定额资料以及投入 的人力多少等，计算各工作的持续时间。其中，Q-工作的工作量；R-可投入的人力和设备的数量；S-每人或每台设备每工作班能完成的工作量；n-每天正常工作班数。使用条件：具有类似工作的
10、持续时间的历史 统计资料。2、三时估计法不具有类似工作的持续时间的历史统计资料时，对工作进行估计三种时间值，然后计算其平均值。其中，乐观时间a-在一切都顺利时，完成工作所需 的最小时间；最可能时间 m-在正常条件下，完成工作所 需的最小时间；悲观时间b-在一切都顺利时，完成工作所需 的最小时间。方差根据大量统计统计 ，它服从 分布，其 三个节点时间参数 节点最早时间TE 节点的最迟时间TL 节点时差R（i）2.2 节点时间参数计算关系式节点的时间参数计算： 节点最早时间TE：节点i的最早时间TEi是以i节点开 始的各项工序最早可以开工时间。它等于从始点开 始到该节点的最长路线的时间。计算公式：
11、TE1=0TEj= maxTEi+Di-j 节点的最迟时间TL：节点i的最迟时间TLj是以j节点 结束的各项工序最迟必须结束的，否则就会延误整 个工期。它等于总周期减去该节点到终点的最长路 线的时间。计算公式：TLn= TEnTLi= minTLj-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)03666 1114111820039961414161820工作的六个
12、时间参数ES i-j(Earliest Starting Time) EF i-j(Earliest Finishing Time) LS i-j(Latest Starting Time)LF i-j(Latest Finishing Time) TF i-j(Total Float Time) FF i-j(Free Float Time)2.3 工作时间参数计算关系式最早时间参数ES i-j 和EF i-j最早开始时间等于其所有的紧前工作最早结束时间中的最大值：ES i-j =max EF h-i=max ES h-i +D h-i 最早结束时间是它的最早开始时间加上该工作的持续时间之和
13、：EF i-j= ES i-j +D i-j1 12 23 34 45 56 610105 54 45 5101010101010ES1-2=0EF1-2=ES1-2+D1-2=0+10=10ES1-3=0EF1-3=ES1-3+D1-3=0+5=5ES3-5=maxEF1-3=5EF3-5=ES3-5+D3-5=5+4=9ES2-5=maxEF1-2=10EF2-5=ES2-5+D2-5=10+5=15ES2-4=maxEF1-2=10EF2-4=ES2-4+D2-4=10+10=20ES4-5=maxEF2-4=20EF4-5=ES4-5+D4-5=20+10=30ES5-6=maxEF3
14、-5,EF2-5,EF4-5=max9,15,30=30EF5-6=ES5-6+D5-6=30+10=40最迟时间参数LS i-j和LF i-j最迟结束时间等于其所有紧后工作的最迟开始时间中的最小值：LF i-j =min LS j-k=min LF j-k D j-k 最迟开始时间是它的最迟结束时间减去该工作的持续时间之差：LS i-j = LF i-j D i-j1 12 23 34 45 56 610105 54 45 5101010101010LS5-6=LF5-6-D5-6=40-10=30LF5-6= 40LS3-5=LF3-5-D3-5=30-4=26LF3-5=minLS5-6
15、=30LS2-5=LF2-5-D2-5=30-5=25LF2-5=minLS5-6=30LS4-5=LF4-5-D4-5=30-10=20LF4-5=minLS5-6=30LS2-4=LF2-4-D2-4=20-10=10LF2-4=minLS4-5=20LS1-3=LF1-3-D1-3=26-5=21LF1-3=minLS3-5=26LS1-2=LF1-2-D1-2=10-10=0LF1-2=minLS2-5,LS2-4=min25,10=10总时差TF i-j在不影响工期的前提下，工作所具有的机动时 间：若干项工作 共同拥有的 机动时间。自由时差FF i-j 在不影响其紧后工作最早开始的前
16、提下，工作所具有的机动时间：某项工作单独拥有的机动时间，其大小不受其它工作机动时间的影响关键路线是由总时差为0的工序所组成的路线。关键路线上的各工序开始时间和结束时间没有一 点机动的余地。网络图制成以后，把时差为0的工序连接起来得到的一条路线就是关键路线。关键路线的特点：(1) 关键路线上的工序，时差等于0。(2) 关键路线是从网络计划开始点到结束点之间持续时间最长的路线。(3) 关键路线在网络计划中不一定只有一条，有时存在两条以上。 第3节 网络计划的优化绘制网络图、计算时间参数和确定关键路线得到的 只是一个初始的计划方案。为了得到一个较(最)好的方案通常还需要从工期、费用、资源利用等方面对初始 计划方案进行调整和改善，这一过程就是网络计划的 优化。资源 优化成本 优化工期 优化网络计 划优化3.1 工期优化若网络计划图的计算工期大于要求的工期，必须
