CPMfinal

Critical Path Method (CPM)

Introduction:

Critical path method (CPM) was invented by project managers in the early 1950's. The US Navy adapted and improved it to manage the Polaris missile project in the late 1950's. Naming the technique PERT (Program Evaluation and Review Technique) the Defense, Aerospace, and other industries adopted the tool as the major project tool to this day.

Critical Path Method (CPM), is a procedure for using network analysis to identify those tasks which are on the critical path: i.e. where any delay in the completion of these tasks will lengthen the project time scale, unless action is taken. For all tasks off the critical path, a degree of tolerance is possible (e.g. late start, late completion, early start, etc.). Network charts and CPM analysis used to be carried out by hand. Software is now available which requires the user only to enter the tasks, duration of each task and dependencies upon other tasks; a network chart and CPM is then automatically created.

Critical Path Analysis is an extremely effective method of analyzing a complex project. It helps you to calculate the minimum length of time in which the project can be completed, and which activities should be prioritized to complete by that date.

Where a job has to be completed on time, critical path analysis helps you to focus on the essential activities to which attention and resources should be devoted. It gives an effective basis for the scheduling and monitoring of progress.

The Critical Path Method (CPM) is a technique used in planing of projects. It is especially helpful when the projects are composed of a number of individual "activities." In many instances, an activity cannot start before the completion of another activity. CPM Models can be used to determine the time required to complete the project and which activities are critical. Critical activities have to be completed on time; otherwise the entire project completion date will be delayed. Non critical activities have "slack" time and be delayed.

Activities, precedences and times:

I have chosen the construction of a residential structure as the project. The tasks to be performed, the tasks that have to be completed prior to, and the duration of each task is shown in the table 1.

Figure 1 shows the activities diagram. Numbered nodes represent stages of project completion, and are made up as the diagram is constructed. They are connected by arrows or links that are activities listed in Table 1. Placing formwork and placing reinforcement can only start after excavation is complete. Now concreting slab can proceed only after both of these activities are complete. But an activity cannot start from two nodes. So a "Dummy" activity is placed to solve this problem. A dummy activity requires no time or cost.

