C# 中的关键路径法实现

• 下载源代码 - 134.13 KB

引言

关键路径法 或简称为 CPM 是一种基于数学的算法，用于安排一组项目活动。

背景

使用 CPM 的基本技术是构建一个项目模型，该模型包括以下内容

• 完成项目所需的所有活动的列表（也称为工作分解结构）
• 每个活动完成所需的时间（持续时间），以及
• 活动之间的依赖关系

对于一个测试用例，让我们假设以下图片

在上图中，我们有圆圈代表以大写字母标识的活动。

每个圆圈内的红色数字表示完成活动所花费的时间。

左上角和右上角的数字分别代表每个活动的最早开始时间和最早结束时间。左下角和右下角的数字分别代表每个活动的最晚开始时间和最晚结束时间。

带有红色边框的圆圈代表此给定活动集的关键路径。

Using the Code

首先对代表每个活动的类进行建模。 该类具有活动的 ID、描述和持续时间以及最早开始时间 (est)、最晚开始时间 (lst)、最早结束时间 (eet) 和最晚结束时间 (let) 作为属性。

每个活动之间的依赖关系存储在两个数组中，即后继者数组和前驱者数组。

public class Activity
{
  private string id;
  private string description;
  private int duration;
  private int est;
  private int lst;
  private int eet;
  private int let;
  private Activity[] successors;
  private Activity[] predecessors;
 
  ...
}

CPM 算法使用活动数据来计算到项目结束的计划活动的最长路径，以及每个活动可以在不延长项目时间的情况下最早和最晚开始和完成的时间。此过程确定哪些活动是“关键的”（即，在最长路径上），哪些活动具有“总浮动时间”（即，可以延迟而不会延长项目时间）。

为了完成这个，创建了两个方法：一个叫做 WalkListAhead，另一个叫做 WalkListAback。

WalkListAhead 方法接收存储活动的数组，并在数组内执行正向遍历，计算每个活动的最早开始时间和最早结束时间。

在正向遍历之后，WalkListAback 执行反向遍历，计算每个活动的最晚开始时间和最晚结束时间。

WalkListAhead 和 WalkListAback 方法的实现

private static Activity[] WalkListAhead(Activity[] list)
{
  list[0].Eet = list[0].Est + list[0].Duration;
 
  for(int i = 1; i < na; i++)
  {
    foreach(Activity activity in list[i].Predecessors)
    {
      if(list[i].Est < activity.Eet)
        list[i].Est = activity.Eet;
    }
 
    list[i].Eet = list[i].Est + list[i].Duration;
  }
 
  return list;
}

private static Activity[] WalkListAback(Activity[] list)
{
  list[na - 1].Let = list[na - 1].Eet;
  list[na - 1].Lst = list[na - 1].Let - list[na - 1].Duration;

  for(int i = na - 2; i >= 0; i--)
  {
    foreach(Activity activity in list[i].Successors)
    {
      if(list[i].Let == 0)
        list[i].Let = activity.Lst;
      else
        if(list[i].Let > activity.Lst)
          list[i].Let = activity.Lst;
    }

    list[i].Lst = list[i].Let - list[i].Duration;
  }

  return list;
}

为了计算关键路径，一个名为 CriticalPath 的方法验证每个活动的最早结束时间减去最晚结束时间以及最早开始时间减去最晚开始时间是否等于零。 如果是，则该活动是关键路径的一部分，其 Id 将写在屏幕上。 还会显示项目的总持续时间。

CriticalPath 方法的实现

void CriticalPath(Activity[] list)
{
  Console.Write"\n          Critical Path: ");
 
  foreach(Activity activity in list)
  {
    if((activity.Eet - activity.Let == 0) && (activity.Est - activity.Lst == 0))
      Console.Write("{0} ", activity.Id);
  }
 
  Console.Write("\n\n         Total duration: {0}\n\n", list[list.Length - 1].Eet);
} 

运行测试用例

这是执行与上图相关的测试用例时的输出

历史

• 最初发布在我的 博客上，发布日期为 2007 年 12 月 18 日