运筹学基础-网络计划(2012修正)

1、第七章第七章 计划评审方法和关键线路法计划评审方法和关键线路法（Program Evaluation and Review Technique，PERT)是一种组织生产和进行计划管理的科学方法，也称统筹法。它是综合运用和的一种较为先进和计划管理方法。（Critical path method,简写CPM)是对计划项目进行核算、评价，然后选定最优计划方案的一种技术。是在计划项目的各项错综复杂的工作中，抓住其中的关键路线进行计划安排的一种方法。第一节第一节 PERT网络图及其绘制规则网络图及其绘制规则 网络图又叫箭头图或统筹图，它是计划项目的各个组成部分内在逻辑关系的综合反映，是进行计划和计算的基

2、础，即网络计划技术的基础是网络图。 以(活动)，以。需要引进虚作业(以虚线表示)，其特点是布图明朗，应用广泛。 以(活动)，以。不需要引进虚作业，但其特点是线条纵横交错，不一目了然，应用不广泛。箭线式网络图例箭线式网络图例135791113151719212325272931ABDEFGHCIJKLMNOPQ 结点（事件）式网络图例结点（事件）式网络图例始始BACDEFGHIJKMNOLPQx箭线式网络图是由、和三个部分组成。 指任何消耗人力、物力或时间等资源的相对独立的作业过程，又称或。 在网络图中用箭线“” 表示，从箭尾到箭头表示一项作业的开始到终结的过程。 在箭线的左（上）侧写上作业的名

3、称，右（下）侧写上该作业所占用的时间。 与某项作业前面直接相连的作业称为，其后直接相连的后继作业为。 虚作业是为了表达相邻工序之间的逻辑关系而虚设的作业。不消耗时间、费用和资源，一般用虚箭线表示。026机器解体82天机器部分维修总装试车5天1天事件（也叫结点），是相邻作业的分界点，标志着作业的开始或结束。 一般用圆圈“”来表示，每个结点编上顺序号；箭尾结点表示作业的开始，箭头结点表示作业的完成。结点既不消耗人力、物力，也不占用时间。 一项规划只有一个总开始结点称为最初结点，和一个总结束结点称为最终结点。 处在网络中间的结点具有两重性，对前面的作业它是终点、对后面的作业它是始点1539b711a

4、chijkefd 线路是指从开始，顺着箭线的方向，由各项作业连贯组成的，到达的一条路。从最初事件到最终事件可以有不同的路。1539b711achijkefd563765(6)5) 13115730908630(4) 131179(3) 1311753010(2) 171166125(1) 1511712关键路线关键路线在所有的线路中，的线路就是。或叫主要矛盾线。关键线路决定整个网络计划的完工时间。，也可由所有各条线路的路长中最长的一条线路所决定。 网络分析的主要任务是找出工程中的，因为它决定着完工期。如果这条线路上工作进度有耽误，则整个工程的工期就要向后推迟；相反，如

5、果能采取积极措施缩短这条线路的完工时间，工期就可能提前。1539b711achijkefd563765三、绘制网络图的规则和注意事项三、绘制网络图的规则和注意事项网络图是有方向的，工序应按工艺流程顺序或工作的逻辑关系从左向右排列。 一条箭线和它的相关结点只能代表一项作业，不能代表多项作业两个结点之间只能有一条箭线相连正确的画法正确的画法13可引入虚作业。132不正确的画法不正确的画法虚作业是为了表达相邻作业之间的逻辑关系而虚设的作业。 它不消耗时间、费用和资源，一般用虚箭线表示。虚作业的引进原因虚作业的引进原因(1)(1)两个事件之间的工作过程只能代表一项作业，当两个或两个以上的作业具有同一个

6、始点和终点时，需要引入虚作业，予以区别。026机器解体82天机器部分维修总装试车5天3天4电器部分维修 虚作业3天虚作业的引进原因(2) 是为了正确表示各个作业之间的先后承接关系，有时必须引入虚作业。如一个工程各个作业之间的先后关系如表：活动名称紧接的前项活动abcdef无无无a,ba,ca,b,c1539b711achijkefd 作业a结束后可以开始b和cabc 作业c在a和b均结束后才能开始abc a、b两项均结束后可以开始c和dacdb c在a结束后即可进行、d必须在a、b两项均结束后才能开始。acdb编号应从始事件开始，按照时序依次从小到大对事件编号，直到终事件。 编号时不允许箭头编

