At times, projects have deadlines that may be impossible to meet using the normal procedures for completion of the project. By using overtime, working weekends, hiring extra workers, or using extra equipment, it may be possible to finish a project in less time than is normally required. However, the cost of the project will usually increase as a result. When CPM was developed, the possibility of reducing the project completion time was recognized; this process is called crashing.
When crashing a project, the normal time for each activity is used to find the critical path. The normal cost is the cost for completing the activity using normal procedures. If the project completion time using normal procedures meets the deadline that has been imposed, there is no problem. However, if the deadline is before the normal project completion time, some extraordinary measures must be taken. Another set of times and costs is then developed for each activity. The crash time is the shortest possible activity time, and this requires the use of additional resources. The crash cost is the price of completing the activity in an earlier-than-normal time. If a project must be crashed, it is desirable to do this at the least additional cost.
Project crashing with CPM involves four steps:
Find the normal critical path and identify the critical activities.
Compute the crash cost per week (or other time period) for all activities in the network. This process uses the following formula:4
Select the activity on the critical path with the smallest crash cost per week. Crash this activity to the maximum extent possible or to the point at which your desired deadline has been reached.
Check to be sure that the critical path you were crashing is still critical. Often, a reduction in activity time along the critical path causes a noncritical path or paths to become critical. If the critical path is still the longest path through the network, return to step 3. If not, find the new critical path and return to step 3.
TIME (WEEKS) | COST ($) | CRASH COST PER WEEK ($) | CRITICAL PATH? | |||
---|---|---|---|---|---|---|
ACTIVITY | NORMAL | CRASH | NORMAL | CRASH | ||
A | 2 | 1 | 22,000 | 23,000 | 1,000 | Yes |
B | 3 | 1 | 30,000 | 34,000 | 2,000 | No |
C | 2 | 1 | 26,000 | 27,000 | 1,000 | Yes |
D | 4 | 3 | 48,000 | 49,000 | 1,000 | No |
E | 4 | 2 | 56,000 | 58,000 | 1,000 | Yes |
F | 3 | 2 | 30,000 | 30,500 | 500 | No |
G | 5 | 2 | 80,000 | 86,000 | 2,000 | Yes |
H | 2 | 1 | 16,000 | 19,000 | 3,000 | Yes |
Suppose that General Foundry had been given 14 weeks instead of 16 weeks to install the new pollution control equipment or face a court-ordered shutdown. Or suppose that there was a bonus on the line for Lester if the equipment is installed in 12 weeks or less. As you recall, the length of Lester Harky’s critical path was 15 weeks. What can he do? We see that Harky cannot possibly meet the deadline unless he is able to shorten some of the activity times.
General Foundry’s normal and crash times and normal and crash costs are shown in Table 11.9. Note, for example, that activity B’s normal time is 3 weeks (this estimate was also used for PERT) and its crash time is 1 week. This means that the activity can be shortened by 2 weeks if extra resources are provided. The normal cost is $30,000, and the crash cost is $34,000. This implies that crashing activity B will cost General Foundry an additional $4,000. Crash costs are assumed to be linear. As shown in Figure 11.11, activity B’s crash cost per week is $2,000. Crash costs for all other activities can be computed in a similar fashion. Then steps 3 and 4 can be applied to reduce the project’s completion time.
Activities A, C, and E are on the critical path, and each has a minimum crash cost per week of $1,000. Harky can crash activity A by 1 week to reduce the project completion time to 14 weeks. The cost is an additional $1,000.
At this stage, there are two critical paths. The original critical path consists of activities A, C, E, G, and H, with a total completion time of 14 weeks. The new critical path consists of activities B, D, G, and H, also with a total completion time of 14 weeks. Any further crashing must be done to both critical paths. For example, if Harky wants to reduce the project completion time by an additional 2 weeks, both paths must be reduced. This can be done by reducing activity G, which is on both critical paths, by 2 weeks, for an additional cost of $2,000 per week. The total completion time would be 12 weeks, and the total crashing cost would be $5,000 ($1,000 to reduce activity A by 1 week and $4,000 to reduce activity G by 2 weeks).
For small networks, such as General Foundry’s, it is possible to use the four-step procedure to find the least cost of reducing the project completion dates. For larger networks, however, this approach is difficult and impractical, and more sophisticated techniques, such as linear programming, must be employed.
Linear programming (see Chapters 7 and 8) is another approach to finding the best project crashing schedule. We illustrate its use on General Foundry’s network. The data needed are derived from Table 11.9 and Figure 11.12.
We begin by defining the decision variables. If X is the earliest finish time for an activity, then
Although the starting node has a variable associated with it, this is not necessary, since it will be given a value of 0, and this could be used instead of the variable.
Y is defined as the number of weeks that each activity is crashed. is the number of weeks by which we will crash activity is the number of weeks by which we will activity B, and so on, up to
Since the objective is to minimize the cost of crashing the total project, our LP objective function is
(These cost coefficients were drawn from the sixth column of Table 11.9.)
Constraints are required to ensure that each activity is not crashed more than its maximum allowable crash time. The maximum for each Y variable is the difference between the normal time and the crash time (from Table 11.9):
This constraint specifies that the last event must take place before the project deadline date. If Harky’s project must be crashed down to 12 weeks, then
The final set of constraints describes the structure of the network. Every activity will have one constraint for each of its predecessors. The form of these constraints is
or
The activity time is given as or the normal activity time minus the time saved by crashing. We know Activity time and Largest EF of predecessors.
We begin by setting the start of the project to time zero:
For activity A,
or
For activity B,
or
For activity C,
or
For activity D,
or
For activity E,
or
For activity F,
or
For activity G, we need two constraints, since there are two predecessors. The first constraint for activity G is
or
The second constraint for activity G is
or
For activity H, we need two constraints, since there are two predecessors. The first constraint for activity H is
or
The second constraint for activity H is
or
To indicate the project is finished when activity H is finished, we have
After adding nonnegativity constraints, this LP problem can be solved for the optimal Y values. This can be done with QM for Windows or Excel QM. Program 11.2 provides the Excel QM solution to this problem.