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 timecost tradeoff 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 timecost tradeoff 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 
A  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 hightemperature 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 BDEFH, for example, would not be an admissible path). The path lengths using normal times are listed in the first column.
PATH LIST
ACFH  9 
ACEGH  15 
BDGH  14 
Examination of the marginal costs for the activities
on the critical path ACEGH 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, BDGH, 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   





ACEGH 
1  E 





BDGH 
Update the compression available for E to 1. Updating
the path list accordingly yields
PATH LIST
ACFH  9  9 
ACEGH  15  14 
BDGH  14  14 
Iter  Activities Crashed  Crashed by  Project Duration  Group M/C  Added Cost  Total Costs  New Critical Path 
0   





ACEGH 
1  E 





BDGH 
2  D&E 





Reduce the availability of D and E to zero. Updating the path list accordingly results in
PATH LIST
ACFH  9  9  9 
ACEGH  15  14  13 
BDGH  14  14  13 
Iter  Activities Crashed  Crashed by  Project Duration  Group M/C  Added Cost  Total Costs  New Critical Path 
0   





ACEGH 
1  E 





BDGH 
2  D&E 






3  G 





Reduce the availability of G to zero. Updating the path list yields
PATH LIST
ACFH  9  9  9  9 
ACEGH  15  14  13  10 
BDGH  14  14  13  10 
Iter  Activities Crashed  Crashed by  Project Duration  Group M/C  Added Cost  Total Costs  New Critical Path 
0   





ACEGH 
1  E 





BDGH 
2  D&E 






3  G 






4  B&C 





Reduce the availability of B to 1 and C to zero. The updated path list becomes
PATH LIST
ACFH  9  9  9  9  8 
ACEGH  15  14  13  10  9 
BDGH  14  14  13  10  9 
Iter

Activities
Crashed 
Crashed
By 
Project
Duration 
Group
M/C 
Added
Cost 
Total
Cost 
New Critical Path  
0   





ACEGH  
1  E 





BDGH  
2  D&E 






3  G 






4  B&C 






5  A&B 





The availability of A and B are reduced to zero. The updated path list becomes
PATH LIST
ACFH  9  9  9  9  8  7 
ACEGH  15  14  13  10  9  8 
BDGH  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   





ACEGH 
1  E 





BDGH 
2  D&E 






3  G 






4  B&C 






5  A&B 






6  H 





PATH LIST
ACFH  9  9  9  9  8  7  6 
ACEGH  15  14  13  10  9  8  7 
BDGH  14  14  13  10  9  8  7 
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 tradeoff curve (convex, piecewise linear)is of interest as well, and is more easily seen from the chart.