PROJECT CRASHING ALGORITHM

The project crashing algorithm described in this section is designed to give the mathematically correct time-cost trade-off curve for small project networks which are to be solved by hand.

The algorithm proceeds from a network description of the project and the normal and crash times and durations for the project activities to a set of tables which enable the time-cost trade-off graph to be plotted. The three tables are the project activity marginal cost list with available compression, a path list for the project network, and a breakpoint table for the steps in the project crashing process. These will be developed for an illustrative numerical example after a general statement of the algorithm is given.

GENERAL ALGORITHM SPECIFICATION

Initialization Steps.

Step 1. Each activity is assumed to have a known Normal cost if completed in a Normal time, and a (larger) Crash Cost if completed in a (shorter) Crash time. Compute the marginal crashing costs (i.e. cost per unit time) for each activity according to the following formula:

 
Marginal Cost = (change in cost)/(change in time) =  (Crash cost - Normal cost)/(Normal time - Crash time)

Place these marginal costs in the first column of the project activity list. Place the number of time periods of crashing availability in the second column of the table.

Step 2. Enumerate all the paths through the project network, and list them with their normal time durations in the path list. Identify the critical path(s) as those with longest duration, and mark the critical activities as such in the third column of the project activity list started in Step 1.

Step 3. Identify the normal project duration, the normal project cost and the normal critical path in the first row of the breakpoint table, labeled as iteration 0.

Iteration Steps.

Step 4. Select that subset of critical activities which, when compressed in parallel, enable all current critical paths to become shorter, and do so at the least group marginal cost, where the group marginal cost for a subset of critical activities is the sum of the marginal costs for activities in the group.

Step 5. Compress the selected critical activities until one or both of the following two conditions occurs: (i) one (or more) of the compressed activities becomes fully crashed (i.e. is reduced to crash time); or (ii) a new path becomes critical.

Step 6. Record the selected activities, number of time periods compressed, the new project duration, the group marginal cost for the selected activities, the added cost resulting from the compression, the new total direct cost, and the new critical path (if any) as items in the breakpoint table for this iteration. Update the compression availabilities and the path list to reflect the reduction in path lengths resulting from the selected compression.

Step 7. Repeat steps 4 through 6 until all activities on some (any) critical path become fully crashed. At this point the breakpoint table is complete, as no further time reduction is possible. Plot the time-cost trade-off graph by linear interpolation between the time/cost pairs which occur in each row of the breakpoint table.

NUMERICAL EXAMPLE
(adapted from Quantitative Analysis for Business, by Render and Stair).

General Foundry, Inc., a metalworks plant in Milwaukee, has long been trying to avoid the expense of installing air pollution control equipment. The local environmental protection group has recently given the foundry 12 weeks to install a complex air filter system on its main smokestack. General Foundry was warned that it will be forced to close unless the device is installed in the allotted period. Lester Harky, the managing partner, wants to make sure the installation of the filtering system progresses smoothly and on time.

The activities involved in the project, the precedence relations between them, and the activity durations (di) in weeks are shown in the following table:

 

                                TABLE 1: Activities and Immediate Predecessors
 

  Activity  Description  Predecessor   di 
Build internal components None 2
 B  Modify roof and floor None 3
C Construct collection stack A 2
D Pour concrete and install frame B 4
E Build high-temperature burner C 4
F Install control system C 3
G Install air pollution device D,E 5
H Inspection and testing F,G 2
 

The network representation of the project is given in the following figure:

 

 

 An analysis of early times shows that the duration of the project given the normal activity times is 15 weeks, which is 3 weeks longer than has been allotted for the project. Mr. Harky realizes that the project time must be reduced, but would like to accomplish the time reduction at least cost. Therefore, a tabulation of the normal and crash times and costs for each activity is compiled from time and cost estimates from the construction company involved, with the following result:
                                                                TABLE 2:
                                        Normal and Crash Data for General Foundry
 

  Times   Cost($)  
   (weeks)      
 
