CPM and PERT

Example of CPM analysis in the critpath package

The table below provides information on the structure of the graph and the duration of activities in some example project. The same dataset is available in the critpath package as cpmexample1. This example assumes that the durations are deterministic. Starting and ending node numbers are provided for each activity. It is also possible to pass the structure of the graph through a list of immediate predecessors. See the Introduction vignette.

Tab. 1. Data for the CPM model
Start. node	End. node	Name	Duration
1	2	A	3
1	3	B	2
1	4	C	5
2	4	D	1
3	4	E	1
4	5	F	3

We will perform the following analyzes:

making a graph of connections between activities,
finding the start and end times of all activities,
indicating the bottlenecks of the project (critical activities),
puting critical activities on the graph,
making a Gantt chart,
making ASAP and ALAP charts.

Notice!

The critpath requires additional packages to be installed. The required packages are DiagrammeR, ggplot2, reshape2 and stringr.

You can preview what the graph looks like before solving it. The plot_graphAOA() function is used for this.

plot_graphAOA(cpmexample1)

Fig. 1. Graph for the cpmexample1 dataset

The next two items from the list above are performed by the solve_pathAOA() function. It creates the schedule of the project and requires two arguments: data frame prepared according to the scheme described above and a logical argument indicating what kind of duration (deterministic or stochastic) we are dealing with.

x <- solve_pathAOA(cpmexample1, deterministic = TRUE)
#> Completion time:  8

After the calculations are completed, a message is displayed with the directive term. The result of the solve_pathAOA() function is saved to the list. Its elements vary slightly depending on the type of method used. For the CPM, these will be:

A saved graph created with a DiagrammeR package.
The schedule of the project.
Project completion time.
List of critical activities.
A table with free float and conditional float values.

