运筹学基础 课件 第6章

第6章网络计划6.1网络计划的发展历程6.2网络建模6.3关键路线法CPM6.4计划评审技术PERT6.5时间－费用优化

最早提出的统筹方法是甘特图法,该方法是科学管理的奠基人泰勒的学生,美国福克兰兵工厂顾问甘特于20世纪40年代开发的一种计划与管理技术。甘特图以时间为横坐标,

以工序为纵坐标,以线条长短表示一项工作或作业的开始和完成时刻以及工作的进展情况。由于甘特图以条形图进行系统计划和管理,故又称为横道图、条形图等(见图6-1)。

图6-1甘特图

甘特图的优点是简单明了、容易绘制、使用方便。甘特图的缺陷是:

(1)不能反映各项工作之间错综复杂的联系和制约的分工协作关系;

(2)不能区别系统中哪些工作是主要的、关键的生产联系和工序,反映不出全局的关键所在,不利于最合理地管理整个系统。

6.1网络计划的发展历程

PERT方法的优化流程为:依据工作流程绘制网络图,计算网络图参数,然后进行网络图的优化。网络图的优化以寻找关键路线为要点,在关键路线上寻找最有利的工序来缩短关键活动的时间,在可能的条件下将工序进一步细分,采用平行作业或交叉作业的方法使工期缩短。

缩短关键路线的方法有三种:

一是从非关键路线上抽调资源(人力、物力、财力等)集中于关键路线,以缩短关键路线的时间;

二是通过增加资源的方法来缩短关键路线上完成任务的期限;

三是采用新技术、新工艺等措施,缩短某些工序的时间,从而达到缩短关键路线时间的目的。

PM和PERT在原理上十分相似,都是采用网络模型,只是在工序时间的确定上有所差别。由于PERT是军方首创,对时间进度最为关心,而CPM是民间首创,对成本非常重视。一开始两种方法的侧重点略有差异,但在后来的使用与发展中逐渐靠拢并融为一体。

6.2网络建模

项目由一系列活动组成,活动的完成需要时间,不同的活动之间有相互的依存关系。在利用网络描述项目的时候,可以使用点来代表活动,使用有向边代表活动之间的先后依存关系,如图6-2所示。

图6-2网络中活动的先后关系

网络建模的步骤如下:

(1)分解出相对独立的活动。分解出相对独立的活动就是将一项任务分解成若干项活动,分析并确定各项活动在工艺和组织方面的相互联系及相互制约关系。

(2)分析活动的顺序关系、依赖关系。确定各项活动的先后顺序,分析各项活动的依赖关系,确定各项活动的所有紧前、紧后活动和与它平行的活动。

(3)列出活动的名称、所需资源。确定各项活动的名称、工期、所需资源(人力、物力、时间)等参数。

(4)每个活动使用一个网络中的一个点来表示,紧前活动和当前活动之间使用一条有向边连接。

(5)为了便于分析,确保没有紧前活动的活动只有一个,没有直接后续活动的活动也只有一个。在所建立的网络中,如果有多个没有紧前活动的活动,则增加一个虚拟的起始活动,并将其连接到所有的没有紧前活动的活动;如果有多个没有直接后续活动的活动,则增加一个虚拟的结束活动,将所有的没有直接后续活动的活动连接到虚拟的结束活动。

例6-1经过分解和分析,某项目可以由11个活动组成,这些活动之间的关系和所需时间如表6-1所示。

利用项目活动分解表,可以绘制项目网络计划的网络示意图如图6-3所示。图6-3项目网络计划的网络示意图

利用网络计划技术能够回答的问题包括:

(1)如果每个活动都按时完成,项目需要多久完工?

(2)如果项目要尽快完工,每个活动的工作时间窗口是什么?

(3)为了使项目尽快完成,哪些活动是瓶颈,哪些活动可以拖延,能拖延多久?

(4)如果有不确定性存在,项目按时完成的概率怎么计算?

(5)如果有一些额外的预算,花到什么地方可以使项目尽可能按时完成?

(6)如果要缩短项目工期,怎样使增加的费用最小?

6.3关键路线法CPM

6.3.1关键路线的计算关键路线法是最先提出的网络计划技术。所谓关键路线,就是在项目的网络中,从起始活动到结束活动所花费时间最长的路线,短于关键路线的路线称为非关键路线。路线的长度使用路线上所有活动花费时间总和计算。

为了利用最短路算法,可以将网络进行以下变换:将任意有向边的长度设为其起点活动对应的时间。

例如,对于图6-3,就可以变换为如图6-4所示的普通网络,在这个网络中,可以利用最短路算法求解从A到K的最长路。

图6-4转换为有向边带权值的普通网络

6.3.2几个时间参数的计算

对于网络中的任意一个活动,还可以计算以下几个参数:

(1)最早开始时间(ES)和最早完成时间(EF)。

任何活动的最早开始时间都决定于其所有紧前活动的最早完成时间,任何活动的最早完成时间都等于其最早开始时间加上本身所需要的时间,因此有

