管科大二上学期课件-运筹学or-chap

第九章网络计划

网络计划技术概论网络图网络时间与关键路径网络优化用网络分析的方法编制的计划称为网络计划第九章网络计划1.网络计划技术概论1.1网络计划的起源和发展1917年，亨利·甘特发明了著名的甘特图GanttChart（也称横道图），使项目经理按日历制作任务图表，用于日常工作安排1956年，美国杜邦公司将关键路径法（CPM）应用于设备维修，使维修停工时间由125小时锐减为7小时

1958年，美国海军特种计划局在北极星导弹设计中，应用计划评审技术（PERT），将项目任务之间的关系模型化，使设计完成时间缩短了2年

1962年美国国防部规定：以后承包有关工程的单位都应采用网络计划技术来安排计划1.1网络计划的起源和发展60年代初，我国著名数学家华罗庚教授将此技术介绍到中国，并把它称为“统筹法”国内外应用网络计划的实践表明，它具有一系列优点

特别适用于生产技术复杂，工作项目繁多、且联系紧密的一些跨部门的工作计划新产品研制开发、大型工程项目、生产技术准备、设备大修等计划、资源安排、工作流程以下主要介绍CPM。编制网络计划包括绘制网络图，计算时间参数，确定关键路线及网络优化等环节1.2网络计划与横道计划的比较简单、清晰、形象、易懂、使用方便；施工过程施工进度（天）2468101214161820支模10人绑钢筋15人浇混凝土10人优点：可以直接在图中进行各项资源需要量统计。102510劳动力动态消耗图1.2网络计划与横道计划的比较不能直接反映各施工过程之间相互联系、相互制约的逻辑关系不能明确指出那些工作是关键工作，那些工作不是关键工作不能计算各工作的时间参数，看不到计划的潜力不能应用计算机进行调整和优化缺点：1.2网络计划与横道计划的比较1213456支模1绑钢筋1浇混凝土1446支模2绑钢筋2浇混凝土2426施工过程施工进度（天）2468101214161820支模10人绑钢筋15人浇混凝土10人1.2网络计划与横道计划的比较1213456支模1绑钢筋1浇混凝土1446支模2绑钢筋2浇混凝土2426能全面而明确地反映各施工过程之间相互联系、相互制约的逻辑关系；通过时间参数的计算，能够找出关键施工过程和关键线路，便于管理者抓住主要矛盾；通过时间参数的计算，可以对网络计划进行调整和优化；优点：第九章网络计划2.网络图2.1网络图的构成网络图是由作业、事项（节点）和路线三大部分组成作业（工作、工序、活动），箭线表示，一般箭线之上表示工作名称，之下表示工作时间作业一般分为两种：消耗一定的时间与资源的工作――实工作，用实箭线表示既不消耗时间也不消耗资源的工作――虚工作，虚设的工作，只表示前后工作之间的逻辑关系，用虚箭线表示“双代号表示法”2.1网络图的构成

事项，节点表示，表示前面工作结束和后面工作开始的时间点，表示工作结束和开始的瞬间，既不消耗时间也不消耗资源1213456支模1绑钢筋1浇混凝土1446支模2绑钢筋2浇混凝土2426起始节点终点节点中间节点2.1网络图的构成1213456支模1绑钢筋1浇混凝土1446支模2绑钢筋2浇混凝土2426节点的编号:从左到右，由小到大；箭尾编号小于箭头编号,即i＜j

；编码可以不连续，但不可以重复。2.1网络图的构成

路线，网络图中，从起始节点开始，沿箭线方向连续通过一系列节点和箭线，最后到达终点节点的若干条通道，称为路线124AC5B2D4E5G3F56351①→②→④→⑥（8天）①→②→③→④→⑥（10天）①→②→③→⑤→⑥（9天）①→③→④→⑥（14天）①→③→⑤→⑥（13天）第四条线路耗时最长（14天），对整个工程的完工起着决定性的作用，称为关键线路；其余线路均称为非关键线路。处于关键线路上的各项工作称为关键工作。关键工作完成的快慢将直接影响整个计划工期的实现。关键线路上的箭线常采用粗线、双线或其它颜色的箭线突出表示。

位于非关键线路上的工作除关键工作外，都称为非关键工作，它们都有机动时间(即时差)；非关键工作也不是一成不变的，它可以转化成关键工作；利用非关键工作的机动时间可以科学地、合理地调配资源和对网络计划进行优化。

