网络图时间参数计算例题

在网络规划与设计时，时间是一个极其重要的因素。了解和计算网络的时间参数，可为网络的高效运行提供保障。本文以一个例题为例，介绍网络图时间参数的计算方法。

假设某公司需要完成以下5项任务，并以网络图形式展示：

任务1需要5天完成，任务2需要10天完成，任务3需要8天完成，任务4需要6天完成，任务5需要7天完成。为了保证任务的优先级，任务3开始前必须完成任务1和任务2；任务4开始前必须完成任务2；任务5开始前必须完成任务3和任务4。现在需要计算完成整个项目需要的最短时间和关键路径。

首先，对任务进行编号，并按照任务之间的依赖关系绘制出网络图：


节点表示任务，箭头表示依赖关系，箭头上的数字表示完成该任务所需的时间。

接下来，根据网络图计算每个任务的最早开始时间（EST）和最迟开始时间（LST），以及每个任务的最早完成时间（EFT）和最迟完成时间（LFT）。其中，EST表示在没有任何限制的情况下，任务最早可以开始的时间；LST表示在不能延误整个项目完成的前提下，任务最迟必须开始的时间；EFT表示在没有任何限制的情况下，任务最早可以完成的时间；LFT表示在不能延误整个项目完成的前提下，任务最迟必须完成的时间。

按照以下步骤计算每个任务的时间参数：

1. 对起点S进行初始化，EST=0，EFT=0。

2. 对第一个任务1进行计算。EST=0，EFT=5。由于任务1没有后继任务，所以LST=EFT=5，LFT=EFT=5。

3. 对第二个任务2进行计算。EST=5，EFT=15。由于任务2没有后继任务，所以LST=EFT=15，LFT=EFT=15。

4. 对第三个任务3进行计算。EST=max(EST(任务1)+时间1，EST(任务2)+时间2)=max(5+8，15+8)=23；EFT=EST(任务3)+时间3=31。因为任务3有后继任务，所以LFT=min(LFT(任务4)，LFT(任务5))=27，LST=LFT(任务3)-时间3=19。

5. 对第四个任务4进行计算。EST=max(EST(任务2)+时间2)=max(15+6)=21；EFT=EST(任务4)+时间4=27。因为任务4有后继任务，所以LFT=min(LFT(任务5))=LFT(任务4)+6=33，LST=LFT(任务4)-时间4=27。

6. 对第五个任务5进行计算。EST=max(EST(任务3)+时间3，EST(任务4)+时间4)=max(31+7，27+7)=38；EFT=LFT(任务5)=33。因为任务5没有后继任务，所以LST=EFT-时间5=26。

如下表所示，每个任务的时间参数计算结果：

| 任务 | EST | EFT | LST | LFT |

|------|-----|-----|-----|-----|

| 1 | 0 | 5 | 5 | 5 |

| 2 | 5 | 15 | 15 | 15 |

| 3 | 23 | 31 | 19 | 27 |

| 4 | 21 | 27 | 27 | 33 |

| 5 | 38 | 33 | 26 | 33 |

根据计算出的时间参数，可得到最短时间和关键路径。最短时间是所有任务的最早完成时间，即节点5的EFT=33。关键路径是所有不能延误整个项目完成时间的任务组成的路径，如下图所示：


根据关键路径可知，在完成整个项目的过程中，任务2、3、4是必须按时完成的任务。

综上所述，网络图时间参数计算是一个复杂而重要的过程。通过计算每个任务的EST、LST、EFT、LFT，可得到最短时间和关键路径，为网络运行提供保障。