Tag Archives: CPM

Formulation and Resolution of a model of Linear Programming to reduce the duration of a Project (Crashing)

In Project Management one of the key aspects is determining the costs to complete the project in a given time. Likewise it is of particular interest to efficiently face the problem of how to reduce the duration of it in the most economical way, on the premise that certain activities could eventually be developed in fewer time than estimated initially after assigning a greater amount of resources.  In this context the following article discusses the above problems through the formulation and computational resolution of a linear optimization model. Consider the following project consisting of 12 strictly necessary tasks, where the relationship of predecessors, times (in weeks) and costs is summarized in the table below:

normal-time-and-crash

For example the activity I can begin once completed the activities F and H and its estimated time is 1.5 weeks at a normal cost of $75. However, the activity I can rush (what is commonly known as a “crash” or “crashing”) so that its length can be 0.5 weeks, but with a higher cost of $135. Consequently the maximum allowable reduction for the task is 1 week (1.5 – 0.5 weeks) with an additional cost of $60. We will also assume that there is proportionality between the time of reduction and the additional cost, for example, if we wanted to reduce the activity I in 0.5 weeks (i.e. going from 1.5 to 1.0 weeks) the cost of the activity would be $105 ($75 + 0, 5*$60) and the additional cost (over the normal cost) is $30.

Then we will determine the duration of the project using the Critical Path Method (CPM), considering the estimated normal times for each activity.

cpm

The project has an estimated duration of 15.5 weeks and there is a unique critical path: A-B-D-G-H-I-K-L (note that all activities on this path have zero slack). The project cost is $2,620 and it is obtained simply by summing the normal costs of each of the activities.

In this context, the following Linear Programming model allows you to optimally deal with the problem of how reduce the duration of the project in the cheapest way possible, by reducing the time of activities (in particular of the activities belonging to the critical route(s).

Decision Variables:
decision-variables-crashing
Parameters:
parameters-crashing

Objective Function: We pretend to minimize the additional cost associated with the project after the “crashing” needed to complete the project in a given time. Note that we could add the normal cost of the project ($2,620) to the objective function as constant) in this case the interpretation of the optimal value would be the total cost of the project which has the duration of K weeks.

objective-function-crashing
Constraints:

Each activity can be reduced (if possible) within the maximum permissible reduction limit:

max-crashing

Predecessors relations between activities and the start time and reduction:

predecessor constraints

For example altogether inequalities (3) and (4) represent that the starting week home for  activity D will be bigger than or equal to the ending week (after any reduction) of the one that finishes later among the predecessor activities (B and C). Additionally, we have defined a “fictitious” or ending activity called “M” which has those activities that end up a route for the project (not necessarily critical) as predecessors, and allow us to estimate the duration of the project.

Definition of the objective time for the project:

constraint time objective

The computational resolution with Excel Solver can simulate for different values of the K parameter as to see how the results change. The minimum duration of the project will be given by the lower value of K that allows to generate a feasible instance for the optimization model.

Non negativity of the decision variables:

non negativity crashing

The results are shown in the table below where the minimum duration of the project corresponds to 8.5 weeks with a total cost of $ 3,295 ($ 675 in addition to the normal cost of the project). We can be see the optimal solution explicit when the activity begins and how it is reduced from its normal time, in the yellow cells (decision variables). For example the G activity begins after 2.5 weeks (counting the beginning of the project) and the normal length is reduced by 1.5 weeks (ie from a normal period of 3 to 1.5 weeks).

crashing-with-solver

Do you want to have the Excel file with the solution of this problem with Solver? Recommend us on Facebook, Google or Twitter using the social network tool at the bottom of this article and then download the file.