55运筹学网络计划

第九章网络计划目录前言第1节网络计划图第2节网络计划图的时间参数计算第3节网络计划的优化前言•用网络分析的方法编制的计划称为网络计划。它是二十世纪五十年代末发展起来的一种编制大型工程进度计划的有效方法。1956年，美国杜邦公司在制定企业不同业务部门的系统规划时，制定了第一套网络计划。这种计划借助于网络表示各项工作与所需要的时间，以及各项工作的相互关系。网络计划方法的基本原理将工程项目分解为相对独立的活动，根据各活动先后顺序、相互关系以及完成所需时间做出反映项目全貌的网络图；从项目完成全过程着眼，找出影响项目进度的关键活动和关键路线，通过对资源的优化调度，实现对项目实施的有效控制和管理。网络计划方法的主要功能1用网络图描述一个实际项目的管理问题(画网络图);2计算项目的最早、最晚完成和开工时间(网络计算);3寻找关键活动和关键路径(网络分析);4根据以上分析对网络进行优化。第1节网络计划图•网络计划图的基本思想是：•首先应用网络计划图来表示工程项目中计划要完成的各项工作，完成各项工作必然存在先后顺序及其相互依赖的逻辑关系；这些关系用节点、箭线来构成网络图。•网络图是由左向右绘制，表示工作进程。并标注工作名称、代号和工作持续时间等必要信息。•通过对网络计划图进行时间参数的计算，找出计划中的关键工作和关键线路；•通过不断改进网络计划，寻求最优方案，以求在计划执行过程中对计划进行有效的控制与监督，保证合理地使用人力物力和财力，以最小的消耗取得最大的经济效果。1.1基本术语网络计划图是在网络图上标注时标和时间参数的进度计划图，实质上是有时序的有向赋权图。表述关键路线法（CPM）和计划评审技术（PERT）的网络计划图没有本质的区别，它们的结构和术语是一样的。仅前者的时间参数是确定型的，而后者的时间参数是不确定型的。于是统一给出一套专用的术语和符号。描述工程项目网络计划图有两种表达的方式：双代号网络计划图和单代号网络计划图。双代号网络计划图在计算时间参数时，又可分为：工作计算法和节点计算法。基本术语：⑴节点,（2）工作•⑴节点，箭线是网络计划图的基本组成元素。箭线是一线段带箭头实射线,虚射线（用“→”,“”表示）。节点用“○”或“□”表示箭线之间的连接点。•⑵工作（曾称工序、活动、作业）将整个项目按需要粗细程度分解成若干需要耗费时间或需要耗费其他资源的子项目或单元。它们是网络计划图的基本组成部分。(3)双代号网络计划图•在双代号网络计划图中，用箭线表示工作，箭尾的节点表示工作的开始点，箭头的节点表示工作的完成点。用（i-j）两个代号及箭线表示一项工作。在箭线上标记必须的信息，如表示图9-1为：ji持续时间工作名称或代号(4)单代号网络计划图用节点表示工作，箭线表示工作之间的先完成与后完成的关系为逻辑关系。在节点中标记必须的信息，如图9-2所示：以下主要介绍双代号网络计划图工作代号工作名称持续时间工作代号工作名称持续时间1.2双代号网络计划图•以下通过例题来说明双代号网络计划图的绘制和按工作计算时间参数的方法。•例1．开发一个新产品，需要完成的工作和先后关系，各项工作需要的时间汇总在逻辑关系表中，见表9-1。要求编制这项目的网络计划图和计算有关参数。表9-1序号工作名称工作代号工作持续时间（天）紧后工作1产品和工艺设计A60B,C,D,E2外购配套件B45L3锻件准备C10F4工装制造1D20G,H5铸件E40H6机械加工1F18L7工装制造2G30K8机械加工2H15L9机械加工3K25L10装配与调试L35/第1步•根据表9-1中数据，绘制以下网络图，见图9-3。图9-312346758设计A60工装制造1D20工装制造2G30加工3K25装配L35铸件E40加工2H15外购配套件B加工1F1845锻件C10虚工作E'为了正确表述工程项目中各个工作的相互连接关系和正确绘制网络计划图，应遵循以下规则和了解有关术语:1.网络计划图的方向、时序和节点编号•网络计划图是有向、有序的赋权图，按项目的工作流程自左向右地绘制。在时序上反映完成各项工作的先后顺序。节点编号必须按箭尾节点的编号小于箭头节点的编号来标记。在网络图中只能有一个起始节点，表示工程项目的开始。一个终点节点，表示工程项目的完成。从起始节点开始沿箭线方向顺序自左往右，通过一系列箭线和节点，最后到达终点节点的通路，称为线路。2.紧前工作和紧后工作•紧前工作是指紧排在本工作之前的工作；完成后，才能开始本工作。紧后工作是指紧排在本工作之后的工作；本工作结束后，才能开始的工作。如图9-3中，只有工作A完成后工作B,C,D,E才能开始，工作A是B,C,D,E的紧前工作；而工作B,C,D,E则是工作A的紧后工作。12346758设计A60工装制造1D20工装制造2G30加工3K25装配L35铸件E40加工2H15外购配套件B加工1F1845锻件C10虚工作E'•在复杂的工程项目中，它们之间的有三种关系：结束后，才开始（FS）；开始后，才开始(SS)；结束后，才结束(FF)。本例只涉及结束后，才开始(FS)的关系。从起始节点至本工作之前在同一线路的所有工作，称为先行工作；自本工作到终点节点在同一线路的所有工作，称为后继工作。工作G的先行工作有工作A,D;工作K,L是工作G的后继工作。3.虚工作•在双代号网络计划图中，虚工作只表示相邻工作之间的逻辑关系，不占用时间和不消耗人力，资金等的虚设的工作。虚工作用虚箭线表示。•如图9-3中的④⑤只表示工作D完成后，工作H才能开始的逻辑关系。4.相邻两节点之间只能有一条箭线连接。否则将造成逻辑上的混乱。•如图9-4是错误画法，为了使两节点之间只有一条箭线，可增加一个节点②’，并增加一项虚工作②′②。图9-5是正确的画法图9-4图9-5应改正为5.网络计划图中不能有缺口和回路。•在网络计划图中严禁出现从一个节点出发，顺箭线方向又回到原出发节点，形成回路。回路将表示这工作永远不能完成。网络计划图中出现缺口，表示这些工作永远达不到终点。项目无法完成。6.平行作业和交叉作业。•（1）平行作业•为缩短工程的完工时间，在工艺流程和生产组织条件允许的情况下，某些工序可以同时进行，即可采用平行作业的方式。如在图9—1中，工序B、C、D、E四个工序即可平行作业。•在有几个工序平行作业结束后转入下一道工序的情况下，考虑到便于计算网络时间和确定关键路线，选择在平行作业的几个工序中所需时间最长的一个工序，直接与其紧后工序衔接，而其它工序则通过虚工序与其紧后工序衔接。虚工作可以用于正确地表示平行工作。如图中市场调查（2，3）中需12天，如增加人力分为三组同时进行，可画为（b）。143212（市场调研）图（a）4123456（调2）44（调1）（调3）图（b）•(2)交叉作业•对需要较长时间才能完成的一些工序，在工艺流程与生产组织条件允许的情况下，可以不必等待工序全部结束后再转入其紧后工序，而是分期分批的转入。这种方式称为交叉作业。交叉作业可以缩短工程周期。如在图9－1中，将工装制造分为两批，将一个工序分为两个工序D、G，分别与紧后工序H、K连接。如工作A与工作B分别为挖沟和埋管子，那么它们的关系可以是挖一段埋一段，不必等沟全部挖好再埋，这就可以用交叉作业来表示。如把这工作各分为三段，A=a1+a2+a3,B=b1+b2+b3，可用下图表示：1234567a1a2a3b1b2b3为了尽量避免弧的交叉，下图（a）整体改为（b）就比较清晰了。1234567891011121314图（a）1234567891011121314图（b）7.起始节点与终点节点。•在网络计划图中只能有一个起始节点和一个终点节点。当工程开始或完成时存在几个平行工作时，可以用虚工作将它们与起始节点或终点节点连接起来。12s下图，有2个始点，3个终点，显然是错误的。123456782433121123465782403130201图9-312346758设计A60工装制造1D20工装制造2G30加工3K25装配L35铸件E40加工2H15外购配套件B加工1F1845锻件C10虚工作E'8.线路：•网络图中从起点节点沿箭线方向顺序通过一系列箭线与节点，最后到达终点节点的通路。本例中有五条线路。并可以计算出各线路的持续时间，见表9-2。线路线路的组成各工作的持续时间之和（天）1①→②→⑦→⑧60＋45＋35=1402①→②→③→⑦→⑧60＋10＋18＋35=1233①→②→④→⑥→⑦→⑧60＋20＋30＋25＋35=1704①→②→④→⑤→⑦→⑧60＋20＋15＋35=1305①→②→⑤→⑦→⑧60＋40＋15＋35=150关键路线•从网络图中可以计算出各线路的持续时间。其中有一条线路的持续时间最长线路是关键路线。或称为主要矛盾线。关键路线上的各工作为关键工作。因为它的持续时间就决定了整个项目的工期。如果能够缩短关键工序所需的时间，就可以缩短工程的完工时间。•而缩短非关键路线上的各个工序所需要的时间，却不能使工程的完工时间提前。即使在一定范围内适当地拖长非关键路线上各个工序所需要的时间，也不至于影响工程的完工时间。关键路线356124543223312124612105613856T=12(周)•而对非关键路线上的各工序，只要在不影响工程完工时间的条件下，抽出适当的人力、物力等资源，用在关键工序上，以达到缩短工程工期，合理利用资源等目的。在执行计划过程中，可以明确工作重点，对各关键工序加以有效控制和调度。•关键路线是相对的，也是可以变化的。在采取一定的技术组织措施之后，关键路线有可能变为非关键路线。而非关键路线也有可能变为关键路线。9.网络计划图的布局。•尽可能将关键路线布置在网络计划图的中心位置，按工作的先后顺序将联系紧密的工作布置在邻近的位置。为了便于在网络计划图上标注时间等数据，箭线应是水平线或具有一段水平线的折线。在网络计划图上附有时间坐标或日历进程。10.网络计划图的类型。•①总网络计划图，以整个项目为计划对象，编制网络计划图。供决策领导层使用；•②分级网络计划图，这是按不同管理层次的需要，编制的范围大小不同，详细程度不同的网络计划图；供不同管理部门使用；•③局部网络计划图，将整个项目某部分为对象，编制的更详细的网络计划图。供专业部门使用。•当用计算机网络计划软件编制网络计划时，在计算机上可进行网络计划图分解与合并。网络计划图详细程度，可以根据需要，将工作分解为更细的子工作；也可以将几项工作合并为综合的工作。以便显示不同粗细程度的网络计划。当前的软件都实现这些操作。例2某调研工作工序如下表：工序内容工时(天)紧前工序A初步研究1/B研究选点2AC准备调研方案4AD联系调研点2BE培训工作人员3B,CF准备表格1CG实地调研5D,E,FH写调研报告2GI开会汇总3H12325132004CFEDBAGHI123456789第2节网络计划图的时间参数计算•网络计划的时间参数计算有几种类型：双代号网络计划有工作计算法和节点计算法；单代号网络计划有节点计算法。以下仅介绍工作计算法。网络图中工作的时间参数。它们是：•工作持续时间(D)；•工作最早开始时间（ES）；•工作最早完成时间（EF）；EF=ES+D•工作最迟开始时间（LS）；LS=LF-D•工作最迟完成时间（LF）；•工作总时差（TF）；TF=LS-ES=lf-d-es==LF-EF•工作自由时差（FF）。12346758设计A60工装制造1D20工装制造2G30加工3K25装配L35铸件E40加工2H15外购配套件B加工1F1845锻件C10ESLSEFLF标记：0060606060170170135135135135110110110110808080801351351006060706013512011710010588115107809011712070TFFF0030304704747000000002001820图9-720⑵工作自由时差FF是指：在不影响其紧后工作最早开始的前提下，工作所具有机动时间:FFi-j=ESj-k－ESi-j－D