Script

PROJECT SCHEDULING – CPM

Slide 1

  • Welcome back.
  • In this module we look at another approach to project scheduling called the critical path method or CPM.

Slide 2

  • CPM is
  • A deterministic approach to project scheduling.
  • It assumes that the time to complete an activity of a project depends only on the amount of money spent to complete the activity, and, given a particular amount that is proposed to be spent, the activity completion time will then be known with certainty.
  • The concept of reducing an activity’s completion time by spending more money on it is called crashing.

Slide 3

  • The concept is rather straightforward.
  • There are two extreme time/cost values that are relevant.
  • An activity will be completed in a normal time T sub N (N for Normal) for a normal cost C sub N. C sub N is the minimum cost that is required to complete the activity, and hence T sub N is the maximum time the activity will ever take.
  • At the other extreme is a minimum reduced time, T sub C (C for for crash) that can be attained by spending a maximum amount C sub C to complete the activity.
  • If any amount between C sub N and C sub C is spent, the time to complete the activity will be reduced proportional to the maximum difference in cost C sub C minus C sub N.
  • There is no need to spend more than C sub C on an activity as it is assumed that additional amounts spent will not reduce the activity’s completion time further..

Slide 4

  • So this is the time/cost relationship.
  • Suppose the maximum time reduction R (which is T sub N minus T sub C) can be attained by
  • Spending the maximum Extra amount E which equals C sub C minus C sub N)
  • Spending any proportion of the maximum extra amount, E, will give the same proportion reduction in the time reduction, R

Slide 5

  • Let’s look at a specific example.
  • Suppose an activity normally takes 20 days to complete which is done by spending $2000 on the activity.
  • The time can be reduced to 12 days by spending $4400 to complete the activity.
  • The maximum time reduction R, then is 20 – 12 or 8 days which it can achieve by spending the maximum extra amount, E of $4400 - $2000 or $2400
  • Thus the marginal cost, that is the cost to reduce the activity completion time by one day is 2400 divided by 8 or $300. We can go either way with this information.
  • Suppose, we wish to know how long it will take to complete the activity if $2600 is spent to complete it.
  • That’s $600 above the minimum amount – since the marginal cost is $300, this would be a 600 over 300 or a 2 day reduction from 20 down to 18 days.
  • Or we could ask, what would it cost to reduce the time from 20 to 17 days.
  • This is a 3 day reduction – at $300 per day, this means that $900 extra must be spent above the normal cost of $2000 – in other words $2900.

Slide 6

  • The basic CPM model was developed for achieving a deadline at a minimum total cost.
  • If the deadline cannot be met using the normal times, certain of the activities will then have to be crashed.
  • CPM can then be used to determine
  • The minimum cost which is equivalent to minimizing the total extra cost above the normal costs (since the normal costs must be spent anyway)
  • Subject to three things
  • The deadline is met
  • No activity is crashed beyond its maximum crash time
  • The precedence relations are met.

Slide 7

  • Let’s consider the following situation.
  • Baja Burrito is a chain of fast food restaurants that
  • That is planning to open a new restaurant in 19 weeks.
  • Management wishes to check and see
  • If this can be accomplished without crashing any activities
  • And determine which activities to crash and by how much, if it cannot.

Slide 8

  • This is a list of all the activities.
  • When it was solved using the normal times. The project would cost $200,000 and take 29 weeks which will not meet the 19 week deadline.
  • On the other hand, if all the activities were crashed to their minimum time values, the project would be completed in 17 weeks, but cost $300,000. The problem is to spend the minimum extra amount above the normal costs of $200,000 so that the project will be completed within 19 weeks.

Slide 9

  • Here
  • Is a network representation of the model. You can see it would be difficult to “eyeball” a minimum cost solution.

Slide 10

  • The maximum time reduction, the maximum extra cost spent to achieve such a reduction, and hence the marginal cost for achieving a one week reduction are given in this table for each activity of the project.
  • For example, for activity A, subtracting the crash time from the normal time gives a maximum 2 week reduction that can be attained by spending a maximum extra amount found by subtracting its normal cost from its crash cost of $11,000. This gives an $11,000 divided by 2 or a $5,500 marginal cost per week of reduction. The other numbers are similarly obtained.

Slide 11

  • This CPM problem can be solved by linear programming.
  • In this approach
  • The variables are of two types
  • The X’s again represent the start time for each of the activities
  • But we will also add a set of Y’s that correspond to how much we will crash each activity
  • The objective is to
  • Minimize the total extra cost spent
  • Subject to
  • The project must be completed in less than or equal to D weeks
  • No activity can be crashed more than the maximum reduction found in the previous table, and
  • The precedence relations saying that the start time for an activity cannot occur until its predecessors have been completed.