Operator “[” returns objects of the list type. In turn, the operator “[[” allows you to access the value of a specific list item.

# Schedule
x[2]
#> $schedule
#>   Name Duration ESij LSij EFij LFij TFij Crit
#> 1    A        3    0    1    3    4    1     
#> 2    B        2    0    2    2    4    2     
#> 3    C        5    0    0    5    5    0    *
#> 4    D        1    3    4    4    5    1     
#> 5    E        1    2    4    3    5    2     
#> 6    F        3    5    5    8    8    0    *
# Directive deadline
x[3]
#> $ComplTi
#> [1] 8
# Critical activities
x[4]
#> $CritAct
#> [1] "C" "F"
# Free float and conditional float values
x[5]
#> $AddSlacks
#>   Name FST CST
#> 1    A   0   1
#> 2    B   0   2
#> 3    C   0   0
#> 4    D   1   0
#> 5    E   2   0
#> 6    F   0   0

The first element of the list x is used by other functions in the package. It belongs to the dgr_graph class supported by the DiagrammeR package. It is possible to perform operations described in the manual of this package. Asterisks in the last column of the schedule indicate which activities are critical.

Now, let’s draw a graph with the critical activities marked. We will use the plot_graphAOA() function again but with different argument. It will be a list created after solving the problem. This requires the use of the solved”* argument.

plot_graphAOA(solved = x)

Fig. 2. Critical path for the cpmexample1 dataset

The next element of the CPM analysis will be the Gantt chart. The plot_gantt() function requires the ggplot2 and reshape2 packages to be installed first. It also takes the list produced by the solve_pathAOA() function as a mandatory argument. Optional argument bar_size determines the thickness of the bar of the drawn activity. The default is 10, and if appropriate, this argument need not be provided.

plot_gantt(x)

Fig. 3. Gantt chart for the cpmexample1 dataset

The activities are displayed in the order they were entered. The critical ones are marked with CR and the non-critical ones with NC. Additionally, total floats greater than zero have been added for non-critical activities.

Based on the Gantt chart we can plot two more charts. The first one is the ASAP chart which shows effetcs of starting activity as early as possible and end it as early as possible. It can be achieved withe the plot_asap() function.

plot_asap(x)

Fig. 4. ASAP chart for the cpmexample1 dataset

On the other hand, the ALAP chart shows effetcs of starting activity as late as possible and end it as late as possible. It can be achieved with the plot_alap() function.

plot_alap(x)

Fig. 5. ALAP chart for the cpmexample1 dataset

The plot_gantt(), plot_asap(), plot_alap() functions have an optional show_dummy parameter. If it is set to TRUE, dummy activities will be placed on the chart.

Example of PERT analysis in the critpath package

We will use a different data than in CPM. This data is available in a set named pertexample1. Let us assume that the durations are described with three numerical values as in Table 2. The package allows you to calculate the expected value and variance according to several different formulas (check the solve_pathAOA() function help). In this example, we will use classic formulas.

Tab. 2. Data for the PERT model
Start. node	End. node	Name	Optimistic dur.	Most likely dur.	Pessimistic dur.
1	2	A	3	5	7
2	3	B	5	7	9
3	4	C	5	5	8
3	5	D	1	6	8
3	6	E	6	8	10
4	7	F	2	6	7
5	7	G	5	6	7
6	7	H	3	5	7
7	8	I	4	6	8

We are interested in the following types of analyzes:

determining the start and end times for each activity,
identifying the bottlenecks of the project (critical activities),
placing critical activities on the graph,
making a Gantt chart,
making ASAP and ALAP charts,
indication of directive terms for the risk-taker and the belayer schedules.

Duration in PERT is a random variable, so we will change the deterministic argument to FALSE.

y <- solve_pathAOA(pertexample1, deterministic = FALSE)
#> Expected compl. time distribution: N( 31 , 1.490712 )

After solving the problem, a message appears giving the parameters of the normal distribution of a random variable describing the project completion time.

Below we display the elements of the list storing the solution. It contains one more element than the list created for the CPM method. The Time column contains the expected duration of the activity.

# Schedule
y[2]
#> $schedule
#>   Name Duration       Var ESij LSij EFij LFij TFij Crit
#> 1    A      5.0 0.4444444  0.0  0.0  5.0  5.0  0.0    *
#> 2    B      7.0 0.4444444  5.0  5.0 12.0 12.0  0.0    *
#> 3    C      5.5 0.2500000 12.0 14.0 17.5 19.5  2.0     
#> 4    D      5.5 1.3611111 12.0 13.5 17.5 19.0  1.5     
#> 5    E      8.0 0.4444444 12.0 12.0 20.0 20.0  0.0    *
#> 6    F      5.5 0.6944444 17.5 19.5 23.0 25.0  2.0     
#> 7    G      6.0 0.1111111 17.5 19.0 23.5 25.0  1.5     
#> 8    H      5.0 0.4444444 20.0 20.0 25.0 25.0  0.0    *
#> 9    I      6.0 0.4444444 25.0 25.0 31.0 31.0  0.0    *
# Expected completion time
y[3]
#> $ComplTi
#> [1] 31
# Standard deviation of the completion time
y[4]
#> $SDevTi
#> [1] 1.490712
# Critical activities
y[5]
#> $CritAct
#> [1] "A" "B" "E" "H" "I"
# Free float and conditional float values
y[6]
#> $AddSlacks
#>   Name FST CST
#> 1    A 0.0 0.0
#> 2    B 0.0 0.0
#> 3    C 0.0 2.0
#> 4    D 0.0 1.5
#> 5    E 0.0 0.0
#> 6    F 2.0 0.0
#> 7    G 1.5 0.0
#> 8    H 0.0 0.0
#> 9    I 0.0 0.0

The activity graph, the Gantt, ASAP anad ALAP charts are obtained in the same way as before.

plot_graphAOA(solved = y)

Fig. 6. Critical path for the pertexample1 dataset

plot_gantt(y)

Fig. 7. Gantt chart for the pertexample1 dataset

plot_asap(y)

Fig. 8. ASAP chart for the pertexample1 dataset

plot_alap(y)

Fig. 9. ALAP chart for the pertexample1 dataset

To set deadlines corresponding to the schedules of the risk-taker and the belayer, we will use the PERT_newtime() function.

# Risk-taker's schedule
PERT_newtime(new_prob = 0.3, y)
#> New expected compl. time:  30.21827
#> $probDT
#> [1] 0.3
#> 
#> $newDT
#> [1] 30.21827

# Belayer's schedule
PERT_newtime(new_prob = 0.6, y)
#> New expected compl. time:  31.37767
#> $probDT
#> [1] 0.6
#> 
#> $newDT
#> [1] 31.37767

The PERT_newprob() function answers to the question about the probability of completing the project for a given directive deadline. For example the probability that the project will end after 30 days

PERT_newprob(new_DT = 30, y)
#> Prob. of completion:  0.2511675
#> $newDT
#> [1] 30
#> 
#> $prob_compl
#> [1] 0.2511675

Besides, the plot_norm() function draws a plot of the normal distribution of a random variable describing the expected directive deadline.

plot_norm(y)

Fig. 10. Normal distribution for the pertexample1 dataset

Additional vertical lines indicate the schedules of the risk-taker and the belayer.

- Example of CPM analysis in the critpath package
- Example of PERT analysis in the critpath package