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 $\left(X_{\text{start}}\right)$ 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. $Y_A$ is the number of weeks by which we will crash activity $\text{A, }{Y}_B$ is the number of weeks by which we will activity B, and so on, up to $Y_H.$

Constraints Describing The Network

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

$$\begin{array}{lll}\hfill \text{Earliest finish time}& \ge \hfill & \text{Earliest finish time for predecessor + Expected activity time}\hfill \\ \hfill \text{EF}& \ge \hfill & {\text{EF}}_{\text{predecessor}}\text{ + (t }-Y\text{)}\hfill \end{array}$$

or

$$X\ge X_{\text{predecessor}}+\left(t-Y\right)$$

The activity time is given as $t-Y,$ or the normal activity time minus the time saved by crashing. We know $\text{EF}=\text{ES}+$Activity time and $\text{ES}=$Largest EF of predecessors.

We begin by setting the start of the project to time zero: $X_{\text{start}}=0.$

For activity A,

$$X_A\ge X_{\text{start}}+\left(2-Y_A\right)$$

or

$$X_A-X_{\text{start}}+Y_A\ge 2$$

For activity B,

$$X_B\ge X_{\text{start}}+\left(3-Y_B\right)$$

or

$$X_B-X_{\text{start}}+Y_B\ge 3$$

For activity C,

$$X_C\ge X_A+\left(2-Y_C\right)$$

or

$$X_C-X_A+Y_C\ge 2$$

For activity D,

$$X_D\ge X_B+\left(4-Y_D\right)$$

or

$$X_D-X_B+Y_D\ge 4$$

For activity E,

$$X_E\ge X_C+\left(4-Y_E\right)$$

or

$$X_E-X_C+Y_E\ge 4$$

For activity F,

$$X_F\ge X_C+\left(3-Y_F\right)$$

or

$$X_F-X_C+Y_F\ge 3$$

For activity G, we need two constraints, since there are two predecessors. The first constraint for activity G is

$$X_G\ge X_D+\left(5-Y_G\right)$$

or

$$X_G-X_D+Y_G\ge 5$$

The second constraint for activity G is

$$X_G\ge X_E+\left(5-Y_G\right)$$

or

$$X_G-X_E+Y_G\ge 5$$

For activity H, we need two constraints, since there are two predecessors. The first constraint for activity H is

$$X_H\ge X_F+\left(2-Y_H\right)$$

or

$$X_H-X_F+Y_H\ge 2$$

The second constraint for activity H is

$$X_H\ge X_G+\left(2-Y_H\right)$$

or

$$X_H-X_G+Y_H\ge 2$$

To indicate the project is finished when activity H is finished, we have

$$X_{\text{finish}}\ge X_H$$

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.

Figure 11.2 Full Alternative Text