Click here to Skip to main content
13,591,177 members
Click here to Skip to main content
Add your own
alternative version

Stats

88.5K views
3.2K downloads
24 bookmarked
Posted 16 Apr 2008
Licenced CPOL

Critical Path Method Implementation in C#

, 16 Apr 2008
Rate this:
Please Sign up or sign in to vote.
C# Console Application for calculating the Critical Path of a set of project activities

Introduction

The Critical Path Method or just CPM is a mathematically based algorithm for scheduling a set of project activities.

Background

The essential technique for using CPM is to construct a model of the project that includes the following:

  • A list of all activities required to complete the project (also known as Work Breakdown Structure)
  • The time (duration) that each activity will take to completion, and
  • The dependencies between the activities

For a test case, let's assume the following picture:

CPM Test Case - Click to enlarge image

In the picture above, we have circles that represent activities identified by capitalized letters.

The red number inside each circle indicates the time spent to complete the activity.

The upper left and right numbers represent the earliest start time and earliest end time of each activity respectively. The lower left and right numbers represent the latest start time and latest end time of each activity respectively.

The circles with a red border represent the critical path for this given set of activities.

Using the Code

A class that represents each activity was firstly modelled. This class has as properties the activity's ID, description and duration along with the earliest start time (est), latest start time (lst), earliest end time (eet) and latest end time (let).

The dependencies between each activity are stored in two arrays, the successors and predecessors arrays.

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;
 
  ...
}

The CPM algorithm uses the activities data to calculate the longest path of planned activities to the end of the project, and the earliest and latest that each activity can start and finish without making the project longer. This process determines which activities are "critical" (i.e., on the longest path) and which have "total float" (i.e., can be delayed without making the project longer).

To accomplish that, two methods were created: one called WalkListAhead and the other called WalkListAback.

The WalkListAhead method receives the array that stores the activities and performs the forward walking inside the array calculating for each activity its earliest start time and earliest end time.

After the forward walking, the WalkListAback performs the backward walking calculating for each activity its latest start time and latest end time.

The WalkListAhead and WalkListAback methods implementation:

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;
}

To calculate the critical path, a method called CriticalPath verifies if each activity's earliest end time minus the latest end time and earliest start time minus the latest start time are equal zero. If so, the activity is part of the critical path and its Id is written in the screen. The project's total duration is also shown.

The CriticalPath method implementation:

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);
} 

Running the Test Case

This is the output when the test case pertaining to the above picture is executed:

CPM Test Case Result

History

  • Originally posted on my blog on 12/18/2007

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

leniel
Software Developer
Brazil Brazil
Jesus Christ follower and computer engineer.
As a geek I am an enthusiast of technology in all forms it is presented. One of my desires is to make a difference in building software products and services used by millions of people every day.

You may also be interested in...

Pro
Pro

Comments and Discussions

 
QuestionCode doesn't work at all if activity has more than one succesor or precedesor Pin
Member 103787609-Apr-14 6:22
memberMember 103787609-Apr-14 6:22 
Questionhow can i find critical path if i store everything in lists Pin
Member 1050843127-Jan-14 23:01
memberMember 1050843127-Jan-14 23:01 
Questioni was struct in getting a result in Earlystart EarlyFinish and Lasterstart and lartestfinish Pin
Member 1050843127-Jan-14 22:58
memberMember 1050843127-Jan-14 22:58 
QuestionGeneral Solution Pin
__ben17-Apr-12 21:48
member__ben17-Apr-12 21:48 
Questionhelp change to vb.net 2005 Pin
Ci Hua Hua18-Dec-11 17:24
memberCi Hua Hua18-Dec-11 17:24 
GeneralI've taken this engine and refactored it as a generic IEnumerable<T> extension method Pin
Emil Lerch18-May-11 10:50
memberEmil Lerch18-May-11 10:50 
GeneralRe: I've taken this engine and refactored it as a generic IEnumerable extension method [modified] Pin
leniel18-May-11 10:56
memberleniel18-May-11 10:56 
GeneralI have a problem Pin
majastipp27-Apr-11 8:11
membermajastipp27-Apr-11 8:11 
GeneralHei, this algorithm is not fully cover all case Pin
THOBONG18-Apr-11 1:08
memberTHOBONG18-Apr-11 1:08 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web03-2016 | 2.8.180618.1 | Last Updated 16 Apr 2008
Article Copyright 2008 by leniel
Everything else Copyright © CodeProject, 1999-2018
Layout: fixed | fluid