例如,在图6-3中,首先将没有紧前活动的活动A的最早开始时间设为0,则其最早完成时间EF=3,然后,对于B和C来讲,最早开始时间都等于A的最早完成时间,然后依次进行计算,计算的顺序参见图6-5中Step的序号。

图6-5最早开始时间和最早完成时间的计算

(2)最晚完成时间(LF)和最晚开始时间(LS)。

最晚完成时间和最晚开始时间,就是在保证整个项目最后一个活动的最早完成时间等于最晚完成时间的情况下,从后往前计算各个活动的最晚完成时间和最晚开始时间。在所

有活动的最早开始时间和最早完成时间已经确定的情况下,可以计算所有活动的最晚完成时间和最晚开始时间,计算公式为

例如,在图6-5中,首先将没有直接后续活动的活动K的最晚完成时间(LF)设为活动K的最早完成时间(EF),这样就可以保证整个项目的工期不被拖后。活动K的最晚开始时间(LS)等于最晚完成时间减去活动K本身所需要的时间。然后可以计算以K为直接后续活动的J的最晚完成时间(LF),等于活动K的最晚开始时间,然后依次进行计算,计算步骤如图6-6中Step的序号所示。

图6-6-项目活动的最晚完成时间和最晚开始时间

(3)可松弛时间。

可松弛时间就是某个活动在不影响整个项目工期的情况下,可以进行活动的时间窗口,其计算公式如下:

例如,对于图6-6,可以计算每个活动的可松弛时间如图6-7所示,其中,可松弛时间为零的关键活动使用深色表示。

图6-7活动的可松弛时间及关键活动

6.4计划评审技术PERT

乐观时间to表示活动完成的乐观估计时间,即在顺利情况下完成某个活动所需的时间。最可能时间tm

表示活动完成的最可能估计时间,即在正常情况下完成某个活动所需的时间。悲观时间tp表示活动完成的悲观估计时间,即在不利情况下完成某个活动所需的时间。

例6-2经过分解和分析,某项目可以由11个活动组成,这些活动之间的关系和所需时间如表6-2所示。

活动所需时间的期望为

对于所需时间的期望μ,这里实际上是采用了加权求和的方法,即假设活动最可能完成时间的权值为4/6,乐观时间和悲观时间的权值为1/6,而4/6≈0.6666,接近于黄金分割率。

在PERT中,假设所需时间的概率分布为一种贝塔分布,而对于贝塔分布来讲,大部分值落在区间[μ-3σ,μ+3σ]内。因此,假设tp-to=6σ,可以估计活动所需时间的方差为

需要注意的是,这里的活动所需时间的期望和方差,均是估计值。

例如,可以在表6-2的基础上,计算任一活动所需时间的期望及其方差,如表6-3所示。

如果以活动所需时间的期望μ作为活动所需时间,将随机问题转化为确定型问题,即可采用CPM的方法求解网络的关键路线,这条关键路线称为PERT的期望关键路线。也就是说,期望关键路线就是以活动所需时间的期望作为活动确定的时间,在网络上得到的关键路线。因此,期望关键路线p的期望长度为

其中,μi为活动i所需时间的期望。

然而,由于项目活动的随机性,期望关键路线上的所有活动未必都按照期望的时间完成,也就是说,期望关键路线p的长度dp应该是一个随机值,且有

如果所有活动所需时间是相互独立(需要注意的是,这个假设有的时候并不成立,有的时候,影响一个活动的因素,也会影响另外一个活动),且具有相同的分布,则dp的方差为

其中,σi2为活动i所需时间的方差。

例如,利用表6-3可以得到网络的期望关键路径如图6-8所示,网络中的活动的所需时间均使用期望时间表示,则期望关键路径p为A—C—D—E—G—I—J—K,期望长度为μp=53.67,期望方差为σ2p=7.72。

图6-8网络的期望关键路径

同理,网络上的其他路线也可以按照同样的假设和公式计算期望长度及其方差,所有路线长度的期望值和方差如表6-4所示。

例如,对于表6-4中的不同路径,计算在40周内完成的概率如表6-5所示。

6.5时间－费用优化

时间费用优化的目的主要是解决如何缩短总工期至规定值并最小化费用的问题。如果总工期小于规定的工期,则说明项目的时间要求并不紧迫,关键路线还可延长,可降低资源投入的强度。如果总工期等于规定的工期,则说明此计划较合适,无须调整。如果总工期大于规定的工期,则说明计划的总工期不能满足实际需求,需对项目计划进行修改和调整。

例如,对于图6-9所示的网络,关键路线的总长度为45,如果将关键活动E所需的时间从15缩短为1,则重新计算网络的时间参数,可得关键路线的总长度为35,调整后的关键路线总共缩短了10,与关键活动E缩短的时间14并不相等,因为关键路线发生了转移。

图6-9关键活动时间的缩短与总工期的缩短并不一定等额

综合来说