7、号小于箭尾编号。事件的编号原则箭尾事件(i)小于箭头事件(j)；一般采用非连续编号，即可空留出几个号，跳着编，将来有变化时，不致打乱全局。132132网络图中只能有一个始点和一个终点，使得自网络图的始点经由任何路径都可以到达终点。1234569781011为了方便计算和美观清晰，PERT网络图中通过调整布局，尽量避免箭线之间的交叉。调整前1234569781011调整后四、箭线式网络图的绘制 就是把一个计划项目的总任务分解成一定数量的分任务，并确定它们之间的先后承接关系 工作的性质不同或由不同单位执行的工作应分开； 同一单位进行的工作，时间先后不衔接的要分开；如产品设计与工装设计，铸造、锻、机

8、械加工、装配要分开如技术设计与工作图设计，材料采购与外协件采购要分开 占用时间不消耗资源，但影响工程完工日期的工作应作为分任务；如油漆后的干燥，热处理后的冷却，方案的审批等 编制计划要熟悉业务，了解工程项目的各个组成部分，深入调查。例：下表是某一工程的作业明细表例：下表是某一工程的作业明细表 任务经过分解以后，可以列出作业明细表。作业紧接的前项作业作业时间(周)ABCDEFGHIJ无无A，BBACE，FD，FG，HI2341532765某一工程的作业时细表某一工程的作业时细表作业紧接的前项作业 作业时间(周)ABCDEFGHIJ无无A，BBACE，FD，FG，HI2341532765 在A后面

9、，画出紧前作业为A的作业E；在B后面，画出紧前作业为B的作业D；给新增的事件编号为、，在A与B后面，画出紧前作业为A、B的作业C；画作业C时要引进虚作业，为新增的事件编号为。 将F画在紧前作业C之后；为新增的事件编号为。 将G画在紧前作业E、F之后；将H画在紧前作业D、F之后，引入虚作业 以此类推，最后得出网络图某工程的网络图某工程的网络图 1AB3ED5C79F13GH1511I1719J21作业紧接的前项作业作业时间(周)ABCDEFGHIJ无无A，BBACE，FD，FG，HI2341532765作业名称紧接的前项作业abcdef无无无a,ba,ca,b,cf1357911abcde作业名

10、称ABCDEF紧前作业无无无ABB、C作业名称ABCDEF紧前作业无无A、BBCDF175311ACDE作业名称ABCDEF紧前作业无无无ABB、CBF15311ACDB作业名称ABCDEF紧前作业无无A、BBCD7E9第二节第二节 网络时间的计算网络时间的计算 网络时间的计算有三种计算方法：、和。图上计算法要用的有关符号在长方形符号中标以作业最早开始时间值，该符号放在箭线的上方，靠近前事件i的右上角。在三角形符号中标以作业最迟完成时间值，该符号放在箭线的好方，靠近后事件j的左好角。ESi,j101379LFi,j（一）作业时间（一）作业时间 作业时间就是在一定的生产技术条件下，完成一项作业或

11、一道工序所需的时间，符号Ti,j就是表示ij这项作业的作业时间。最乐观时间：在最理想的情况下完成工序所需时间a；最悲观时间：在最不利的情况下完成工序所需时间b；最可能时间：在正常情况下完成工序所需时间m。加权平均就是工序时间t64j , iEbmat工序时间期望时间 (1)单一时间估计法：就是在估计各项作业的时间时，只确定一个时间值。 (2)三种时间估计法：就是在估计各项作业的作业时间时，先估计出三个时间值，然后再求出完成该作业的作业时间。22E)6tab （方差例、求作业的期望时间和方差 各项作业的三个估计时间如下表，求各作业的期望时间和方差。作业(i,j)代号估计完成时间（a-m-d)/T

12、(1)1)(2)2)(3)3)(1,2)A3-5-7(1,3)B8-9-16(1,4)C8-11-14(3,4)D2-4-6(2,5)E3-4-5(4,6)F8-16-18(5,6)G18-20-28(5,8)H26-33-52(5,7)I18-25-32(7,8)J12-15-18(6,8)K11-21-25计算：计算：作业(i,j)代号估计完成时间（a-m-b)/T 期望完成时间（d）方差(1,2)A3-5-750.44 (1,3)B8-9-16101.78 (1,4)C8-11-14111.00 (3,4)D2-4-640.44 (2,5)E3-4-540.11 (4,6)F8-16-1

