Process Scheduling: PERT-CPM
Calculate the expected time (hours, days, weeks, or whatever) for the following tasks. Report the time to the next highest whole number.
|Task||Optimistic (shortest) Time||Most Likely Time||Pessimistic (longest) Time||Expected Time (answer)|
|Each of these CPM diagrams corresponds to one of the task lists given below. Match them. Ex. A:#, B:#, etc.
Estimated and crash costs for each task are shown in the table below.
Answer the questions below the table.
|Version 1||Original Estimates||Crash Estimates||Crash Differentials|
CP=Critical Path. If task is on CP, then *; otherwise blank.
- Fill in the blank cells under Crash Differentials.
- Instead of the scheduled 7 weeks, Task B took 9 weeks. Which task or tasks should be crashed to make up the lost time, at minimum cost? Explain.
References (You don’t have to use them all)
Campbell, S. (1982). Critical path method. Appraisal Journal, 50(4), 607-15.
Foltz, B. (2012). Operations management 101: Critical path analysis part II
(Video file). Retrieved on 8 Oct 2014 from
Sporkforge. (2008). Critical path calculator. Retrieved on 8 Oct 2014 from
PERT stands for Program Evaluation and Review Technique; CPM stands for the Critical Path Method. These are conceptually distinct, but are frequently taught together, as we’ll do here.
The PERT and CPM procedures have been greatly expanded and elaborated upon by the project management profession. These elaborations are essential when projects are vast and complicated, and they’re usually supported by equally elaborate computer apps. In this module, many of those elaborations are ignored. The emphasis will be on understanding basic principles. If you remember that much, when you’re working as a manager, then you’ll recognize situations in which PERT-CPM might be useful. Following that recognition, you can then go to the Web; either to review the PERT-CPM procedures or, more likely, to find and hire a consultant.
PERT-CPM is frequently taught as a project management tool. There, it’s used to determine the probable duration of a project, and its total cost. But PERT-CPM also valuable for the analysis of existing processes; not necessarily from beginning to end, but from one point in the process to another, further downstream. These two points may define the steps that you, as a manager, are examining as part of a continuous improvement initiative.
There are two big questions that PERT-CPM answers. The first is about task length—how long is something going to take, or analogously, how much is it going to cost? That’s answered by PERT. The second is about project length—given a series of interrelated tasks, how long will it take to get everything done? That’s answered by CPM.
Let’s jump into the discussion with some examples.
Your company is migrating to a new MIS. For your sins, you’ve been made the project officer. The CIO needs to know how many weeks it will take; in particular, she needs one number that she can present to the Board. “One number!” she tells you, waggling a manicured finger under your nose. “That’s one, O-N-E. Not a range, not a band, not some list of numbers along with a list of maybes and what-ifs. One number. And it had better be on target, or darn close.”
You convene a meeting of the company’s most experienced IT professionals, plus representatives from the vendor. Three different numbers are heard repeatedly; an optimistic time (“If everything goes right, we’ll be done in 3 weeks”), a pessimistic time (“But it could take as long as two months”) and a most likely time. (“Actually, though, I think six weeks would be a good guess.”) These numbers are helpful, but they’re not the single number the CIO wants from you.
You consider various options. Obviously, you could take an average of everyone’s most optimistic numbers, but that average would probably be wrong. You could average of the most pessimistic numbers, but that would probably result in wasted time, since the company would adjust its schedule to accommodate a project that would, in the end, not take as long as expected. You could average everyone’s most likely times, but that doesn’t seem right either; both the optimistic and the pessimistic outcomes are possible, and those numbers should be incorporated into the estimate in some way.
The PERT solution goes like this. First, settle on three numbers; optimistic, pessimistic, and likely. Each of these could be obtained using some sort of group decision process, such as the Delphi technique. With these three numbers in hand, calculate a single value, a so-called expected value, in a way that includes the optimistic, pessimistic and most likely values, but puts the most weight on the most likely value. In PERT, the optimistic and the pessimistic estimates both get a weight of one; the most likely, a weight of four. Here’s the formula.
|O = optimistic value|
|P = pessimistic value|
|L = most likely value|
|E = expected value|
Here’s an example. Suppose the group decides that the best outcome you could hope for is to be finished in three weeks. That’s O. But if things get really out of hand, it could take as long as two months, or eight weeks. That’s P. But it’s most likely the project will be finished by six weeks. That’s L. The number you want to give to the CIO is the expected completion time, E. That’s:
Since 0.83 weeks is 5.8 days, it would probably be a good idea to round that number up to six weeks. You would, of course, want to tell the CIO that you’ve done that.
TEST YOUR UNDERSTANDING I
Here’s a table with the pessimistic (P), optimistic (O), and most likely (L) times for three tasks. Calculate the expected (E) times. The answer is given on the page: Module 4 TYU Answers. Don’t peek!
Time is given in days. Round the expected times up to the nearest whole day. This is reasonable, since most workers are paid for whole days; if they show up, they get paid.
And now, for a completely different scenario.
One of the few domestic tasks Bill’s wife entrusts him with is fixing breakfast. The menu never varies; hot oatmeal with cinnamon and raisins, buttered toast, hot tea, and OJ.
Over the years, Bill has observed that the two activities that take the most time are heating the two bowls of oatmeal in the microwave. (If a bowl isn’t on the middle of the turntable, it boils over. So he has to cook the bowls separately.) That takes 5 minutes 30 seconds per bowl, for a total of 11 minutes. Moving the various ingredients from the cupboard and fridge to the counter, and fixing the first bowl, takes two minutes; swapping the bowls in the micro after the first one is finished takes 20 seconds. Taking the food to the table takes another 20 seconds. These tasks—setting up, cooking the oatmeal, serving—have to be done in sequence. Everything else in the breakfast routine, such as pouring the OJ, making and buttering the toast, making the tea and putting stuff back into the fridge, can be done while the oatmeal is in the micro.
That sequence of events—setup, cooking the oatmeal, serving—is the critical path. If Bill wants to get breakfast on the table more quickly, he’ll have to find some way to shorten one or more of the tasks on that path. One possible solution would be to buy a micro that only needs three minutes to cook a bowl of oatmeal, instead of five and a half minutes.
Let’s formalize that idea.
Suppose a project consists of eight tasks, labeled A through H. Each task takes a certain amount of time; that would be its expected time, which we learned how to calculate above. All the tasks have to be completed before the project itself is completed, but some tasks have to be finished before other tasks can go forward (such as getting the breakfast fixings onto the counter before the first bowl can go into the micro). The ones that necessarily come before others are called predecessors.
We begin with a starting point—always a good place to start. The starting point doesn’t require any time. It’s just the point where the clock starts to run. (We’ll leave out the task times for the moment, and put them in later.) Suppose tasks A and B go first; they have no predecessors, and they can start at the same time. In the breakfast example, A might be making the oatmeal, while B is making the tea; Bill can do the first task while his wife does the second, on the other side of the kitchen.
Let’s make a list of tasks and predecessors, and simultaneously draw a timeline diagram that runs from left to right.
Task A must be completed before C can begin; task B must be completed before D can begin. That is, A is C’s predecessor, and B is D’s predecessor. Since time runs from left to right, C must be shown after (to the right of) A, and D must be shown after B.
Let’s assume that C is the predecessor of both F and E, while both D and E are predecessors of G.
The last task is H. It has two predecessors, F and G. After H is finished, the project itself is finished. We arrive at the End, which doesn’t have any time associated with it. It’s just the finish line.
The first step in determining the critical path is to list in the expected times for the tasks, if we haven’t already. We’ll add a column for the task times, to the right of the Task column.
|(Time in weeks)|
So far, we’ve been following the example that Foltz (2012) works out in his online video. But at this point, we’ll part company with him. Foltz explains a technique that involves calculating the early and late start times of each activity, calculating the so-called slack time for each activity, and then determining the critical path as the one consisting of activities having zero slack. That’s fine, and it works great for complicated projects. But for the moment, we’ll take a more simple-minded approach. That’s because we’re only trying to understand what’s going on.
By an empirical inspection process (that is, by looking), we discover that there are three distinct paths between Start and End. Even though it’s obvious, it’s worth pointing out that every path must run from left to right, with no backtracking; that’s because we can’t travel backwards in time.
Here are the paths, in bold.
The tasks on each path having non-zero expected times are ACFH, ACEGH, and BDGH.
Determine the length (total duration) of each path by finding the total of the expected task times.
ACFH = 2 + 2 + 3 + 2 = 9
ACEGH = 2 + 2 + 4 + 5 + 2 = 15
BDGH = 3 + 4 + 5 + 2 = 14
The longest path is the critical path. It’s ACEGH. If everything goes according to plan, then the project will take 15 weeks, from start to finish, and not one day less.
But what happens if something doesn’t go according to plan? Suppose we sign a contract promising to finish in 15 weeks, but activity A takes three weeks instead of the expected two. That will lengthen the critical path from 15 to 16 weeks, and that’s not good. We’ll have to make up the week by shortening one of the other activities on the critical path. But which one? Making that decision requires us to consider costs.
Before beginning the project, we negotiate a price for each of the tasks. The prices are either paid to contractors, or charged against our company’s budget; but in either event, they’re paid. Nothing’s free!
The prices are based on the expected times required to complete the tasks. Typically, longer tasks cost more, although this depends to a great extent on what’s being done. For example, pouring concrete for a new building’s foundations costs less, per man-hour, than installing the wiring.
In deference to Murphy’s Law1, we also negotiate a crash time for each task, along with a crash price. The crash time is shorter, but the crash price is also higher—the contractor agrees to put extra workers on the job, or pay overtime, or whatever, in order to shorten the task by an specific length of time, but only in exchange for a larger fee.
Crashing a task is an all-or-nothing proposition. Here’s an example. Suppose we’re building a house. Pouring the foundation takes four days instead of the expected three. In order to stay on schedule, we have to shave a day off some other task. Assume we decide to “crash” the next task on the critical path, which is framing. Instead of paying $5,000 for five days, we go to the agreed-upon crash option, and pay $7,000 for three days. That makes up the lost day, plus a day—but taking “half a crash” isn’t an option. We can’t split the difference, and pay $6,000 to get the framing done in four days. Both the regular schedule/price and the crash schedule/price have already been discussed and settled, in advance. We have to take one or the other.
So which task do we crash? It depends upon where we are in the project, how much time we have to make up, and also upon the cost of crashing; that is, how much extra we’d have to pay. To make this clear, let’s go back to the eight-task project we considered above, and add in costs.
(Estimated task time in weeks. Costs in $1K)
To clarify things, we’ll highlight the tasks on the critical path, and insert two new columns; the time saved by crashing that task, and the extra cost of doing so.
Now let’s look at some possible scenarios.
- Task A, scheduled for two weeks, actually takes three. How should we make up that time?
First, we look at the tasks that will save one week, if crashed. Task A can’t be crashed—it’s already been completed, and in the process, it burned the extra week that we now have to make up. The other tasks that would save a week are B, C, D, E, F and H. Of those, the cheapest would be F, with an extra cost of $2,000—but wait, making F a week shorter won’t help at all, because it’s not on the critical path! The cheapest alternative on the critical path is E; crashing that task makes up the week, and only costs an extra $3,000.
- Task C, scheduled for two weeks, actually takes four. How should we make up that time?
Task A is already out of consideration; it’s in the past. So is C; it’s the one that ran over, and caused the problem. Looking at the remaining tasks on the critical path, we see there are two ways of making up two weeks: crash both E and H, for a total additional cost of $9K, or crash G, for an additional cost of “only” $5K. The latter is the obvious choice.
- Task F, scheduled for three weeks, takes five. How should we make up that time?
This is trickier. At first glance, it looks like we don’t have to worry, because F is not on the critical path. It is, however, on path ACFH, which has a nominal length of nine weeks. Adding two weeks to that path lengthens it to 11 weeks, which is still shorter than the critical path. So having verified that slipping F by two weeks won’t change the critical path, we decide we don’t have to do anything.
- Task G, scheduled for five weeks, takes seven. How should we make up that time?
We’re in trouble. The only remaining task is H, and crashing that will only make up one week. If we do nothing, we’ll overshoot the scheduled end date by two weeks; if we crash H, we’ll be an extra $6K out of pocket, and still overshoot by one week. It’s time to review the penalty clauses in the contract, talk to the customer, and try to work something out.
TEST YOUR UNDERSTANDING II
Here’s a simple project consisting of four tasks, A through D.
(Times in days, costs in hundreds of dollars)
- Based on the (expected) times, what’s the critical path?
- What’s the length of the critical path?
- The first task on the critical path slips by one day. Which, if any, task(s) should be crashed, to get the project back on schedule?