2.1网络图的构成2.2画网络图的规则网络图只能一个开始节点，一个终止节点网络图应从左向右延伸，编号应从小到大，且不重复。箭头事项编号大于箭尾事项编号不能出现循环路线（即不允许有回路）2365412.2画网络图的规则两事项间只能有一项作业改为箭线的首尾都必须有节点131211配砂造型14131211造型配砂2配砂1网络图要布局规整、条理清晰、重点突出。绘制网络图时，应尽量采用水平箭线和垂直箭线而形成网格结构，尽量减少斜箭线，使网络图规整、清晰。其次，应尽量把关键工作和关键线路布置在中心位置，尽可能把密切相连的工作安排在一起，以突出重点，便于使用。2.2画网络图的规则1234EBDACF（a）有交叉和斜向箭线的网络图1234EFDCAB（b）调整后的网络图ABABCABCABCACB序号工作之间的逻辑关系网络图中的表示方法说明1A工作完成后进行B工作A工作制约着B工作的开始，B工作依赖着A工作2A、B、C三项工作同时开始

A、B、C三项工作称为平行工作3A、B、C三项工作同时结束A、B、C三项工作称为平行工作4有A、B、C三项工作。只有A完成后，B、C才能开始A工作制约着B、C工作的开始，B、C为平行工作5有A、B、C三项工作。C工作只有在A、B完成后才能开始C工作依赖着A、B工作，A、B为平行工作BACDACBDiDA1B1A2A3B2B3ADBCE6有A、B、C、D四项工作。只有当A、B完成后，C、D才能开始通过中间节点i正确地表达了A、B、C、D工作之间的关系7有A、B、C、D四项工作。A完成后C才能开始，A、B完成后D才能开始D与A之间引人了逻辑连接（虚工作），从而正确地表达了它们之间的制约关系8有A、B、C、D、E五项工作。A、B完成后C才能开始，B、D完成后E才能开始虚工作i-j反映出C工作受到B工作的制约；虚工作i-k反映出E工作受到B工作的制约9有A、B、C、D、E五项工作。A、B、C完成后D才能开始，B、C完成后E才能开始虚工作反映出D工作受到B、C工作的制约10A、B两项工作分三个施工段，平行施工每个工种工程建立专业工作队，在每个施工段上进行流水作业，虚工作表达了工种间的工作面关系ACBE

i

j

k2.3网络图的绘制实例任务分解(WorkBreakdownStructure,WBS)绘制网络图节点编号作业分析表试探性绘制法：试探试探性绘制法：修改流程图过渡绘制法：流程图流程图过渡绘制法：加事项流程图过渡绘制法：去方框流程图过渡绘制法：修改2.4练习某新产品研制项目的各项序动、所需时间及相互关系如下表。工序工序代号所需时间紧后工序产品及工艺设计a60b,c,d,e外购配套件b45l下料、锻件c10f工装制造1d20g,h木模、铸件e40h机械加工1f18l工装制造2g30i机械加工2h15l机械加工3i25l机械加工4l25j装配调试j3512345678a60d20g30i25l25b45f18e40h15c109j352.4练习第九章网络计划3.网络时间与关键路径3.1时间参数计算网络图绘制，只是用网络的形式表达出了工作之间的逻辑关系。还必须通过计算求出工期，得到一定的时间参数计算网络图中有关的时间参数，主要目的是找出关键路线，为网络计划的优化、调整和执行提供明确的时间概念时间参数：工序所需时间、事项最早、最迟的时间、工序的最早、最迟时间及时差完成工序所需时间确定，只给出一个时间值CPM在影响工序因素较多，作业时间难以准确估计时，采用三点时间PERTa—最快可能完成时间m—最可能完成时间b—最慢可能完成时间3.2工序时间的确定确定型概率型3.3事项的时间参数-最早事项（节点）的最早时间——tE(j)表示以j为始点的各工序最早可能开始的时间，也表示以j为终点的各工序均完成的最早可能时间起始节点的最早开始时间为0，即tE(1)=0

tE(j)=max{tE(i)+t(i,j)}i,j

分别代表箭尾和箭头事件从起始节点开始,正向计算i3.3事项的时间参数-最迟事项（节点）最迟时间——tL(i)表示在不影响任务总工期的条件下，以i为始点的各工序最迟必须开始时间，或以i为终点的各工作的最迟必须完成时间一般将任务的最早完工时间作为任务的总工期

tL(n)=tE(n)

n为终点事项

tL(i)=min{tL(j)–t(i,j)}i,j

分别代表箭尾和箭头事件从终点节点开始,反向计算，即从编号大到小顺序j3.3事项的时间参数-例题计算各事项的最早时间和最迟时间。3.3事项的时间参数-例题时间参数的图上计算法3.4工序的时间参数-最早工序的最早可能开工时间——tES(i,j)任何一个工序都必须在其所有紧前工序全部完成后才能开始工序的最早可能完工时间——tEF(i,j)表示工作按最早开工时间开始所能达到的完工时间tES(1,j)=0tES(i,j)=max{tES(k,i)+t(k,i)}tEF(i,j)=tES(i,j)+t(i,j)tES(i,j)=tE(i)EarlyFinishEarlyStarttEF(i,j)=tE(i)+