I then used MicroSoft Excel (Spread Sheet). Figure 2 shows the Activities, the times and the nodes. Highlight the nodes, and copy them in the program as shown in figure 3. Only the first eight nodes are visible. A scroll bar will enable the rest to be seen. The computer program will locate all the possible paths. 1 means that there is a path, and 0 means that there is no path. There are eight possible paths. Copy these paths in the spreadsheet as shown in figure 4. To find the time required for the first path, we have to multiply the path by the time and add. The spreadsheet command is =SUMPRODUCT(B9:R9,$B$7:$R$9). Highlighting this cell and and dragging down and using fill down will calculate the times for the rest of the paths. =MAX( S9:S17) will determine the path with the largest time. Figure 4 shows the spreadsheet up to this stage. The path with the maximum time is the critical path with no slack. Figure 5 is a diagram showing all the paths that are possible. To see which activities are on each of the paths, enter = IF(B9=1,B$2,""). If there is a path, the activity letter will appear (where there is a 1). Otherwise there will be a blank space. Since the critical path is the path with the maximum time, type = IF(S9=$K$18,"CRITICAL","). Fill down will indicate the CRITICAL path. Figure 6 shows the spread sheet at this stage. Figure 7 shows a diagram with the critical path.

The algorithm explains the forward and the backward pass. The first node has no precedence. During forward pass, activity times are added to determine the end of each activity. If an activity has to start after the completion of two or more activities, the maximum time is determined. The last node has no successor. The algorithm ensures that the critical path will be selected. The latest finish time is the same as the earliest finish time. During backward pass, activity times are subtracted. If an activity has to finish before the start of two or more activities, the minimum time is computed. If the earliest start time is the same as the latest start time (or the earliest finish time is the same as the latest finish time) that activity is critical. Otherwise the slack time is calculated by subtraction. The FORTRAN program accomplishes this. The output from this program is shown in Figure 8. Table 2 is a pictorial representation of this output.

Acknowledgments:

1.    Samuel L. Baker, University of South Carolina, Norman J. Arnold School of Public Health, Dept. of Health Administration.
2.    Bob Luttman, Robert Luttman and Associates.
3.    Delivering on Time, Stephen Richard, Manager, Multimedia Development, McGraw-Hill Book Company, Europe.

Activity	Description	Predecessor	Duration
A	Ground Clearance	(None)	3 days
B	Excavation	A	3 days
C	Placing Framework	B	2 days
D	Placing Reinforcement	B	3 days
E	Concreting Slab	C, D	2 days
F	Plumbing Connections	C	6 days
G	Raising Wall Studs	E	4 days
H	Placing Sheet Rock	G	3 days
I	Plastering Wall	H	4 days
J	Mechanical Connections	F	7 days
K	Electrical Connections	I	4 days
L	Tiles and Carpets	E	8 days
M	Placing Roof Trusses	G	5 days
N	Framing Doors and Windows	G	6 days
O	Finishing Roof	M	3 days
P	Finishing Touches	J, K, L, N, O	2 days

TABLE 1

PATHFINDER

PATHFINDER

Activities
	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Dummy
Nodes
	1	2	3	3	5	4	6	8	9	7	10	6	8	8	11	12	4	Start
	2	3	4	5	6	7	8	9	10	12	12	12	11	12	12	13	5	End
Times
	3	3	2	3	2	6	4	3	4	7	4	8	5	6	3	2	0
Paths
	1	1	1	0	0	1	0	0	0	1	0	0	0	0	0	1	0	23
	1	1	0	1	1	0	0	0	0	0	0	1	0	0	0	1	0	21
	1	1	1	0	1	0	0	0	0	0	0	1	0	0	0	1	1	20
	1	1	0	1	1	0	1	0	0	0	0	0	0	1	0	1	0	23
	1	1	1	0	1	0	1	0	0	0	0	0	0	1	0	1	1	22
	1	1	0	1	1	0	1	0	0	0	0	0	1	0	1	1	0	25
	1	1	1	0	1	0	1	0	0	0	0	0	1	0	1	1	1	24
	1	1	0	1	1	0	1	1	1	0	1	0	0	0	0	1	0	28
	1	1	1	0	1	0	1	1	1	0	1	0	0	0	0	1	1	27
																	MAXIMUM	28
	A	B	C			F				J
	A	B		D	E							L				P
	A	B	C		E							L				P
	A	B		D	E		G							N		P
	A	B	C		E		G							N		P
	A	B		D	E		G						M		O	P
	A	B	C		E		G						M		O	P
	A	B		D	E		G	H	I		K					P	CRITICAL
	A	B	C		E		G	H	I		K					P

ALGORITHM

Initialization

Step 0: Place a BOP at the beginning of the project if there is no activity which must precede all others (i.e. when several activities may begin in parallel). Place an EOP node at the end of the project if there is no activity which must follow all others (i.e. when several activities may end in parallel). Place an ES flag value of zero on the designated origin node, and let EF(1) = d(1) for the first node (where the duration of both BOP and EOP nodes is taken to be zero).

Forward Pass

Step 1: Pick any node k such that all of its predecessors have EF time flags. If none remain, i.e. the last or EOP node has just been flagged, go to the Backward Pass.

Step 2: Let the ES(k) time for the selected node be the maximum of the EF times at the preceding nodes, and set the EF(k) time for node k equal to ES(k) + d(k). Return to step 1. Mathematically, we can write formulas for the early start and finish times as follows:

Backward Pass

Initialization: Set the LF time at the last or EOP node equal to the EF time, so that no delays at the final project time are allowed. Then set the LS there equal to the ES, as well. Hence the node slack at the last node is zero, by definition.

Step 3. Choose any node such that all following nodes have LS time flags. If none remain, i.e. the beginning or BOP node has just been flagged, go to the computation of slacks.

Step 4. Set the LF(j) time for the selected node to the minimum of the LS times at the succeeding nodes, and set the LS(j) time for node j equal to LF(j) - d(j). Return to step 3. Mathematically, we can write formulas for the late start and finish times as follows:

Activity Slacks

Let activity slack S(k) = LS(k) - ES(k) for each node. Activities with zero slack are called critical activities, and are always found on one or more critical paths. This (or these) critical path(s) determine minimum project duration since all of them must be completed as part of the project, and all non critical activities can be completed concurrently with the critical activities.

PROGRAM

C     THIS PROGRAM FINDS THE CRITICAL PATH
   10 FORMAT(4X, 6(3X, I2))
C     EF = EARLIEST FINISH, ES = EARLIEST START, LF = LATEST FINISH, LS = LATEST START
        INTEGER TIMES(16), EF(16), ES(16), LF(16), LS(16), SLACK(16)
        PRINT *, 'ACTIVITY   ES   EF   LS   LF SLACK'
        PRINT *, '--------   --   --   --   -- -----'
C     ENTER THE TIMES FOR THE ACTIVITIES
        TIMES(1) = 3
        TIMES(2) = 3
        TIMES(3) = 2
        TIMES(4) = 3
        TIMES(5) = 2
        TIMES(6) = 6
        TIMES(7) = 4
        TIMES(8) = 3
        TIMES(9) = 4
        TIMES(10) = 7
        TIMES(11) = 4
        TIMES(12) = 8
        TIMES(13) = 5
        TIMES(14) = 6
        TIMES(15) = 3
        TIMES(16) = 2
C     FORWARD PASS
C     START WITH TIME ZERO FOR THE FIRST ACTIVITY AND ADD TIMES
        ES(1) = 0
        EF(1) = ES(1) + TIMES(1)
        ES(2) = EF(1)
        EF(2) = ES(2) + TIMES(2)
        ES(3) = EF(2)
        EF(3) = ES(3) + TIMES(3)
        ES(4) = EF(2)
        EF(4) = ES(4) + TIMES(4)
C     ACTIVITY E MUST START ONLY AFTER THE COMPLETION OF ACTIVITIES C AND D
        ES(5) = MAX(EF(3), EF(4))
        EF(5) = ES(5) + TIMES(5)
        ES(6) = EF(3)
        EF(6) = ES(6) + TIMES(6)
        ES(7) = EF(5)
        EF(7) = ES(7) + TIMES(7)
        ES(8) = EF(7)
        EF(8) = ES(8) + TIMES(8)
        ES(9) = EF(8)
        EF(9) = ES(9) + TIMES(9)
        ES(10) = EF(6)
        EF(10) = ES(10) + TIMES(10)
        ES(11) = EF(9)
        EF(11) = ES(11) + TIMES(11)
        ES(12) = EF(5)
        EF(12) = ES(12) + TIMES(12)
        ES(13) = EF(7)
        EF(13) = ES(13) + TIMES(13)
        ES(14) = EF(7)
        EF(14) = ES(14) + TIMES(14)
        ES(15) = EF(13)
        EF(15) = ES(15) + TIMES(15)
C     ACTIVITY P CAN START AFTER ALL OTHER ACTIVITIES ARE COMPLETE
        ES(16) = MAX(EF(10), EF(11), EF(12), EF(14), EF(15))
        EF(16) = ES(16) + TIMES(16)
C     BACKWARD PASS
C     LATEST FINISH IS SAME AS EARLIEST FINISH
        LF(16) = EF(16)
        LS(16) = LF(16) - TIMES(16)
        LF(15) = LS(16)
        LS(15) = LF(15) - TIMES(15)
        LF(14) = LS(16)
        LS(14) = LF(14) - TIMES(14)
        LF(13) = LS(15)
        LS(13) = LF(13) - TIMES(13)
        LF(12) = LS(16)
        LS(12) = LF(12) - TIMES(12)
        LF(11) = LS(16)
        LS(11) = LF(11) - TIMES(11)
        LF(10) = LS(16)
        LS(10) = LF(10) - TIMES(10)
        LF(9) = LS(11)
        LS(9) = LF(9) - TIMES(9)
        LF(8) = LS(9)
        LS(8) = LF(8) - TIMES(8)
C     ACTIVITY G MUST FINISH BEFORE START OF ACTIVITIES H, M AND N
        LF(7) = MIN(LS(13), LS(8), LS(14))
        LS(7) = LF(7) - TIMES(7)
        LF(6) = LS(10)
        LS(6) = LF(6) - TIMES(6)
C     ACTIVITY E MUST FINISH BEFORE START OF ACTIVITIES G AND L
        LF(5) = MIN(LS(12), LS(7))
        LS(5) = LF(5) - TIMES(5)
        LF(4) = MIN(LS(5), LS(6))
        LS(4) = LF(4) - TIMES(4)
C     ACTIVITY C MUST FINISH BEFORE ACTIVITIES E AND F
        LF(3) = MIN(LS(5), LS(6))
        LS(3) = LF(3) - TIMES(3)
        LF(2) = MIN(LS(4), LS(3))
        LS(2) = LF(2) - TIMES(2)
        LF(1) = LS(2)
        LS(1) = LF(1) - TIMES(1)
C     PRINT THE RESULTS
        DO I = 1, 16
        SLACK(I) = LF(I) - EF(I)
        PRINT 10, I, ES(I), EF(I) , LS(I), LF(I), SLACK(I)
        END DO
        PRINT*, '                    Figure 8'
        END
$ fortran cpm.for
$ link cpm
$ run cpm

ACTIVITY ES EF LS LF SLACK

1 0 3 0 3 0

2 3 6 3 6 0

3 6 8 7 9 1

4 6 9 6 9 0

5 9 11 9 11 0

6 8 14 13 19 5

7 11 15 11 15 0

8 15 18 15 18 0

9 18 22 18 22 0

10 14 21 19 26 5

11 22 26 22 26 0

12 11 19 18 26 7

13 15 20 18 23 5

14 15 21 20 26 5

15 20 23 23 26 3

16 26 28 26 28 0

ACTIVITY	DESCRIPTION	EARLIEST START TIME	EARLIEST FINISH TIME	LATEST START TIME	LATEST FINISH TIME	STATUS
A	Ground Clearance	0 days	3 days	0 days	3 days	CRITICAL
B	Excavation	3 days	6 days	3 days	6 days	CRITICAL
C	Placing framework	6 days	8 days	7 days	9 days	Slack(1)
D	Placing Reinforcement	6 days	9 days	6 days	9 days	CRITICAL
E	Concreting Slab	9 days	11 days	9 days	11 days	CRITICAL
F	Plumbing Connections	8 days	14 days	13 days	19 days	Slack(5)
G	Raising Wall Studs	11 days	15 days	11 days	15 days	CRITICAL
H	Placing Sheet Rock	15 days	18 days	15 days	18 days	CRITICAL
I	Plastering Wall	18 days	22 days	18 days	22 days	CRITICAL
J	Mechanical Connections	14 days	21 days	19 days	26 days	Slack(5)
K	Electrical Connections	22 days	26 days	22 days	26 days	CRITICAL
L	Tiles and Carpets	11 days	19 days	18 days	26 days	Slack(7)
M	Placing Roof trusses	15 days	20 days	18 days	23 days	Slack(3)
N	Framing Doors and Windows	15 days	21 days	20 days	26 days	Slack(5)
O	Finishing Roof	20 days	23 days	23 days	26 days	Slack(3)
P	Finishing touches	26 days	28 days	28 days	28 days	CRITICAL

TABLE 2

ACTIVITY	ES	EF	LS	LF	SLACK
1	0	3	0	3	0
2	3	6	3	6	0
3	6	8	7	9	1
4	6	9	6	9	0
5	9	11	9	11	0
6	8	14	13	19	5
7	11	15	11	15	0
8	15	18	15	18	0
9	18	22	18	22	0
10	14	21	19	26	5
11	22	26	22	26	0
12	11	19	18	26	7
13	15	20	18	23	5
14	15	21	20	26	5
15	20	23	23	26	3
16	26	28	26	28	0