Project Crashing

SLOPE=(Crash Cost-Normal Cost)/(Crash Time-normal Time; if <0 as the time required for a project/task decrease, the cost increase

To formulate a project crashing problem as a linear programming problem, the user must :

  1. define variables.
  2. Define an objective function as a linear combination of decision variables.
  3. Define constraints which use linear combinations of the decision variables.

Defining the decision variables is fairly easy. The user should define two variables for each activity. The first variable should represent the amount of reduction (“crashing”) in each activity. Render and Stair use the variable :
Yj = amount of reduction in activity j.

Yi,j = amount of reduction in activity defined from beginning node i to ending node j.

The second variable should be :
endj = time at which activity j ends.

The objective function, which is to be minimized, is :

Total cost of crashing = S Cj * Yj
Crash costj – normal costj
where Cj = crash cost per day =
normal timej – crash timej

One set of constraints recognizes the limitations in crashing any individual activity. This set of constraints can be stated as :
Yj <= normal timej – crash timej

A second set of constraints recognizes that the ending time of every activity is the starting time plus the duration of that activity, and no activity can start until all of its predecessors have been completed. This set of constraints can be written as :
endj >= endpred + tj -Yj

If an activity has only one predecessor, the inequality in the constraint above could be changed to a strict equality. In general, constraints can have more than one predecessor, so the entire set of constraints is written with the more general >= relationship. Before we can use a computer program to solve the linear programming formulation, the constraint above must be put into standard form (all variables on the left side, only constants on the right side). We do this by adding the term Yj to both sides of the inequality, and subtracting the term endpred from both sides. The result can be written as :
– endpred + endj + Y>= tj

The final constraint recognizes the target for crashing. It can be stated as :
endlast <= Target

where Target must be a constant and endlast represents the end of the last activity in the project (activity with no successors). If there are several activities without successors, then it may be necessary to repeat the constraint above for each possible last activity.
If there is a specific deadline that causes a penalty if it is not met, a new variable and a special constraint should be added. The new variable can be called “late”, defined by the following statement :
late >= endlast – deadline

This statement can be turned into a constraint by multiplying both sides by -1 (which reverses the inequality) and adding the term endlast to both sides. The result will look like this :
endlast – late <= deadline

The term ‘ + penalty * late’ (where ‘penalty’ is a numerical constant ) should be added to the objective function.

you can use the following steps to crash a project :
1. Predict the time characteristics of the project including the critical path

2. Calculate crash cost / day for each activity using the formula
Crash costj – normal costj
Cj = crash cost per day = ——————————
normal timej – crash timej

3. Select the activity on the critical path with the lowest crash cost/day

4. Crash the selected activity until

it can’t be crashed any more, or
you have reached your target, or
you use up all of the slack and changed the critical path

5. repeat steps 3 and 4 until you have reached your target

Scroll to Top