Slide 12

  • Thus for the Baja Burrito problem
  • We define the X’s as the time each activity will start and the Y’s as the amount each activity will be crashed. We will again define X(Finish) to mean the finish time for the project.
  • The objective is to minimize the total extra costs or the total cost from crashing
  • Looking down the last column this is minimize 5500YA + 10000YB and so forth down to $5,333 times YP.

Slide 13

  • The first constraint says
  • meet the deadline.
  • Which says X(Finish) must be less than or equal to 19.
  • The second set of constraints say that no activity can be crashed more than the maximum time reduction given in the second column of the table.

Slide 14

  • Finally, the last set of constraints state that the precedence relations must be kept – that is no activity can be started until all of its immediate predecessors have been completed.
  • Let’s look at the set of constraints for Activity O. The others follow in a like manner.
  • Activity O has two immediate predecessors, E and M. The time to do E is its normal time 4 less any time it is crashed, Y sub E; and the time to do M is its normal time 3 less any time it is crashed, Y sub M.
  • One constraint says O’s start time must be greater than or equal to E’s finish time
  • O’s start time is X sub O
  • E’s finish time is its start time X sub E, plus the time to do activity E which we have just established is 4 minus y sub E.
  • Similarly O’s start time must be greater than or equal to M’s finish time
  • Again O’s start time is X sub O
  • And M’s finish time is its start time X sub M, plus the time to do activity M which we have just established is 3 minus y sub M. These are two of the constraints representing the precedence relations.

Slide 15

  • So the complete list of the precedence relations
  • Which state an Activity’s start time must be greater than or equal to its immediate predecessor’s finish times
  • Is given here.
  • Of course we must also include that both the X’s and Y’s must be greater than or equal to 0.

Slide 16

  • The CPM Deadline template performs all the required calculations.
  • The input looks like this with
  • The input values of
  • Activity Names in column A, column B is automatically generated, the normal times and costs in columns C and D, and the crash times and costs in columns E and F.
  • The deadline is entered into cell E1
  • And the immediate predecessors are entered into columns H and I
  • Then Solver is Selected
  • And a preprogrammed dialogue box appears.
  • We simply click SOLVE.

Slide 17

  • This generates this output giving the minimum project completion cost of $248,750 in cell D3, the completion time of 19 in cell D4, and the lowest cost if all the activities were completed at their normal times in cell H3 and the highest cost if all activities were crashed to their limits in cell H4. The output gives the suggested completion time for each activity, a feasible start and finish time for each activity, the amount each activity should be crashed from its normal time, and the corresponding extra cost of this crashing in column G, giving the total cost, including the normal cost in column H. Incidentally the entry in cell G13, 7.87 times 10 to the minus 11-th power is taken to be 0 by Excel.

Slide 18

  • A second way CPM can be used
  • is given a total budget,
  • to determine a minimum project completion time
  • Of course, if the budget is the sum of the normal costs, no crashing can be done and the problem is simply solved with the normal times as the expected times for each of the activities.
  • But if the budget is in excess of the sum of the normal costs, crashing can take place to lower the time to complete the project.

Slide 19

  • For this new CPM model,
  • The only change is that the objective function in the previous model becomes the first constraint, and the first constrain in the previous model becomes the objective function.
  • In the CPM Deadline model
  • We minimized the sum of the extra costs
  • Subject to the project must be completed by week 19.
  • In the CPM-Budget model
  • The new objective
  • is the old first constraint – minimize X(Finish)
  • And the old objective function
  • Becomes the left side of the new first constraint which must be less than or equal to a maximum extra budget of say $25,000 on the right hand side.
  • All other constraints remain the same.

Slide 20

  • Here we see the CPM Budget template
  • The input
  • is the same
  • except in cell E1 where a maximum budget (not extra budget) is entered.
  • The immediate predecessors are entered in columns H and I except there is one small difference.
  • An Activity, which must be called END is entered in the activity description column (column A) and in the immediate predecessor columns H and I.
  • When Solver is called, a preprogrammed dialogue box appears.
  • Just click Solve.

Slide 21

  • This gives output similar to the previous model with the total project completion time and costs in cells D3 and D4 respectively.

Slide 22

  • Let’s review what we’ve done in this module.
  • We’ve stated the basic CPM assumption that if extra money is spent on an activity, its completion time reduces proportionately up to some maximum amount.
  • We gave the linear programming formulation for the cases where we had
  • To meet a deadline at minimum cost and for the case where we had to
  • Minimize the time to complete the project while operating within a fixed budget.
  • And we showed how to use the CPM-Deadline and the CPM-Budget templates.

That’s it for this module. Do any assigned homework and I’ll be back to talk to you again next time.