13、8152.78 (5,6)G18-20-28212.78 (5,8)H26-33-523518.78 (5,7)I18-25-32255.44 (7,8)J12-15-18151.00 (6,8)K11-21-25205.44 64j , iEbmat22E)6tab （二）作业时间参数计算（二）作业时间参数计算max0,1ihihjihijjTESESES其值等于从初始点起到本作业的最长路线上各作业时间之和。从最初作业开始，自左向右，顺着箭线方向逐个计算 。截取下面部分讨论截取下面部分讨论 在箭线式网络图中，要计算的作业时间有两个，即作业的、。EF479113551315CDGH作业最早开始

14、时间计算如下：作业最早开始时间计算如下：ES7,9=？EF479113531315CDGHES9,11=？ES11,13=？ES11,15=？ min,jikjkjiijjnTLFLFTLF总 指作业最迟必须完工的时刻，否则将会影响后续作业按时开工，以至推迟整个工程的完工时间。 最终作业的最迟完成时间应等于总完工时间从终点开始，从右向左，逆箭线方向逐个计算。EF479113531315CDGH事件最迟完成时间计算如下：事件最迟完成时间计算如下：LF9,11=？LF7,9=？EF479113531315CDGHLF3,7=？LF5,7=？作业时间的完整计算 作业的是的方向，逐个计算； 作业的是的

15、方向，逐个计算；00CF4300AB23 1I6GH2J57E5D1 3 5 7 9 111315171921（三）时差与关键路线（三）时差与关键路线 一个工作或一个工程有多大时差，就表明了有多大的机动时间可以利用。时差越大，则时间的潜力也越大。即可以将工作的资源暂时调出去支援关键性线路。计算和利用时差是网络分析中一个重要问题，它为计划进度的安排提供了可供选择和协调的可能性，也是确定关键线路的依据。又称机动时间或宽裕时间，是指在不影响如期完成任务的条件下，各道工序可以机动使用的一段时间。1、作业时差、作业时差在不影响工程最早结束时间的条件下，工序最早开始时间最早开始时间可以推迟的时间，称为该工

16、序的总时差。(即工序的完工期可以推迟的时间)即：工序总时差工序总时差 = 最迟完成时间作业时间最早开始时间最迟完成时间作业时间最早开始时间 工序总时差越大，表明该工序在整个网络中的机动时间越大，可以在一定范围内将该工序的人力、物力资源利用到关键工序上去，以达到缩短工程结束时间的目的。 在不影响紧后作业最早开始时间的条件下, 作业最早开工时间可以推迟的时间，称为该工序的单时差。Ri,j= LFi,jTi,jESi,jFi,jmin ESj,kTi,jESi,i=LFi,jTi,jESi,jR3,13=1552800CF4300AB23 1I6GH2J57E5D1 3 5 7 9 11131517

17、1921Fi,j= ESj,k Ti,jESi,jF3,13= ES13,17T3,j3ES3,1310523注：自由时差并不是每个作业有，自由时差的形成是由于作业的始点和终点中，四个时间ESi、LFi 、Esj、LFj 是由不同线路上的作业决定的。 00CF4300AB23 1I6GH2J57E5D1 3 5 7 9 111315171921F5,1510136F7,974303 3、线段时差、线段时差两个关键事件之间的一个作业、或两个关键事件之间的几个作业连续相接的连线，称为线段。、 、 、 )、 、 )= 、 、 R)= 、00CF4300AB23 1I6GH2J57E5D1 3 5 7

18、 9 1113151719214 4、线路时差、线路时差线路是指从始点出发，经过连续相接的作业，直到终点的一条连线。线路1-3-13-17-19-21的线路时差为8线路时差为0的线路，称为。是从始点出发，由各个关键作业连续相接，直到终点的线路。注：关键线路的时差等于注：关键线路的时差等于0，非关键线路时差通常不计算。，非关键线路时差通常不计算。线路1-5-7-9-11-15-17-19-21时差为0，即为关键线路。 00CF4300AB23 1I6GH2J57E5D1 3 5 7 9 111315171921小结：各时间的计算及标注方法小结：各时间的计算及标注方法 tLF(i,j)t(i,j)

