关键路径

来自计算思维百科
跳转至: 导航搜索

在我们完成一个工作时,往往有完成工作的多种进度序列,在这些序列中,有一条从开始到结束有着最长工期的路径或是没有任何时差的路径,这个路径称为关键路径。

关键路径1.png

基本概念

关键路径通常是决定项目工期的进度活动序列。它是项目中最长的路径,关键路径的工期决定了整个项目的工期,这条路径上很小的变化都可能直接影响整个项目的最早完成时间。例如,我们要准备一个家庭宴会,有很多工作需要准备,包括:制定菜单、购买原料、准备餐具、准备甜点、清洗原料、烹饪、布置餐桌。其中准备甜点与原料清洗可以同时进行,而布置餐桌和准备餐具可以和清洗原料、烹饪登工序并行,互不影响。这样,这个工作就有两条关键路径:

1、 制定菜单 →采购原料→清洗原料→烹饪

2、 制定菜单 →采购原料→甜点准备→烹饪 这两条关键路径中任何一个环节的时间如果有变化,整个工作的时间就会随之变化,所以他们是关键路径。

关键路径往往不止一条,也非一成不变,在一定条件下,受干扰因素的影响,可能会发生两方面变化:一是数量增加;二是关键路径和非关键路径发生转化。非关键路径上的某些工作拖延,相关路径的路长超出了关键路径路长,则该路径就转化为关键路径,原来的关键路径就转化为非关键路径。最容易发生转化的是路长仅次于关键路径路长的路径,称为次关键路径。

关键路径是一种网络图方法,由雷明顿-兰德公司(Remington- Rand)的JE克里(JE Kelly)和杜邦公司的MR沃尔克(MR Walker)在1957年提出的,它适用于有很多作业而且必须按时完成的项目。

应用范围

关键路径法主要应用于项目的进度管理。

使用方法及步骤

1) 将项目中的各项活动视为有一个时间属性的结点,从项目起点到终点进行排列;例如家庭宴会这个工作的节点包括:

活动描述

用时(小时)

依赖关系

制定菜单

0.5

 

采购原料

2

制定菜单必须完成

准备餐具

0.5

 

准备甜点

1

采购原料必须完成

清洗原料

1

采购原料必须完成

烹饪

2

清洗原料必须完成

布置桌椅

0.2

准备餐具必须完成

2) 用有方向的线段标出各结点的紧前活动和紧后活动的关系,使之成为一个有方向的网络图;

关键路径2.png

3) 在这张图中有三条路径,其中有两条包含必须的烹饪步骤,这两条路径的完成时间都是5.5小时;所以这两条路径是关键路径;

应用案例

应用1-项目的时间管理

案例:

今年暑假,张红要到山区小学支教,早晨需要做以下几项任务:A、扫地(5分钟)B、淘米(4分钟)C、洗菜(6分钟)D、烧水(3分钟)E、煮饭(8分钟)F、炒菜(7分钟)。试给张红分析各任务之间的进程安排情况,得出任务的总工期。

解决步骤:

1) 将项目中的各项活动视为有一个时间属性的结点,根据实际情况可知,扫地,洗菜可与烧水煮饭同时进行,即A、C可与D、E同时进行;

2) 用有方向的线段标出各结点的紧前活动和紧后活动的关系,使之成为一个有方向的网络图;

关键路径3.png

3) 根据网络图可得,从开始节点1到节点7有两条路: a、B->A->C->F,需22分钟; b、B>D->E->F,需24分钟; 因此,b路径工序时间之和最长,为关键路径,因此决定了活动总工期为24分钟。

应用2-木桶原理

盛水的木桶是由多块木板箍成的,盛水量也是由这些木板共同决定的。若其中一块木板很短,则此木桶的盛水量就被限制,该短板就成了这个木桶盛水量的“限制因素”。若要使此木桶盛水量增加,只有换掉短板或将其加长才行。人们把这一规律总结为“木桶原理”

木桶中的短板是决定木桶盛水量的关键,可称作是木桶工程中的关键路径。

可以体现的计算思维

关键路径法体现了计算思维中的并行及抽象的思想,在解决问题的时候,让多个任务同时进行,提高处理问题的速度,有效地利用时间,而任务完成的效率由最耗时的路径决定;同时也结合图的思想,把问题抽象成图,从纷繁中提炼出问题的本质,从而使问题易于解决。