Activity Normal Crash Normal Crash
A 2 1 22,000 22,900
B 3 1 30,000 34,000
C 2 1 26,000 26,800
D 4 3 48,000 49,000
E 4 2 56,000 57,400
F 3 2 30,000 30,500
G 5 2 80,000 86,000
H 2 1 16,000 19,000
 

    The first step in the procedure is to compute the marginal crash costs and the available compression for each each project activity in the project activity table, as shown below.

 

ACTIVITY CRASH COST 
PER WEEK
AVAILABLE 
COMPRESSION
Critical 
?
----------------------- ----------------------- ----------------------- -----------------------
A $900 1 Y
B 2000 2 N
C 800 1 Y
D 1000 1 N
E 700 2 Y
F 500 1 N
G 2000 3 Y
H 3000 1 Y
 
 

    The second step is to enumerate all the possible paths through the project network and list them in the path list for the project. (Recall that a path must respect the direction indicated on each directed arc, so that B-D-E-F-H, for example, would not be an admissible path). The path lengths using normal times are listed in the first column.

PATH LIST
 

A-C-F-H 9
A-C-E-G-H 15
B-D-G-H 14
 

    Examination of the marginal costs for the activities on the critical path A-C-E-G-H reveals that the minimum marginal cost occurs for activity E at $700 per week. We see that there are two weeks of compression available for activity E, however we must also check the path list to see if any new paths become critical as we compress activity E. Since activity E only occurs on the second path, the first and third path stay at constant duration as E is compressed. This means that the third path, B-D-G-H, becomes critical after E is crashed only one week. Thus the first breakpoint recorded in the breakpoint table occurs after activity E is compressed just one week.
 

Iter Activities Crashed Crashed by Project Duration Group M/C Added Cost Total Costs New Critical Path
0 -
-
15
-
-
308,000
A-C-E-G-H
1 E
1
14
700
700
308,700
B-D-G-H
 

    Update the compression available for E to 1. Updating the path list accordingly yields
 

PATH LIST
 

A-C-F-H 9 9
A-C-E-G-H 15 14
B-D-G-H 14 14
 
    Returning now to step 4, we seek the least cost combination of activities which, when compressed in parallel, will enable both critical paths to become shorter. Now we have a choice, since the two critical paths overlap on the G-H part of the paths. We can either crash one activity, G or H, which is common to both CPs, or we can crash two activities in parallel, one from the A-C-E branch and one from the B-D branch. Comparing the marginal costs for G and H, we find that of these two, G would have the lesser marginal cost at $2,000 per week. Along the A-C-E branch, E has the least marginal cost at $700 per week. Along the B-D branch, D has the least marginal cost at $1,000 per week. Thus the D&E combination has a group marginal cost of only $1,700 in comparison with $2,000 per week for G. Thus our next step is to compress D&E together. Since there is only one week of compression available on D and on E, the next step is to crash D&E together by one week.
 
Iter Activities Crashed Crashed by Project Duration Group M/C Added Cost Total Costs New Critical Path
0 -
-
15
-
-
308,000
A-C-E-G-H
1 E
1
14
700
700
308,700
B-D-G-H
2 D&E
1
13
1700
1700
310,400
 
 

    Reduce the availability of D and E to zero. Updating the path list accordingly results in

 

PATH LIST
 

A-C-F-H 9 9 9
A-C-E-G-H 15 14 13
B-D-G-H 14 14 13
 
    Since both D and E are fully crashed, the least cost activity from the A-C-E branch is C at $800 per week, and the least cost activity from the B-D branch is B at $2,000, so the C&B combination at $2,800 is the best that can be done using two activities in parallel. Since this is more than the $2,000 per week cost of activity G, our next step is to crash G. And since G is on both critical paths, we can crash it the full three weeks that are available for this activity. The breakpoint table then becomes as follows.

 

Iter Activities Crashed Crashed by Project Duration Group M/C Added Cost Total Costs New Critical Path
0 -
-
15
-
-
308,000
A-C-E-G-H
1 E
1
14
700
700
308,700
B-D-G-H
2 D&E
1
13
1700
1700
310,400
 
