[科普中国]-关键路径法

关键路径是指设计中从输入到输出经过的延时最长的逻辑路径。优化关键路径是一种提高设计工作速度的有效方法。一般地，从输入到输出的延时取决于信号所经过的延时最大路径，而与其他延时小的路径无关。在优化设计过程中关键路径法可以反复使用，直到不可能减少关键路径延时为止。EDA工具中综合器及设计分析器通常都提供关键路径的信息以便设计者改进设计，提高速度。1

起源关键路径法（CPM）最早出现于1956年，当时美国杜邦（Du Pont）公司的主要负责人Morgan Walker和雷明顿兰德（Remington Rand）公司的数学家James E. Kelly研究如何能够采取正确的措施，在减少工期的情况下能尽可能少的增加费用。1957年5月7日，Kelly借用了线性规划的概念来解决项目计划自动计算的问题，简单的说就是确定了每个活动的工期和活动间的逻辑关系，输入电脑后就能自动计算项目的工期，为了电脑的计算，Kelly在活动间使用了i，j这样的节点来表示活动间的前后逻辑关系。同时Kelly绘制了图形来解释电脑所作的工作，图形以箭线表示活动，以节点表示活动间的逻辑关系，这就是最早的箭线图（ADM）。1959年，Kelly和Walker共同发表了”Critical Path Planning and Scheduling” 论文，在这篇长达25页的论文中，Kelly和Walker不仅阐述了关键路径法的基本原理，还提出了资源分配与平衡、费用计划的方法。我们今天所使用的方法的原理，与Kelly和Walker在论文中提出的方法，并没有原则上的不同。

与此同时，另外一个对关键路径法（CPM）的发展起到重要作用的是美国海军北极星计划开发的计划评审技术（PERT）。在1955年11月17日，美国海军北极星计划成立了一个特别项目管理办公室（SPO），管理其Fleet Ballistic Missile计划，负责人是Admiral Raborn。在1956年和1957年期间，他们研究了各种已经存在的项目管理技术，在大约1957年秋季的时候，他们接触到了杜邦公司开发的计划管理技术，这对他们开发PERT起到了重要的作用。1958年1月份，SPO研究了在计算机上实现计划和控制的可行性，1958年1月27日，SPO正式成立了一个小组开发PERT技术，在大约一年以后，PERT技术成为一种可操作性的技术，计划评审技术（PERT）和关键路径法（CPM）基本上一样，唯一的区别是计划评审技术的每个活动的工期不是确定的，而是包括了悲观值，乐观值和最有可能值三个值。比较有趣的是，1959年，北极星计划的这个特别项目管理办公室（SPO）开了一个招待会，介绍他们的这种新技术，并希望参会者能给出更多的意见，Kelly和Walker在被邀请之列，在会上，他们发现SPO开发的PERT和他们的Kelly-Walker法原理上完全一样，而SPO所说的关键线路（Critical Path），就是他们的Kelly-Walker法中的主链路（Main Chain）。回去之后，他们决定将它们的方法的名称改为关键路径法（Critical Path Method）。

关键路径法（CPM）最初被开发是用于项目管理，不过，在发展过程中，它逐渐在工程项目的合同索赔和纠纷解决上起到重要作用。最早在诉讼中涉及到要求使用关键路径法（CPM）是1972（Appeal of Minmar Builders，Inc，GSBCA No. 3430，72-2 BOA）年，在此案例中，法庭由于承包商没有使用关键路径法（CPM）而拒绝了承包商的索赔，因为其使用的横道图不能显示具体的活动是否在关键线路上，从而无法判断活动耽误对于整体的影响。之后，关键路径法（CPM）逐渐成为工期延误索赔中必须的做法，并逐渐形成了很多专门的分析方法，甚至有很多人专业从事工期延误分析的工作。1

使用步骤画出网络图，以节点标明事件，由箭头代表作业。这样可以对整个项目有一个整体概观。习惯上项目开始于左方终止于右方；

在箭头上标出每项作业的持续时间（T）；

从左面开始，计算每项作业的最早结束时间（EF）。该时间等于最早可能的开始时间（ES）加上该作业的持续时间；

当所有的计算都完成时，最后算出的时间就是完成整个项目所需要的时间；

从右边开始，根据整个项目的持续时间决定每项作业的最迟结束时间（LF）；

最迟结束时间减去作业的持续时间得到最迟开始时间（LS）；

每项作业的最迟结束时间与最早结束时间，或者最迟开始时间与最早开始时间的差额就是该作业的时差；

如果某作业的时差为零，那么该作业就在关键路线上；

项目的关键路线就是所有作业的时差为零的路线。

分类关键路径法是用寻找关键路径及其时间长度来确定项目的完成日期与总工期的方法。

根据绘制方法的不同，关键路径法可以分为两种：即箭线图（ADM）和前导图（PDM）。

箭线图（ADM）法又称为双代号网络图法，它是以横线表示活动而以带编号的节点连接活动，活动间可以有一种逻辑关系，结束-开始型逻辑关系。在箭线图中，有一些实际的逻辑关系无法表示，所以在箭线图中需要引入虚工作的概念。

箭线图箭线图（ADM）要表示的是一个项目的计划，所以其清晰的逻辑关系和良好的可读性是非常重要的，除了箭线图（ADM）本身具有正确的逻辑性，良好的绘图习惯也是必要的。因此在绘图时遵守上面的这些规则就是非常重要的，另外，在绘图时，一般尽量使用直线和折线，在不可避免的情况下可以使用斜线，但是要注意逻辑方向的清晰性。绘制箭线图时主要有以下一些规则：