19、tES(i,j)ijR(i,j)【例【例1】下表是某一工程的作业明细表】下表是某一工程的作业明细表 序号作业内容紧前作业作业时间(h)123456789型砂准备A造型B砂型烘干C芯砂准备D芯骨浇铸E芯骨装配F造4个1号泥芯G造4个2号泥芯H2号泥芯干燥I无12无无54，64，682444.77.226.244.3某一工程的作业时细表某一工程的作业时细表解（1）画出PERT网络图1324567 2A4.7D7.2E4B4C2F6.2G4H4.3I（2）计算作业时间和时差Ri,j=LFi,jTi,jESi,jFi,j=ESj,k Ti,jESi,iESLF13245672A4.7D7.2E4B4C

20、2F6.2G4H4.3I练习练习 序号序号工作名称工作名称工作代号工作代号工作持续时间工作持续时间紧后工作紧后工作1 1产品设计与工艺设计产品设计与工艺设计A A6060B B、C C、D D、E E2 2外购配件外购配件B B4545L L3 3锻件准备锻件准备C C1010F F4 4工装制造工装制造1 1D D2020G G、H H5 5铸件铸件E E4040H H6 6机械加工机械加工1 1F F1818L L7 7工装制造工装制造2 2G G3030K K8 8机械加工机械加工2 2H H1515L L9 9机械加工机械加工3 3K K2525L L1010装配与调试装配与调试L L

21、35351）画出PERT网络图2）计算作业时间和时差画出画出PERT网络图网络图12467835a60b45 c10d20e40f18g30h15k25l350 12467835a60b45 c10d20e40f18g30h15k25l350ESLFRi,j=LFi,jTi,jESi,jFi,j=ESj,k Ti,jESi,i 二、表格计算形式二、表格计算形式 三、三、EXCEL计算形式计算形式-同图论中最短线路问题同图论中最短线路问题第三节第三节 网络计划的优化网络计划的优化 绘制网络图、计算网络时间和确定关键路线,得到一个初始的计划方案。但通常还要对初始计划方案进行调整和完善。根据计划的要

22、求，综合地考虑进度、资源利用和降低费用等目标，即进行网络优化，确定最优的计划方案。 网络计划的优化包括网络计划的优化包括 改进工艺和技术装备，压缩关键工序的作业时间；合理组织平行作业、交叉作业， 平行作业指两道以上相互独立的工序同时进行， 交叉作业指将紧前工序完成的部分任务分期分批地转入下道工序。利用时差，合理调配资源等途径实现。 优先保证关键路线上关键工序对资源的需求量。向非关键工序要资源，利用时差调整非关键工序的开工时间，以达到与其它工序在占用资源的时间上错开，拉平资源需要量的高峰。在时间进度优化中，重点在于如何缩短工期，工期的缩短与费用是密切相关的。网络计划的优化中，应考虑不同的完工时间

23、所对应的工程费用，找到工程费用最低的完工时间(最低成本日程)。【例【例2】如例】如例1中列出的各项作业必须在中列出的各项作业必须在15小时内结束小时内结束 1324567244.77.2246.244.31.91.6n 表格计算形式表格计算形式 作业(i,j)作业(i,j)作业时间最短时间最大可调整的时间单位时间增加花费用作业开始时间作业缩短时间作业完成时间(1,2)A22000.0 0.0 2 (2,5)B44002.0 0.0 6 (5,7)C44006.0 0.0 10 (1,4)D4.73.51.220.0 0.0 5 (1,3)E7.24.2350.0 0.0 7 (3,4)F211

24、47.2 0.4 9 (4,7)G6.242.22.58.8 0.0 15 (4,6)H41338.8 2.1 11 (6,7)J4.32.81.5610.7 0.0 15 练习：练习：12467835a60b45 c10d20e40f18g30h15k25l350各项作业必须在140小时内结束12467835a60b45 c10d20e40f18g30h15k25l35020151030123456789101112131415161727人 27人 31人 32人 25人 16人 19人 17人 17人 17人 12人 12人 10人6人6人6人6人013256478ABCDHEFGIJK某工程安装工人需要数平衡图（某工程安装工人需要数平衡图（22人）第一方案人）第一方案某工程安装工人需要数平衡图（第二方案）某工程安装工人需要数平衡图（第二方案）123456789101112131415161721人 21人 31人 31人 24人 16人 19人 19人 19人 17人 17人 17人 10人6人6人6人6人013256478ABCDHEFGIJK某工程安装工人需要数平衡图（第三方案）某工程安装工人需要数平衡图（第三方案）12345678910111213141516171821人 21