t(i,j)k3.4工序的时间参数-最迟工序的最迟必须开工时间——tLS(i,j)表示工序(i,j)在不影响整个任务如期完成的前提下，必须开始的最晚时间工序的最迟必须完工时间——tLF(i,j)表示工作(i,j)按最迟时间开工，所达到的完工时间tLF(i,n)=tL(n)=tE(n)tLS(i,j)=min{tLS(j,k)-t(i,j)}tLF(i,j)=tLS(i,j)+t(i,j)tLF(i,j)=tL(j)LateFinishLateStarttLS(i,j)=tL(i)

-

t(i,j)k作业时间和事项时间的关系ijETESEFETLTLTLFLStij+tij=－

tij=工序的时差或工序的机动时间工序总时差R(i,j)，在不影响总工期的情况下，最早开始（或结束）时间可以推迟的时间R(i,j)=tLF(i,j)-tEF(i,j)=tLS(i,j)-tES(i,j)总时差为0的作业是关键作业，开始和结束的时间没有一点机动的余地由关键作业构成的路线是关键路线，它是时间最长的路线3.5时差-总时差3.5时差-单时差工序单时差——r(i,j)

表示不影响紧后工序最早开始时间的条件下，工序最早结束时间可以推迟的时间

r(i,j)=tES(j,k)–tEF(i,j)

tES(j,k)为工序(i,j)的紧后工序的最早开始时间单时差为0，总时差不一定为0总时差为0，单时差一定为03.5时差-总时差与单时差的关系计算各作业的最早时间、最迟时间和时差。3.6例题13.6例题1时间参数的表上计算法143568927B62IHDGECA22KLJ741034343.6例题2

143568927025261519120202256102915190228151221226212500221212151521919111187612615811746151115711B62IHDGECA22KLJ741034343.6例题23.7概率型网络图的时间参数总完工期（期望工期）——关键路线上各工序的平均工时之和总完工期的方差——关键路线上各工序的方差之和3.7概率型网络图的时间参数

为达到严格控制工期，确保任务在计划期内完成的目的，我们可以计算在某一给定期限Ts前完工的概率。

一般可指定多个完工期Ts，直到求得有足够可靠性保证的计划工期Ts*，将其作为总工期。标准正态分布3.7概率型网络图的时间参数—举例

例：已知某一计划中各件工作的a,m,b值（单位：月）。要求：（1）每件工作的平均工时

t和均方差σ；（2）画出网络图，确定关键路线；（3）在25个月前完工的概率。工作ambt①→②78980.333①→③5786.8330.5②→⑥691291③→④44440③→⑤78108.1670.5③→⑥10131913.51.5④→⑤3464.1670.5⑤→⑥4575.1670.5⑤→⑦791190.667⑥→⑦3484.50.8333.7概率型网络图的时间参数—举例按

t值计算出各工作的最早开工时间tES和最迟开工时间

tLS，以及总时差

R。工作tEStLSR①→②03.3333.333①→③000②→⑥811.3333.333③→④6.8336.9990.166③→⑤6.8336.9990.166③→⑥6.8336.8330④→⑤10.83310.9990.166⑤→⑥1515.1660.166⑤→⑦1515.8330.833⑥→⑦20.33320.3330√√√关键路线：①→③→⑥→⑦

总完工期：24.8333.7概率型网络图的时间参数—举例在25个月前完工的概率为：注1：计算某一事项i在指定日期Ts(i)前完成的概率具有较小概率的事项应特别注意，凡是以它为完工时间的工作均应加快进度。注2：还应注意那些从始点到终点完工日期与总工期相近的次关键路线，计算它们按总工期完工的概率，实施计划时对其中完工概率较小的一些路线从严控制进度。第九章网络计划4.网络优化网络计划优化工期优化费用优化资源优化4.1工期限定，资源需要平衡该作业每天所需劳动力该作业时间4.1工期限定，资源需要平衡关键路线作业总时差作业时间各工作都按最早开始时间开始工期不变，就是关键工作时间不能调整，即不调整关键路线上的作业资源不平衡将导致资源不足利用时差，调整非关键路线上工作的开始时间，使资源实现平衡4.1工期限定，资源需要平衡4.1工期限定，资源需要平衡4.1工期限定，资源需要平衡4.2资源有限，要求工期最短某工程按作业最早开工期安排的日程网络图如下：若每天最多只有10人工作，试问如何安排才能使总工期最短？4.2资源有限，要求工期最短调整方案一4.2资源有限，要求工期最短调整方案二4.3费用优化工程项目的成本费用是和时间进度有关的。投入的资源愈多，作业时间也愈短反之，成本费用可能低些，但作业时间会加长综合考虑费用优化主要有以下两个方面：工程周期给定，如何安排各项作业，使整个工程的直接费用降低如果有一笔准备用来加快工程进度的追加费用，如何安排才能使工程总周期缩短最多。或者说，如果要求工程缩短一定时间，如何安排才能使追加的费用最小4.3费用优化工期