在箭线图（ADM）中不能出现回路；

箭线图（ADM）一般要求从左向右绘制；

每一个节点都要编号，号码不一定要连续，但是不能重复，且按照前后顺序不断增大；

一般编号不能连续，并且要预留一定的间隔；

表示活动的线条不一定要带箭头，但是为了表示的方便，一般推荐使用箭头；

一般要求双代号网络图要开始于一个节点，并且结束于一个节点；

在绘制网络图时，一般要求连线不能相交，在相交无法避免时，可以采用过桥法或者指向法等方法避免混淆。

前导图前导图（PDM）法又称为单代号网络图法，它是以节点表示活动而以节点间的连线表示活动间的逻辑关系，活动间可以有四种逻辑关系，结束-开始、结束-结束、开始-开始和开始-结束。绘制前导图时主要有以下一些规则：

单代号网络图必须正确表达已定的逻辑关系；

单代号网络图中，严禁出现循环回路；

单代号网络图中，严禁出现双向箭头或无箭头的连线；

单代号网络图中，严禁出现没有箭尾节点的箭线和没有箭头节点的箭线；

绘制网络图时，箭线不宜交叉，当交叉不可避免时，可采用过桥法或指向法绘制。2

时间参数在关键路径法中，一般有以下的时间参数：

最早开始时间（Early Start）是指活动最早开始时间，由所有前置活动中最后一个最早结束时间确定。

最早结束时间（Early Finish）是指活动最早结束时间，由活动的最早开始时间加上其工期确定。

最迟结束时间（Late Finish）是指一个活动在不耽误整个项目的结束时间的情况下能够最迟结束的时间。它等于所有紧后工作中最早的一个最迟开始时间。

最迟开始时间（Late Start）是指一个活动在不耽误整个项目的结束时间的情况下能够最迟开始的时间。它等于活动的最迟结束时间减去活动的工期。

总时差（Total Float) 是指一项活动在不影响整体计划工期的情况下最大的浮动时间。

自由时差（Free Float）是指活动在不影响其紧后工作的最早开始时间的情况下可以浮动的时间。

如果是对于箭线图法，用到的时间参数还常有：

最早节点时间（Early Event Occurrence Time）由其前置活动中最晚的最早结束时间确定。

最迟节点时间（Late Event Occurrence Time）由其后置活动中最早的最迟开始时间确定。2

时间计算正推法箭线图（ADM）的计算一般有正推法（Forward Pass）和逆推法（Backward Pass）两种，正推法用于计算活动和节点的最早时间，其算法如下：

设置箭线图（ADM）中的第一个节点的时间，如设置为1；

选择一个开始于第一个节点的活动开始进行计算；

令活动最早开始时间等于其开始节点的最早时间；

在选择的活动的最早开始时间上加上其工期，就是其最早结束时间；

比较此活动的最早结束时间和此活动结束节点的最早时间。如果结束节点还没有设置时间，则此活动的最早结束时间就是该结束节点的最早时间；如果活动的结束时间比结束节点的最早时间大，则取此活动的最早结束时间作为节点的最早时间；如果此活动的最早结束时间小于其结束节点的最早时间，则保留此节点时间作为其最早时间；

检查是否还有其它活动开始于此节点，如果有，则回到步骤3进行计算；如果没有，则进入下一个节点的计算，并回到步骤3开始，直到最后一个节点。

逆推法活动和节点的最迟时间采用逆推法（Backward Pass）计算，逆推法（Backward Pass）一般从项目的最后一个活动开始计算，直到计算到第一个节点的时间为止，在逆推法的计算中，首先令最后一个节点的最迟时间等于其最早时间，然后开始计算，具体的计算步骤如下所示：

设置最后一个节点的最迟时间，令其等于正推法计算出的最早时间；

选择一个以此节点为结束节点的活动进行计算；

令此活动的最迟结束时间等于此节点的最迟时间；

从此活动的最迟结束时间中减去其工期，得到其最迟开始时间；

比较此活动的最迟开始时间和其开始节点的最迟时间。如果开始节点还没有设置最迟时间，则将活动的最迟开始时间设置为此节点的最迟时间，如果活动的最迟开始时间早于节点的最迟时间，则将此活动的最迟开始时间设置为节点的最迟时间，如果活动的最迟开始时间迟于节点的最迟时间，则保留原节点的时间作为最迟时间；

检查是否还有其它活动以此节点为结束节点，如果有则进入第二步计算，如果没有则进入下一个节点，然后进入第二步计算，直至最后一个节点；

第一个节点的最迟时间是本项目必须要开始的时间，假设取最后一个节点的最迟时间和最早时间相等，则其值应该等于1。2

应用在项目管理中，编制网络计划的基本思想就是在一个庞大的网络图中找出关键路径，并对各关键活动，优先安排资源，挖掘潜力，采取相应措施，尽量压缩需要的时间。而对非关键路径的各个活动，只要在不影响工程完工时间的条件下，抽出适当的人力、物力和财力等资源，用在关键路径上，以达到缩短工程工期，合理利用资源等目的。在执行计划过程中，可以明确工作重点，对各个关键活动加以有效控制和调度。

关键路径法主要是一种基于单点时间估计、有严格次序的一种网络图。它的出现为项目提供了重要的帮助，特别是为项目及其主要活动提供了图形化的显示，这些量化信息为识别潜在的项目延迟风险提供极其重要的依据。3

本词条内容贡献者为:

杜强 - 高级工程师 - 中国科学院工程热物理研究所