3 G
3
10
2000
6000
316,400
 
 

    Reduce the availability of G to zero. Updating the path list yields

PATH LIST
 

A-C-F-H 9 9 9 9
A-C-E-G-H 15 14 13 10
B-D-G-H 14 14 13 10
 
    Since G is now fully crashed, activity H is the only one activity which will cause both critical paths to become shorter, and it costs $3,000 per week. Thus the C&B combination is the least cost available at this point, so the next step is to crash B and C in parallel. In this case all three paths get shorter together, so no new critical paths occur. However, C has only one week of compression available, so the C&B combination can be compressed only one week. Thus the next breakpoint table is as follows.

 

Iter Activities Crashed Crashed by Project Duration Group M/C Added Cost Total Costs New Critical Path
0 -
-
15
-
-
308,000
A-C-E-G-H
1 E
1
14
700
700
308,700
B-D-G-H
2 D&E
1
13
1700
1700
310,400
 
3 G
3
10
2000
6000
316,400
 
4 B&C
1
9
2800
2800
319,200
 
 

    Reduce the availability of B to 1 and C to zero. The updated path list becomes

PATH LIST
 

A-C-F-H 9 9 9 9 8
A-C-E-G-H 15 14 13 10 9
B-D-G-H 14 14 13 10 9
 
 
    At this point A and B are the only two activities on the upper and lower branches with remaining compression availability, and their combined cost is $2,900 which is still less than the $3,000 for activity H. And since they each have only one week of compression remaining, the next step is to compress A&B together by one week.

 

Iter 
 
Activities 
Crashed
Crashed 
By
Project 
Duration
Group 
M/C
Added 
Cost
Total 
Cost 
New Critical Path
0 -
-
15
-
-
308,000
A-C-E-G-H
1 E
1
14
700
700
308,700
B-D-G-H
2 D&E
1
13
1700
1700
310,400
 
3 G
3
10
2000
6000
316,400
 
4 B&C
1
9
2800
2800
319,200
 
5 A&B
1
8
2900
2900
322,100
 
 

    The availability of A and B are reduced to zero. The updated path list becomes

PATH LIST
 

A-C-F-H 9 9 9 9 8 7
A-C-E-G-H 15 14 13 10 9 8
B-D-G-H 14 14 13 10 9 8
 

    At this point H is the only activity left to shorten the last two paths, and only one week of compression is available, so the final step in the breakpoint table is to compress H by one week.
 

Iter Activities Crashed Crashed by Project Duration Group M/C Added Cost Total Costs New Critical Path
0 -
-
15
-
-
308,000
A-C-E-G-H
1 E
1
14
700
700
308,700
B-D-G-H
2 D&E
1
13
1700
1700
310,400
 
3 G
3
10
2000
6000
316,400
 
4 B&C
1
9
2800
2800
319,200
 
5 A&B
1
8
2900
2900
322,100
 
6 H
1
7
3000
3000
325,100
 
 
 
    The final path list is therefore

PATH LIST
 

A-C-F-H 9 9 9 9 8 7 6
A-C-E-G-H 15 14 13 10 9 8 7
B-D-G-H 14 14 13 10 9 8 7
 
 
    Since both critical paths are now fully crashed, the project crashing process is complete. The optimal time-cost trade-off values are contained in the project duration and project cost columns of the final breakpoint table. The final step of the process is to graph these points and connect them with straight line segments, as shown below.

     The only remaining task is to interpolate for the project cost corresponding to the 12 week project duration of interest to Mr. Harky. Since this is just one week less than the 13 week solution in the breakpoint table, activity G will be crashed only one week rather than three, so the project cost for the 12 week schedule will be $310,400 plus $2,000 or $312,400. This result can be computed directly from the final breakpoint table, but the shape of the complete trade-off curve (convex, piece-wise linear)is of interest as well, and is more easily seen from the chart.